8. Hash Table

Hash Table

데이터를 저장할 때 key 값을 사용하여 저장하면 데이터를 찾을 때 맞는 key 값을 찾는 탐색 과정이 필요하다.

따라서 데이터가 많아질수록 key 값을 위한 탐색 과정이 길어져 느려지게 된다.

 

이 때문에 key 값을 통해 바로 데이터의 위치를 알 수 있는 방법을 사용하게 된다.

key 값에 특정한 산술 연산을 하여 데이터의 주소를 얻어 데이터에 접근하게 되며, 이 과정을 Hashing 이라고 한다.

 

Hash Table은 hashing을 통해 데이터를 저장하는 dictionary를 말한다.

 

 

Hash Function

hash table에서는 hash function을 통해 key 값을 일정 범위 내의 integer 값으로 변환하여 저장한다.

따라서 hash function은 어떤 형식으로 들어올 지 모르는 key 값을 integer로 바꾸는 hash code 부분,

그리고 바뀐 integer 값을 원하는 범위로 축소시키는 compression function 으로 구성된다.

 

1. Hash Code

앞서 말했 듯 hash code는 임의의 형태로 들어온 key 값을 integer 형태로 변환하는 것이다.

따라서 들어온 key 값에 따라 방식을 나누어 변환한다.

 

1.1. Integer cast

key 값을 integer 형태로 바로 casting 하여 사용하는 방법이다.

integer 보다 적거나 같은 수의 bit를 사용하는 자료형(byte, short, int, float)에 사용한다.

 

1.2. Component sum

key 값을 일정한 수의 bit 단위로 나누어 더하는 방법이다.

integer 보다 많거나 같은 수의 bit를 사용하는 자료형(long, double)에 사용한다.

 

1.3. Polynomial accumulation

String 타입의 key 값을 component sum 방식을 사용하면 "pots" 와 "spot"이 같은 key 값을 갖게 된다.

따라서 String 타입의 key는 아래와 같이 polynomial accumulation 방식을 사용한다.

 

문자열을 char 배열로 생각하면 위와 같이 나타낼 수 있다.

 

이렇게 나뉘어진 각각의 char에 임의의 수를 차수를 늘려가며 곱한 후 더해주면 된다.

이 때 임의의 수 z는 주로 33, 37, 39, 41과 같이 1이 아닌 소수를 사용하여야 중복된 key 값을 줄일 수 있다.

 

2. Compression Function

hash code를 통해 integer 형태로 변환된 key 값은 정해진 범위 내로 축소하여 사용하게 된다.

이렇게 정해진 범위 내로 integer 값을 변환할 때는 다음과 같은 방법들을 사용한다.

 

2.1. Division

제일 간단한 형태로 key 값을 hash table의 크기 N으로 나눈 나머지를 사용하는 방법이다.

 

2.2. Multiply, Add, Divide (MAD)

key 값에 임의의 값 a를 곱하고 임의의 값 b를 더한 뒤 hash table의 크기 N으로 나눈 나머지를 사용하는 방법이다.

 

 

 

Collision Handling

그렇다면 이렇게 hash function을 통과한 key 값이 중복된 경우에는 데이터를 어떻게 저장하는지 알아보자.

 

1. Seperate Chaining

hash table의 각각의 cell을 리스트로 구현하여 새 데이터가 들어올 때마다 리스트의 뒤에 삽입하는 방법이다.

이 경우 간단하게 구현이 가능하나 추가적인 메모리가 필요하다는 단점이 있다.

 

2. Open Addressing

open addressing이란 데이터가 추가될 때마다 메모리를 추가로 할당하는 것이 아니라,

테이블 내의 빈 자리에 충돌이 발생한 데이터를 추가하는 방법이다.

 

2.1. Linear Probing

linear probing은 충돌이 발생한 cell로부터 한칸씩 이동하며 빈자리를 찾아 데이터를 삽입하는 방법이다.

 

예를 들어 위와 같은 7로 나눈 나머지를 key 값을 갖는 hash table이 있을 때 24을 새로 추가하려 한다.

24를 7로 나눈 나머지는 3인데 이미 데이터가 들어가 있어 충돌이 발생한다.

 

이 경우 key 값이 4인 자리에 빈 자리가 있으므로 여기에 데이터를 추가하게 된다.

 

여기에 46이라는 데이터를 추가하면 이미 46을 7로 나눈 나머지인 4 cell은 데이터가 들어가 있기 때문에,

한칸씩 이동하다 빈자리가 존재하는 6번 cell로 데이터가 삽입되게 된다.

 

2.2. Double Hashing

double hashing은 충돌이 발생할 경우 해당 key 값을 다른 hash function에 한번 더 통과시키는 방법이다.

이렇게 빈자리를 찾을 때까지 반복해서 hash function에 통과시키게 된다.

 

마찬가지로 7로 나눈 나머지를 key 값으로 갖는 테이블에 24를 새로 추가하려 한다.

24를 7로 나눈 나머지는 3인데 3번 cell은 이미 데이터가 있으므로 새 hash function에 다시 통과시킨다.

 

이 때 새 hash function은 key 값을 5로 나눈 값을 5에서 뺀 값으로 설정하자.

첫번째로 hash function을 통과한 값인 3을 새 hash function에 넣으면 5-3=2 가 된다.

 

따라서 24는 2번 cell에 저장되게 된다.