해시 테이블(Hash Table)

[1] 해시테이블 (Hash Table) ??

 해시 테이블은 Key, Value 형테로 데이터를 저장하는 자료구조이며, 평균 시간 복잡도가 O(1) 인 만큼 빠른 검색 속도를 제공한다. 해시 테이블이 빠른 속도를 제공하는 이유는 해시함수(hash function) 와 해시 테이블(hash table)의 버킷(bucket) 덕분이다. 해시 함수(hash function) 은 Key 값을 해시(Hash) 로 변환해주는 함수를 말하고, 버킷(bucket) 은 해시 테이블의 값을 저장하는 공간이다.

 

2. 해시테이블 동작원리

Key 값을 해시 함수(Hash Function) 을 거쳐 해시 값(Hash) 을 변환하여 해시테이블의 특정 버킷의 저장할 인덱스를 설정하고 Key, Value, Hash 와 같은 값들을 저장한다.

• 해시 함수(Hash Function) : 임의의 데이터를 정수(Integer) 로 변환하는 함수

 

3. 해시 함수

해시 함수는 크게 Division Method, Digit Folding, Multiplication Method, Univeral Hashing 기법이 존재한다.

 

1. Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기(bucket size)로 모듈러 연산을 통해 인덱스를 결정한다.
   • ( 주소 = 입력값 % 버킷 사이즈) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding : 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method : 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
4. Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

4. Hash collision

 해시 함수의 결과가 같을 경우의 데이터를 관리하는 방법을 말한다. 해시 테이블 bucket 의 데이터를 관리하는 방법은 크게 open address, seperate chaining 을 통해 해결하고 있다.

 

[1] 분리 연결법(seperate chaining)

 

Seperating Chaining 은 동일한 버킷의 데이터에 LinkedList 와 같은 자료구조를 추가해 다음 데이터 주소를 저장하는 것을 말한다. Seperating Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현하는 것이 가능하지만 동일한 버킷의 체이닝되는 데이터가 많아지면 탐색 속도가 떨어지는 단점이 있다.

 

[2] 개방 주소법(Open Addressing)

 

Open Addressing 은 비어있는 해시 테이블의 버킷을 활용하는 방법이다. Open Addressing 을 구현하기 위한 대표적인 방법은 Linear Probing, Quadratic Probing, Double Hashing Probing 이 존재한다.

 

1. Linear Probing : 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
2. Quadratic Probing : 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
3. Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

 

5. java 에서의 HashMap

자바에서는 해시 충돌 해결 방법으로 Seperate chaining 방식을 선택하고 있으며, 데이터 접근, 삽입, 삭제 시간 모두 상수 시간에 접근하지만, 같은 해시 값이 늘어난다면 값이 해당 버킷에 대한 검색 시간이 선형 시간으로 변경될 수 있기 때문에 위에서 언급한 해시함수를 선언하는 것에 대해 신중할 필요가 있다. ([이펙티브 자바] 아이템 11. equals를 재정의하려거든 hashCode도 재정의하라)

 

Reference

• https://www.youtube.com/watch?v=ZBu_slSH5Sk
• https://mangkyu.tistory.com/102
• https://www.codingeek.com/data-structure/complete-guide-open-addressing-classification-eliminate-collisions/
• https://en.wikipedia.org/wiki/Hash_table