Hash Index

Hash Index란?

hash index란 데이터의 위치를 hashing을 통해 index를 저장하는 방식을 말한다.

hashing이란 특정한 hash function를 정의하여 이를 통해 key 값을 일정한 범위의 수로 변환하는 작업이다.

따라서 hash function에 key 값을 통과시키면 바로 index의 위치를 얻을 수 있기 때문에 별도의 공간이 필요하지 않다.

 

index entry들은 일정한 크기의 bucket이라는 단위로 나뉘어 저장되게 되는데,

이 때 hashing을 통해 각각의 index entry들은 어떤 bucket에 들어가게 될 지 결정되게 된다.

 

hashing은 이 bucket을 할당하는 방식에 따라 static hashing(정적 해싱)과 dynamic hashing(동적 해싱)으로 나뉜다.

static hashing은 bucket을 고정된 수 만큼만 할당하여 사용하는 방식이고,

dynamic hashing은 데이터 양에 따라 가변적으로 bucket 수를 늘려 할당하는 방식이다.

 

그렇다면 각각의 방식이 어떻게 동작하는지 자세히 알아보자.

 

 

 

Static Hashing

static hashing은 앞서 말했듯 고정된 수의 bucket을 사용한다.

그리고 hashing이란 key 값을 hash function을 통해 변환하여 데이터가 들어갈 bucket을 결정하는 작업이다.

 

그렇다면 key 값을 일정한 규칙을 통해 숫자로 변환하고 이를 n(bucket 수)으로 나누게 되면 0~(n-1) 사이의 나머지 값을 얻을 수 있고, 이 나머지 값 번째의 bucket에 데이터를 저장함으로써 데이터들을 분배할 수 있다.

 

 

실제 예시를 통해 살펴보자.

 

위와 같은 데이터들을 static hashing을 통해 bucket에 나누어보자.

 

먼저 bucket은 8개가 있다고 가정하자.

hash function은 학과의 알파벳들을 숫자로(ex. a=1, b=2, ...) 변환하여 합한 수를 8로 나눈 나머지를 반환한다.

이 때 hash function이 8로 나눈 나머지를 반환하는 이유는 bucket이 8개이므로 숫자를 0~7 내로 압축하기 위해서이다.

 

hash function을 h(key)라 하면, h("Music") = (13+21+19+9+3) mod 8 = 1 이고,

h("History") = (8+9+19+20+15+18+25) mod 8 = 2 이다.

이와 같이 모든 데이터를 hash function을 통해 bucket을 결정하여 삽입하면 아래와 같이 된다.

 

 

데이터들이 hashing을 통해 8개의 bucket에 나뉘어 담긴 모습을 볼 수 있다.

 

 

※ Bucket Overflow

그렇다면 데이터가 8개의 bucket 중 하나에만 삽입되면 어떻게 될까?

bucket이 가득 차 데이터가 넘치는 bucket overflow가 발생하게 된다.

 

따라서 기본적으로 이상적인 hash function은 같은 수의 key 값과, 같은 수의 record를 갖도록 설계되어야 한다.

그래야 모든 bucket에 골고루 데이터가 삽입되어 overflow를 막을 수 있기 때문이다.

 

그리고 최악의 경우 이상적으로 hash function을 구성했더라도 bucket의 수가 적거나 데이터가 너무 많다면 overflow가 발생할 수 있어, 이를 처리할 방법을 생각해야 한다.

 

bucket overflow를 handling 하기 위한 방법들은 아래 게시글의 collision handling 부분을 참고하자.

8. Hash Table

 

static hashing은 이와 같이 데이터가 많아질수록 bucket 수가 부족하여 너무 많은 overflow가 발생해 이를 handling 하는 데 자원이 많이 소모되어 성능이 하락하게 된다.

 

따라서 이와 같은 static hashing의 단점을 개선하기 위해 dynamic handling이 고안되었다.

 

 

 

Dynamic Hashing

dynamic hashing은 static hashing과 달리 bucket 수를 동적으로 바꿔가며 사용하는 hashing을 말한다.

이 글에서는 dynamic hashing의 한 형태인 extendable hashing을 다뤄볼 것이다.

 

Extendable Hashing

extendable hashing은 데이터가 늘어날 때 bucket도 추가로 할당하여 사용하는 hashing 기법이다.

 

먼저 key 값을 hash function을 통해 binary 값으로 변환한 뒤, 맨 앞 비트부터 한개씩 늘려가며 bucket을 나눈다.

이 때 분류에 사용할 bit 수를 prefix라고 하자.

 

맨 처음에는 prefix=0, 즉 0 bit, 2^0=1 개의 bucket이 사용가능하다.

데이터가 추가되면 숫자를 늘려 1 bit, 2^1=2 개의 bucket을 사용할 수 있도록 확장한다.

이렇게 데이터가 모자랄 때마다 prefix를 1씩 올려 prefix가 i 일 때, 2^i 개의 bucket을 사용할 수 있다.

 

그리고 만약에 한 종류의 key 값만 계속 들어오게 된다면, 이 때는 prefix를 증가시켜 bucket 수를 늘리는 것이 아니라, 앞서 언급한 overflow handling 기법을 사용하여 bucket을 연결리스트 형태로 연결하여 사용한다.  

 

 

예시를 이용하여 살펴보자.

 

앞서 사용한 데이터를 똑같이 dynamic hashing을 통해 삽입해보자.

 

 

먼저 임의의 hash function을 통해 key 값을 위와 같이 binary 값으로 변환하였다.

그리고 각 bucket의 크기는 2로 설정하였다.

 

 

먼저 데이터가 없을 때는 0개의 prefix를 통해 1개의 bucket 만 갖고 있다.

 

 

이제 "Srinivasan" "Wu" "Mozart" 3개의 데이터를 삽입해보자.

먼저 데이터의 수가 bucket size인 2를 초과하므로, prefix를 1 늘려 bucket을 2개로 확장한다.

각 데이터의 첫번째 bit는 1, 1, 0이므로 "Mozart"는 0번 bucket, "Srinivasan" "Wu"는 1번 bucket에 삽입된다.

 

※ 각각의 table 위 숫자는 몇개의 bit를 통해 판단하고 있는지를 나타낸다.

0번 bucket과 1번 bucket 모두 1개의 bit를 통해 분류하므로 1이 적혀있다.

 

 

이제 "Einstein" 데이터를 새로 넣어야 하고 dept는 "Physics"이며 첫번째 bit는 1이다.

하지만 이미 1번 버킷은 2개의 데이터로 가득 차있으므로 다시 prefix를 2로 늘려 bucket을 4개로 확장한다.

 

이제 각각의 entry의 prefix를 2 bit 씩 살펴보면,

"Mozart"는 00, "Wu" "Einstein"은 10, "Srinivasan"은 11이므로 각각에 맞는 bucket에 들어간다.

 

이 때, 10번 bucket과 11번 bucket은 2 bit로 구분해야 될 필요가 있으므로 위 prefix를 2로 표기해준다.

하지만 0번 버킷의 경우 1 bit 만으로 충분하므로 prefix는 1이며, address table의 00, 10 두 자리를 차지하게 된다.

 

 

이런 방식으로 모든 데이터를 삽입해보면 위와 같이 index 파일이 구성되게 된다.

 

마지막 bucket의 경우 bucket의 공간이 부족하지만 key 값이 같아 prefix를 증가시켜도 의미가 없기 때문에

overflow handling을 통해 새 bucket을 연결 리스트 형태로 연결해준 것을 볼 수 있다.