Hash table

Hash table는 어떤 자료구조인가?

hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받는다. hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다. 저장, 삭제, 검색의 시간복잡도는 모두 0(1)입니다.

 

 

Hash table

(key, value) 데이터 쌍을 저장하기 위한 방법으로 직접 주소화 방법이 잘 맞지 안습니다. hash table은 hash function h를 이용해서 (key, value)를 index: h(k)에 저장합니다. 이때 "키 K값을 갖는 원소가 위치 h(k)에 hash된다. 또는 "h(k)는 키 k의 해시값이다" 라고 표현합니다. key는 무조건 존재해야 하며, 중복되는 key가 있어서는 안됩니다. 한편, hash table을 구성하고 있는 (key, value)데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 합니다.

 

 

 

Collision

collision이란 서로 다른 key의 해시값이 똑같을 때를 말합니다. 즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이 때 collision이 발생했다고 합니다. 따라서 collision이 최대한 적게 나도록 hash function을 잘 설계하고, 어쩔 수 없이 collision이 발생하는 경우 seperate chaining 또는 open addressing등의 방법을 사용하여 해결합니다.

 

 

 

시간복잡도와 공간효율

시간복잡도는 저장, 삭제, 검색 모두 기본적으로 0(1)이지만, collision으로 인하여 최악의 경우 O(n)이 될 수 있습니다. 공간효율성은 떨어집니다. 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야 하기 때문입니다. 따라서 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 생길 수 있습니다.

 

 

 

좋은 hash function의 조건은 뭘까?

각 상황마다 good hash function은 달라질 수 있으나 대략적인 기준은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 합니다.