Hash Table

1. Hash Table이란

특정한 값을 Search 하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대하여 Time Complexity 가 O(1)이 되는 것이다.(항상 O(1)이 아니고 average case에 대해서 O(1)인 것은 collision 때문이다.) 

 

그래서 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에서 추가적인 비용이 없도록 만들어진 구조이다.

 

---

2. Hash Function

위에서 언급한 '특별한 알고리즘'을 hash method 또는 해시 함수(hash function)라고 하고 이 메소드에 의해 반환된 데이터의 고유 숫자 값을 hashcode라고 한다. 저장되는 값들의 key 값을 hash function을 통해서 작은 범위의 값들로 바꿔준다.

하지만 어설픈 hash function을 통해서 key 값들을 결정한다면 동일한 값이 도출될 수가 있다. 이렇게 되면 동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것인데 이를 Collision 이라고 한다. Collision : 서로 다른 두 개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미)되면 같은 곳에 저장할 수 없게 된다.

 

2.1 Hash Function의 조건

일반적으로 좋은 hash function은 키의 일부분을 참조하여 해쉬 값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만들어 낸다. 하지만 좋은 해쉬 함수는 키가 어떤 특성을 가지고 있느냐에 따라 달라지게 된다.

hash function를 무조건 1:1로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능하기도 하지만 그런 hash function를 만들어봤자 그건 array 와 다를 바 없고 메모리를 너무 차지하게 된다.

Collision 이 많아질 수록 Search에 필요한 Time Complexity 가 O(1)에서 O(n)에 가까워진다. 어설픈 hash function는 hash 를 hash 답게 사용하지 못하도록 한다. 좋은 hash function를 선택하는 것은 hash table의 성능 향상에 필수적인 것이다.

 

충돌 문제 해결

1. 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)
3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함