[알고리즘] 해시 테이블 (Hash Table)

 

Hash Table

---

Hash Table는 연관배열 구조를 이용하는 자료구조 중 하나로써 단순하게 생각하면 'key-value'의 구조라고 할 수 있다. 연관배열 자료구조(associative array)란 key와 value가 1:1로 이루어진 구조이다. Hash는 검색과 저장이 빠른 자료구조이다. 파이썬에서는 Dictionary로 구현이되어있고, 자바에서는 java.util 하위에 HashMap, Map으로 정의되어있다. 해시는 값 자체를 Index로 사용하기 때문에 시간복잡도 O(1)로 매우 빠르다.

 

hash table을 사용하여 해결할 수 있는 문제유형은 한 묶음의 데이터에 '중복이 없거나', 데이터가 몇번 발견되는지에 대한 '빈도를 세거나', '순서가 필요하지 않거나', 'key-value 쌍으로 이루어져야 관리가 쉬운' 과 같다고 생각한다.

 

 

Keywords

---

Key	- Key-value 형태에서 Key를 의미 - 고유한 값이어야 함 - hash function의 input으로 사용됨
Value	- Key-value 형태에서 value를 의미 - bucket에 저장되는 값 - Key값과 매칭되어 저장, 삭제, 검색 접근이 용이해야함
Hash function	- key를 hash로 바꾸어주는 역할을 하는 기능 - Hash collision 발생 활률을 최대한 줄이는 함수를 만드는 것이 중요
Hash	- hash function의 결과물 - bucket에서 value와 매칭되어 저장됨
Hashing	- key가 hash로 변환되는 것을 hashing이라 부름
Bucket	- 데이터를 저장하는 테이블, 즉 저장 공간을 의미
Insertion	- 데이터 삽입

 

Hash Table Data Structure

---

<hash function image: 위키백과>

Hash table은 임의의 길이로 이루어진 key들을 고정길이의 hash로 hashing한 후 이 hash들을 value와 함께 매핑하여 bucket에 저장하는 자료구조이다.

 

 

Insertion

---

위 그림을 통해 삽입되는 과정을 확인할 수 잇따. 76, 93, 40, 47, 10, 55를 삽입하려 한다. hash table에 자료를 저장하기 위해서는 key를 hash로 변경하여야 하는데, 이 변환 방법을 hash function이라고 하고 위 그림에서는 나눈 나머지를 활용하는 기법으로 구현되어 있다. 한개의 스텝만 예로 들어보자면, '76'이라는 key를 삽입하려고 할때 hash function을 통해 key를 hash인 6으로 변경하고 bucket의 6번(hash) 자리에 value를 삽입한다. 위와 같은 작업을 진행하다보면 서로 다른 Key가 동일한 hash로 hashing 될 수 있는데, 이러한 문제를 hash collision이라고 하고 이러한 문제를 해결하여야 한다. 

 

 

Deletion

---

hash table에 저장되어있는 값을 삭제할 때에는 저장소에서 해당 key와 매칭되는 value를 찾아가 삭제하면 된다. 저장소에는 hash와 value가 매칭되어 저장되기 때문에 한꺼번에 지우면 된다.

 

 

Search

---

key로 value를 찾아내는 과정은 Deletion과 유사하다. 우선 key로 hash를 구하고 hash값으로 value를 탐색하면 된다.

 

 

 

Hash Collision

---

Hash table은 무조건 Collision이 발생할 수 밖에 없는 구조이다. 그 이유는 hash 개수가 유한하게 정해져있기 때문이다. 그래서 이러한 문제를 해결할 수 있는 대안이 존재해야 한다. 바로 channing 기법이다.

Channing 기법은 hash table에 자료를 저장할때 bucket에 충돌이 일어날 경우 (여기서 충돌이라는 것은 hash function에서 hashing을 할때 동일한 bucket에 value를 삽입하는 경우) 충돌한 값을 기존 값에 연결리스트 형태로 연결시키는 것을 의미한다. 

Channing을 사용하였을때는 위처럼 유한한 hash의 개수 안에서 효율적으로 데이터를 저장할 수 있다는 장점이 있다. 하지만 특수한 상황에서는 hash의 쏠림현상이 발생하여 검색에 대한 효율을 낮출수 있다는 것이다. 결국은 hash function이 중요하다고 할 수 있다. 

 

 

reference

---

 

해시 함수 - 위키백과, 우리 모두의 백과사전

Hash table - Wikipedia

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

Implementing own Hash Table with Open Addressing Linear Probing - GeeksforGeeks