Hash Table이란?
출처 : 위키백과 - 해시테이블
해시 테이블(hash table)
- 자료 구조 중 하나로, Key와 Value를 저장한다.
- Key, Hash Function, Hash, Value로 구성된다.
John Smith(key)의 전화번호인 521-1234(value)를 저장한다고 하자.
입력된 John Smith(key)를 Hash function에 적용해서 02(Hash)라는 값을 얻는다.
그러면 "521-1234"(value)는 미리 확보한 공간(0~15번) 중
02(Hash)에 저장하게 된다.
이후 Key 값으로 John Smith를 입력하면, Hash Function을 통해 02라는 위치값을 알게되고, 그 위치에 저장된 521-1234라는 Value값을 얻어낼 수 있다.
- 데이터를 저장할 공간을 미리 확보해야하고,
입력된 Key 값을 받아 Hash Function을 통해 Hash 값을 얻고,
Hash 값을 통해 미리 확보한 공간 어느 위치에 데이터를 저장할지 정하게 된다. - key값의 길이는 모두 달라도, 동일한 길이의 Hash 값이 나온다.
자바스크립트 언어는 High Level Language로, Low Level 메모리를 관리할 수 없다.
따라서 해시테이블을 구현할 땐, 빈 객체/배열을 사용한다.
Hash Table 시간복잡도
해시 충돌이 없다 는 조건으로, Hash Table 의 시간 복잡도 는 모두 O(1) 이다.
- Insertion : O(1)
- Deletion : O(1)
- Search : O(1)
Hash Table은 완벽한가?
Insertion, Deletion, Search 모두 시간복잡도가 O(1)인 Hash Table은 완벽해보인다.
그러나,
- 순서가 있는 데이터에는 적합하지 않다.
- Input된 key 값은 순서에 상관없이 Hash값을 기준으로 저장된다.
- 미리 데이터를 저장할 공간을 확보하고 있어야 한다.
- 좋은 Hash 함수가 있어야 한다.
좋은 Hash 함수가 되려면?
- 멱등법칙(Idempotent) 성질이 있어야 한다.
- 멱등법칙(Idempotent) : 연산을 여러 번 적용하더라도 결과가 달라지지 않는 성질
- Value를 저장되는 공간에서 고르게 분포할 수 있어야 한다.
- 미리 확보한 공간을 효율적으로 사용할 수 있도록 Hash 충돌이 적어야 한다.
- 성능이 좋아야 한다.
- Hash값을 보고 Hash 함수의 내용이 예측되어서는 안된다.
Hash Collision
출처 : 위키백과 - 해시함수
Hash collision(해시 충돌)
- 다른 Key 값이지만, 같은 Hash 값이 나올 때가 있다.
이런 현상을 해시 충돌이라 한다.
새로운 key Sandra Dee(key)를 입력했는데, Hash값으로 02(Hash)를 얻었다.
John Smith(key)의 Hash값과 같다.
Sandra Dee(key)과 John Smith(key)을 구분하지 않고 저장하면,
다른 Key값인데, 동일한 Value를 얻게 된다.
해시충돌을 해결하는 방법은 크게 2가지가 있다.
Separate Chaining
해시 충돌이 발생했을 경우, value를 linked list로 저장하는 방법이다.
출처 : GeeksforGeeks
- 장점
- 사용이 간편하다.
- 계속 key를 입력해도 Hash Table은 절대 full로 채워지지 않는다.
- 해시함수에 대한 영향이 크지 않다. (Hash값이 중복되면 계속 채워진다..)
- 데이터가 얼마나 많이, 자주 입력되거나 삭제되는지 모를 때 주로 사용된다.
- 단점
- 공간 사용이 비효율적이다. (Hash Table의 일부분은 전혀 사용되지 않을 수 있다.)
- Data를 찾을 때 Worst Case의 시간복잡도는 O(n)이다.
- Linked List로 구현되면서, link를 위한 여분의 공간도 확보해야한다.
Open Addressing
해시 충돌이 발생했을 경우, 다른 Hash값에 저장하는 방법이다.
출처 : GeeksforGeeks
Open Addressing 방법에는 3가지가 있다.
- Linear Probing (선형 탐색)
- 해시충돌이 일어나면, 그 다음 Hash값 혹은 몇 개를 건너뛰어 데이터를 저장한다.
즉, 충돌이 일어나지 않을 때까지 위치를 이동하여 저장한다.
단, Hash값 충돌로 원래 위치의 다음 위치, 그 다음 위치 순으로 입력되다보니
데이터가 군집되는 현상인 Clustering 문제가 있다.
- 해시충돌이 일어나면, 그 다음 Hash값 혹은 몇 개를 건너뛰어 데이터를 저장한다.
- Quadratic Probing (제곱 탐색)
- 해시 충돌이 일어나면 제곱만큼 위치를 건너뛰어 저장한다.
- Double Hashing (이중 해시)
- 해시 충돌이 일어나면 다른 Hash 함수를 적용한 결과를 이용한다.
참고
