Hash Table

Hash는 배열을 사용하여 값을 저장하기 때문에 빠른 검색속도를 가지고 있다.

특정한 값을 search하는데 데이터 고유의 인덱스로 접근을 하는데 이 인덱스로 저장되는 key 값이 불규칙 하다.

그래서 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.

특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 다른 데이터의 사이에 끼어들거나, 삭제시 다른 데이터로 채울 필요가 없으므로 연산에서 추가적인 비용이 없도록 만들어진 구조이다.

 

해쉬 충돌 (Hash Collision) 방지

 

Hash Table

1. Separate Chaining

연결리스트를 이용하는 방식으로 키(Key)에 매핑된 인덱스가 가르키는 연결 리스트(Linked List)에 노드(Node)를 추가하여 값(Value)을 추가한다.

 

탐색 방법

해시 함수(Hash Function)을 통해 인덱스를 구하고 해당 인덱스의 연결 리스트(Linked List)를 선형적으로 검사하여 해당 키(Key)의 노드(Node)가 존재하는지 확인하고 값(Value)를 리턴한다.

 

삭제 방법

검색과 동일하게 해당 인덱스의 연결 리스트(Linked List)를 선형적으로 검사하여 해당 키(Key)의 노드(Node)를 삭제하면 된다.

 

 

 

 

 

 

hash Table

2. Open adressing

충돌이 발생했을 경우  해시 테이블(Hash Table)의 빈 버킷(Bucket)을 이용하는 방법이다.

3번째 인덱스에 값이 있는 경우 3번째 인덱스에 값을 추가하면 아래 버킷이 빈 공간인지 확인하고 빈 공간이면 그 자리에 추가 된다.

 

삭제 방법

충돌(Collision)에 의해 뒤에 저장된 데이터가 검색되지 않을 수 있다. 이를 방지하기 위해 삭제한 위치에 Dummy Node를 삽입한다

 

탐색방법

• 선형 탐사(Linear probing) : 가장 간단한 방식으로 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(예컨대 1칸)을 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)한다. 여기에 데이터가 있으면 고정폭으로 또 옮겨 액세스한다.

 

• 제곱 탐사(Quadratic probing) : 고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어난다는 특징이 있다. 예컨대 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면 1212칸을 옮기고 여기에서도 충돌이 일어나면 이번엔 2222칸, 그 다음엔 3232칸 옮기는 방식이다.

 

• 이중해싱(double hashing) : 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법이다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용합니다. 이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화할 수 있다.