해쉬테이블과 Linear Probing에 관한 정리

해쉬테이블 구조

출처 - https://khalilstemmler.com/blogs/data-structures-algorithms/hash-tables/

해쉬테이블이란 key, value 형태로 값을 저장하여 빠르게 key값만 가지고 데이터를 검색할 수 있습니다.

 

이러한 해쉬테이블은 key값은 중복이 되면 안되고, value값은 중복될 수 있는데요.

쉽게 설명하면 웹사이트에서 id로 쓰는 값이 key값이고 password가 value값입니다.

id는 같은 사람이 없지만 password는 (우연할지라도) 같을 수 있는 것과 같습니다.

 

그러면 이 key값은 어떻게 보관할까요?

 

해쉬테이블이 key 값을 저장하는 방법

해쉬테이블은 hash function에서 key값을 가져와 특정 연산을 하여 인덱스 값을 계산하는데 이를 해싱이라고 합니다.

해싱을 사용하면 키의 데이터 타입이나 크기에 상관없이 일정한 크기의 해시코드를 생성할 수 있습니다.

그리고 storage(혹은 bucket) 이라 불리는 저장공간(일반적으로 배열)의 인덱스(해시코드) 위치에 value 값을 저장합니다.

 

하지만 이렇게 hash function에서 연산을 하는 과정에서 key값이 다르더라도 function의 연산값이 같아 해시 값이 겹칠 수 있습니다.

이를 해시 충돌이라고 합니다.

 

이러한 해시 충돌을 해결하는 방법 중에는 개방 주소법(Open Addressing)과 체이닝(Separate Chaining) 방식이 있습니다.

 

해시 충돌 해결법

먼저 개방 주소법(Open Addressing)이란 비어있는 해시공간을 이용하여 빈 공간에 값을 넣는 기법이고, 체이닝(Separate Chaining)이란 같은 해시 값을 가지는 경우 자료구조(LinkedList등)를 활용하여 병렬배치하여 저장하는 방법입니다.

 

개방 주소법을 다시 나누어보면 Linear Probing, Quadratic Probing, Double Hashing Probing 있는데요.

이번 포스팅에서는 Linear Probing에 대하여 알아보겠습니다.

 

Linear Probing

Linear Probing 방식은 계산된 해시코드가 중복될 경우 그 인덱스에서 1을 추가하여 저장하는 방법입니다.

이 때 key값을 확인하여 key가 같으면 value를 업데이트 해야하고,

만약 key값은 다른데 해시코드만 같은 거라면 인덱스를 +1 해서 저장합니다.

 

예시코드

private int hash(K key) {
    return key.hashCode() % capacity;
}

public void put(K key, V value) {
    // resize 생략
    int index = hash(key);

    while (table[index] != null) {
        if (table[index].getKey().equals(key)) {
            // Key가 존재하면 value 업데이트
            table[index].setValue(value);
            return;
        }
        index = (index + 1) % capacity;
    }

    table[index] = new Entry<>(key, value);
    size++;
}

위 코드에서는 hash(key)로 해쉬코드를 연산합니다.

연산된 해쉬코드의 값을 테이블 배열의 인덱스로 사용하여 조회했을때 값이 있다면 먼저 key값을 확인합니다.

 

key값마저 동일하다면 value를 업데이트하고, 그냥 해쉬코드 값만 같다면 인덱스를 1 추가합니다.

코드를 자세히보면 그냥 1만 추가하는 것이 아니라 index = (index + 1) % capacity 형태로 저장하고 있습니다.

이는 해쉬코드 값이 배열의 범위를 벗어나면 안되기 때문에 capacity(배열의 크기)로 나누어 나머지 값을 구하는 것입니다.

(배열이 이미 가득찬 경우라면 put 메소드 시작에 배열을 늘리면 됩니다.)

 

하지만 이러한 방식은 해쉬함수로 연산한 값이 특정 부분에 몰려 클러스터링 문제를 야기할 수 있습니다.

동일한 해싱값이 있다면 탐색을 계속해야 하기 때문에 성능이 떨어지는 문제가 있습니다.

 

또한, 값을 삭제할 때에도 key값과 해싱 값이 같다는 보장이 없으므로 값을 삭제한 경우에 다른 해시값들을 다 한칸씩 땡기거나, 혹은 특정한 표기("delete" 등)를 하여 값이 삭제되었다는 걸 알려주어야하는 등의 작업이 필요합니다.