[자료구조] Hash table

Hash table

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

Direct-address Table

hash table을 알아보기에 앞서, Direct-address Table을 알아보자.

Direct-address Table(직접 주소화 테이블)이란, key값으로 k를 갖는 원소는 index k에 저장하는 방식이다. 즉, 아래 데이터를 기준으로 key값을 index로 설정하여 index 3번에는 맹짱구를 저장하고, 5번에는 김철수, 6번 정훈이, 7번에는 남맹구를 저장한다.

key: 출석번호, value: 이름

(3, 맹짱구)
(5, 김철수)
(6, 정훈이)
(7, 남맹구)

Direct-address(직접 주소화)방법을 통해 key-value쌍의 데이터를 저장하고자 하면 불필요한 공간을 낭비하거나, key가 다양한 자료형을 담을 수 없는 등 많은 문제가 발생한다.

불필요한 공간 낭비

key: 출석번호, value: 이름

(22390, 맹짱구)
(22392, 김철수)
(22393, 정훈이)
(22397, 남맹구)

22390, 22392 등의 key 값을 저장시키기 위해 앞에 무수히 많은 공간이 낭비되고 있다.

key에 다양한 자료형을 담을 수 없음

key: ID, value: 이름

(zzang9, 맹짱구)
(ironsu, 김철수)
(huni, 정훈이)
(namm9, 남맹구)

index는 0부터 시작하기 때문에, String 타입의 ID는 key값으로 저장할 수 없다.

위에서 살펴본 Direct-address Table(직접 주소화 테이블)의 단점을 보완할 수 있는 Hash table은 hash function h를 이용해서 (key, value)를 index:h(k)에 저장한다. 이를 "키 k값을 갖는 원소가 위치 h(k)에 hash된다." 또는 "h(k)는 키 k의 해시값이다."라고 표현한다.

한편, hash table을 구성하고 있는 (key, value)데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 한다.

맹짱구의 22390이란 값을 hash function에 넣으면 22390을 9로 나눈 나머지 값이 index가 된다(예제를 위해 값은 정확하지 않다). 22390을 9로 나눈 나머지 값은 0이 나왔기 때문에, index 0의 key로 22390, value로 맹짱구가 저장되었다.

Collision

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

시간복잡도 및 공간효율성

시간복잡도는 저장, 삭제 및 검색 모두 기본적으로 O(1)이지만, collistion으로 인하여 최악의 경우 O(n)이 될 수 있다.

공간효율성은 다소 떨어진다. 데이터가 저장되기 전에 미리 저장공간(slot, butket)을 확보해야 하기 때문이다. 따라서 저장공간이 부족하거나, 채워지지 않은 부분이 많은 경우가 생길 수 있다.