[CS] Hash

Hash

해시 (Hash)

키/값 쌍을 버킷이라는 배열에 저장하며 키를 사용하여 값을 빠르게 찾을 수 있는 자료구조로, 삽입, 삭제, 검색이 평균 O(1)의 속도로 아주 빠르다. 해시 함수로 만들어진 해시 값은 겹칠 수 있기 때문에 고르게 분포되는 것이 중요하다. 테이블에 데이터를 저장할 때 위치는 무작위로 지정되고 정렬할 수 없다. C++에서는 std::unordered_map이 자주 사용된다.

[STL] 10. unordered_map

해시 충돌

해시가 겹치는걸 해시 충돌이라 하는데 성능이 떨어진다. 겹침 문제를 해결하기 위한 방법으로 체이닝 기법과 오픈 어드레싱 기법 등이 있다.

충돌 문제 해결

체이닝 기법은 충돌 발생 시 버킷을 연결 리스트로 구현하는 방식으로, 충돌 시 해당 위치의 참조를 반환한다. 이렇게 하면 연결 리스트의 인덱스로 접근이 가능해진다. 오픈 어드레싱 기법은 충돌한 버킷 내에서 다른 빈 공간을 찾아 해당 값을 저장하는 방식이다. 읽을 때에는 버킷에 있는 데이터가 키 값에 맞는지 확인한 뒤 아니면 다음 공간으로 이동한다. 이중 해싱 기법은 2개의 해시 함수를 사용해 해싱한다. 첫번째 해시 함수가 충돌했다면 다른 해시 함수로 해시값을 만들어낸다.

응용

정렬이 필요 없지만 입력, 삭제, 읽기 속도가 빨라야 하는 대규모 데이터 셋에서 선호된다.

Graph

그래프 (Graph)

정점(Vertex)과 이들을 연결하는 간선(Edge)으로 구성된, 관계도를 나타내는 자료구조이다. 지도, 네비게이션, SNS나 메신저의 관계도, 깃허브의 버전관리 등의 다양하게 응용할 수 있다. 그래프의 종류로는 양방향, 일방향, 무방향, 순환, 비순환 등 여러가지가 있고, 탐색 방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있다.

주요 알고리즘

다익스트라 알고리즘(Dijkstra's Algorithm): 가중치가 양수인 그래프에서 단일 시작점으로부터 모든 정점까지의 최단 경로를 찾는 알고리즘.

벨만-포드 알고리즘(Bellman-Ford Algorithm): 가중치가 음수일 수도 있는 그래프에서 단일 시작점으로부터 모든 정점까지의 최단 경로를 찾는 알고리즘.

플로이드-와샬 알고리즘(Floyd-Warshall Algorithm): 모든 쌍의 정점 간의 최단 경로를 찾는 알고리즘.

크루스칼 알고리즘(Kruskal's Algorithm): 간선을 가중치에 따라 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성.

프림 알고리즘(Prim's Algorithm): 하나의 정점에서 시작하여 가장 낮은 가중치의 간선을 선택하면서 MST를 확장.

Tree

트리 (Tree)

그래프 자료구조 중 하나로, 계층적인 구조를 나타내며, 순환성이 없는 무방향 그래프이다. 노드는 트리를 구성하는 요소로, 데이터와 자식 노드를 가진다. 트리는 안정적일 수록 탐색의 시간 복잡도 효율이 좋다.

이진 탐색 트리

이진 트리는 자식 노드의 개수가 두 개 이하인 특징을 가지는 트리를 말하는데, 이진 탐색 트리는 이진 트리의 특성을 가지면서, 각 노드의 값이 특정 순서를 따르는 구조이고, 방향성이 있다.

left node에는 부모 노드보다 작은 값이, right node에는 부모 노드보다 큰 값이 저장된다.

모든 노드는 중복된 값을 가지지 않는다.

중복 확인 과정이 성능에 중요한 영향을 미친다면, 삽입 중에 중복을 확인하는 것이 더 효율적일 수 있다.

응용

트리는 상황과 조건에 맞게 응용할 수 있다. 이진트리, 이진탐색트리, AVL트리, 레드블랙트리 등 여러가지로 응용이 가능한데, 전부 탐색과 관련이 있다. 랭킹 검색, 디렉토리 폴더 구조에 사용할 수 있다.