Hash Table 자료구조
Hash Table 자료구조
Hashing이란 임의의 길이의 값을 Hash function을 사용하여 고정된 크기의 값으로 변환하는 작업
Hashing을 사용하여 데이터를 저장하는 자료구조를 Hash table 이라고 한다.
- Key : 고유한 값이며, Hash function의 input이 된다.
- Hash function : Key를 Hash로 바꿔주는 역할을 한다.
- Value : bucket(저장소)에 최종적으로 저장되는 값으로 Key와 매핑이 된다.
특징
- Key와 Value로 구성되어 1:1로 연관되어 있는 자료구조
- Key를 통해 Value를 구할 수 있다.
- hash function을 수행하면 array내에 저장된 index 위치를 찾아 낼 수 있어 저장과 삭제가 빠르다.
연산
- put : Key/Value가 주어졌을 때, Key/Value를 저장하는 명령[O(1)], worst : O(N)]
- search : Key가 주어졌을 때 연관되는 Value를 얻는 명령[O(1), worst : O(N)]
- delete : Key가 주어졌을 때 주어진 Key와 매핑되는 Value를 삭제하는 명령[O(1), worst : O(N)]
Collision(충돌)
서로 다른 key가 같은 hash가 되는 경우 Hash collision이라고 한다.
- Collision은 필연적으로 생길 수 밖에 없으며 Collision을 관리하는게 목표이다.
- 두가지 방법이 존재한다.
- Separate Chaining
- Open Addressing
Separate Chaining
- 충돌이 발생하면 그 index가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가한다.
- 데이터를 추출하고자 할 때는 key에 대한 hash를 구한 후, hash가 가리키고 있는 Linked list를 선형 검색하여, 해당 key에 대한 data를 return
- java8의 경우 bucket이 8이상일 경우 Tree로, 6이하일 경우 Linked list로 구성한다.
Open Addressing
- 추가적인 메모리를 사용하지 않고, hash table의 빈 공간을 사용하는 방법
- Separate chaining에 비해 메모리를 덜 사용한다.
- Hash function의 성능에 의존한다.
- 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해야 한다.
- 3가지 방식
- Linear Probing
- 충돌이 발생했을 때, index 뒤에 있는 bucket 중에서 빈 bucket을 찾아 데이터를 넣는 방식
- Quadratic Probing
- 1^2, 2^2, 3^2… 으로 탐사를 하는 방식으로 Linear Probing에 비해 탐색과 삭제에 효율적
- 하지만 초기 해시값이 같을 경우 클러스터링 문제가 발생
- Double Hashing
- 클러스터링 문제를 피하기 위해 도입
- 처음 Hash function으로 hash를 찾고, 두번째 Hash function으로 충돌이 발생했을 때 탐사폭을 계산하기 위해 사용되는 방식
- Linear Probing
- 삭제