[CLRS] [11-2,11-3] Hash Tables / Hash Function

1. Hash Table?

- 해시테이블은 해싱을 통해서 데이터를 저장하는 자료구조이다.

- 즉, 해시 함수(Hash Function)을 사용해서 변환한 값을 index로 사용해 key와 data를 저장하는 자료구조이다.

- 이러한 Hash table은 삽입, 삭제, 탐색이 대부분 O(1)으로 빠르다. 

- 대부분 이라는 건 아닌 경우도 있다는 걸까? / 이에대한 의문은 찬찬히 알아가보자.

 

2. Hash Function(해시 함수)

- Hash Function은 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 mapping해주는 함수이다.

- mapping되기전 입력되는 것을 key라고 한다면,

- 이 key를 hash function을 통해 반환되는 것을 Hash value(해시 값)이라고 한다.

- 대표적인 Hash Function에 대해서 간단하게 알아보자.

 

2.1. Division Method

 

- key를 해시 테이블의 크기(m) 으로 나눈 나머지를 hash value(해시값)으로 사용하는 방식이다.

 

2.2. Multiplication method

- kA mod 1 (0<A<1) 은 소수부분을 나타낸다.

- 즉, N* (kA mod 1)은 0~N사이의 값으로 만들어주고 이를 내림해줌으로써 정수로 return하게 해준다.

 

2.3. Universal Hashing(Random Hashing)

- key를 랜덤하데 Hashing value로 변환해주는 함수를 의미한다.

 

3. 해시 충돌(Hash Collision)

- 우리는 앞서 Hash Table은 삽입,제거,탐색을 대부분 O(1)만에 해결한다는 것을 알게되었다.

- 대부분인 이유는 해시 충돌(Hash Collision) 챕터에서 알 수 있다.'

 

- 해시 충돌은 다른 키가 같은 해시값을 가질 때 이를 해시 충돌이라고 한다.

- 이를 해결하는 방법에 대해서 알아보자.

3.1. Chaining

- 다음 처럼 중복되는 Hash Value에 대해 연결리스트로 각 key를 연결해주면 해결이 가능하다.

- 만일 정말 우연히 모든 key들이 하나의 Hash-Value를 가지게 된다면 탐색이나 제거에서 O(N)만큼 걸리게 된다

 

3.2. Open Addressing(개방 주소법)

- Chaining 기법에선 저장해야하는 인덱스에 값이 있으면 그 칸에 연결리스트를 통해 중복으로 저장했다면,

- Open Addressing에서는 그 자리를 피하는 방법이라고 생각하면 된다.

- 빈자리를 찾는 방법은 여러가지가 있는데 2가지만 알아보자.

3.2.1. Linear Probing(선형탐사)

- 해시충돌이 일어나면 바로 다음 인덱스로 이동하여 해시값을 저장하는 방식이다.

 

3.2.2. Double Hashing

- 충돌이 생기면 또 다시 해시함수로 다시 해싱하여 새로운 주소를 할당하는 방식이다.