Hash Table에 대해 설명하세요
Keyword
hash, index, collision, hashcode, hash function, key, Open Address , Separate Chaining
Script
hash table은 data를 hash function을 통해 hash code로 변환하고, 고유의 index로 작용하여 저장되기 때문에, 어떠한 값을 탐색, 삽입, 삭제에 평균적으로 O(1)의 시간복잡도로 수행이 가능합니다.
하지만 index의 중복이 발생하게 되면, collision이 일어나고 성능이 악화됩니다. 그래서 hash function을 설계할 때, collision을 최소화할 수 있도록 설계해야 합니다.
그럼에도 collision이 발생할 수 밖에 없고, 이를 해결하는 방법에는 여러가지가 있지만, 대표적으로 Open Address 방식과 Separate Chaining 방식이 존재합니다. 그리고 만약 collision이 발생했을 때, worst case에서는 O(n)의 시간복잡도로 탐색이 수행됩니다.
Additional
Open Addressing
Open Addressing은 데이터를 삽입할 때, 해당하는 key값이 이미 사용되고 있다면, 다른 hash bucket에 삽입하는 방식이다. 그 방법으로는 linear probing, quadratic probing, double hashing 등이 있다.
Separate Chaining
Separate Chaining은 추가적인 메모리를 사용하여 동일한 bucket에 값이 존재한다면, linked list를 사용하여 해당 bucket에 새로운 데이터를 추가하는 방식을 사용한다. linked list 대신 red black tree를 사용하는 경우도 있으며, 메모리 사용량을 고려할 때, 데이터 개수가 적을 때는 linked list가 유리하고 많다면 tree 구조를 사용하는 것이 유리하다.
Open Addressing vs Separate Chaining
두 방식 모두 worst case에서 O(N)의 성능을 가진다. 하지만 Open Addressing 방식은 연속된 공간에 데이터를 저장하기 때문에 상대적으로 캐시의 hit rate가 높아 데이터의 양이 적을 때는 더 효율적이다. 하지만 separate chaining 방식에 비해, open addressing은 버킷을 계속해서 사용하기 때문에 데이터가 많은 경우 hash table의 확장이 잦고 캐싱 효율이 떨어진다. 데이터가 많은 경우 separate chaining이 더 효율적이다.
| Separate Chaining | Open Addressing |
|---|---|
| hash table 내부와 외부에 모두 key가 저장됨 | 모든 key는 오직 hash table에만 저장 |
| hash table에 추가적인 메모리 공간을 사용하므로, key의 개수가 hash table의 크기를 넘을 수 있음 | 추가적인 메모리 공간을 사용하지 않기 때문에, hash table의 크기를 넘을 수 없음 |
| 삭제가 쉬움 | 삭제가 어려움 |
| 상대적으로 hash function과 load factor에 덜 민감함 | 구조상 hash function과 load factor에 민감함 |
| 주로 얼마나 많은 데이터가 얼마나 자주 삽입/삭제될지 예측할 수 없을 때 사용 | 특정 key들의 주기와 개수를 알고 있을 때 주로 사용 |
| cache 효율이 비교적 좋지 않음 | cache 효율이 좋음 |
| 전혀 사용되지 않는 bucket이 존재할 수 있는 점에서 공간의 낭비 | 직접적으로 해당 bucket에 mapping되지 않아도 그 bucket을 사용하게 됨 |
| 추가적인 메모리 공간이 필요 | 추가적인 메모리 공간을 사용하지 않음 |
Open Addressing에서의 deletion
단순히 원하는 데이터를 삭제하기만 할 경우, 선형 탐사를 위한 부분이 유실되어 open addressing의 선형 탐사가 작동하지 않을 수 있다. 이를 방지하기 위해, 삭제된 bucket은 deleted 라는 임의의 값을 저장해두어야 하는 추가적인 연산이 필요해진다. 단순히 linked list의 한 Node를 삭제하기만 하면 되는 separate chaining보다 삭제 과정이 더 복잡하다.
Load Factor
Load Factor는 hash table의 size 대비 저장된 key의 개수를 의미한다. Load Factor의 값이 클 수록 collision이 발생할 확률이 높아지고, Load Factor가 1이 되는 순간부터는 무조건 collision이 발생한다.
일반적으로는 Load Factor를 0.75이하로 유지하는 것이 이상적이다. 그래서 Load Factor가 일정 수준 이상으로 높아지면, Resize 과정을 통해 hash table size를 2배로 늘린다. 일반적으로 그 시점이 0.75가 되는 시점이다.
