[자료구조] 해시 테이블 (Hash Table)

해시 테이블?

해시 테이블은 키(Key)에 값(Value)를 저장하는 자료구조입니다. 파이썬의 Dict(딕셔너리)가 해시 테이블과 같은 구조입니다. 해시 테이블은 미리 데이터를 저장할 공간을 크게 확보한 후 데이터를 저장합니다. 많은 공간이 필요하지만 빠른 속도로 데이터를 찾을 수 있습니다.

 

용어

해시(Hash) : 데이터를 고정된 길이를 갖는 데이터로 매핑하는 함수

해싱 함수(Hashing Function) : 키에 대한 산술 연산을 통해 데이터 위치(인덱스)를 찾을 수 있는 함수

슬롯(Slot) : 한개의 데이터를 저장할 수 있는 공간

해시 충돌(Hash Collision) : 해싱함수를 통해 생성된 키에 대한 인덱스가 같을 경우 발생하는 충돌 상황

 

 

방식

key를 해싱함수를 통해 데이터의 위치로 변환합니다. 데이터의 위치를 해시 테이블에 저장합니다.

또한 데이터를 검색하기 위해 입력 받은 key를 다시 해싱함수를 통해 위치로 변환하여 값을 찾습니다.

 

구현

hash_table = list(0 for i in range(10))


def hash_func(key):
    hash_key = hash(key)
    store_key = hash_key % 10
    return store_key


def store(key, value):
    index = hash_func(key)
    hash_table[index] = value


def get_value(key):
    hash_key = hash_func(key)
    return hash_table[hash_key]


store('key1', 'value1')
print(get_value('key1'))

하지만 위의 방식은 충돌을 해결하지 못합니다. 만약 key1과 key2 가 hash_func를 통해 같은 index를 가지게 된다면 해시 충돌이 발생합니다.

 

해시 충돌을 해결하는 방법을 알아보도록 하겠습니다.

 

 

체이닝(Chaining)

체이닝 기법은 Open Hashing 기법 중 하나로 해시 테이블 외의 공간을 활용하는 기법입니다.

해쉬 충돌이 발생했을때 링크드 리스트로 데이터를 이어가는 방식입니다.

hash_table = list(0 for i in range(10))


def hash_func(key):
    hash_key = hash(key)
    store_key = hash_key % 10
    return store_key


def store(key, value):
    index = hash_func(key)
    if hash_table[index] == 0:
        hash_table[index] = [[key, value]]
    else:
        for i in range(len(hash_table[index])):
            if hash_table[index][i][0] == key:
                hash_table[index][i][1] = value
                return
        hash_table[index].append([key, value])


def get_value(key):
    index = hash_func(key)

    if hash_table[index] == 0:
        return None
    else:
        data_list = hash_table[index]
        for item in data_list:
            if item[0] == key:
                return item[1]

        return None


store('key1', 'value1')
store('key2', 'value2')
store('key3', 'value3')
store('key4', 'value3')

print(hash_table)

[0,
 0,
 0,
 0,
 [['key1', 'value1'], ['key3', 'value3'], ['key4', 'value3']],
 0,
 [['key2', 'value2']],
 0,
 0,
 0]

동일한 hash_index를 가지지만 리스트를 이용하여 데이터를 추가적으로 저장합니다.

 

 

선형 탐사법(Linear Probing)

선형 탐사법은 Close Hashing 기법으로 해시 테이블 안에서 충돌을 해결하는 기법입니다.

해시 충돌이 발생했을때 hash_index의 다음 index부터 맨 처음 나오는 빈공간에 저장하는 기법입니다.

hash_table = list(0 for i in range(10))


def hash_func(key):
    hash_key = hash(key)
    store_key = hash_key % 10
    return store_key


def store(key, value):
    index = hash_func(key)

    if hash_table[index] == 0:
        hash_table[index] = [key, value]
    else:
        for i in range(index + 1, len(hash_table)):
            if hash_table[i] == 0:
                hash_table[i] = [key, value]
                return
            elif hash_table[i][0] == index:
                hash_table[i][1] = value
                return


def get_value(key):
    index = hash_func(key)

    if hash_table[index] == 0:
        return None
    else:
        for i in range(index + 1, len(hash_table)):
            if hash_table[i] == 0:
                return None
            elif hash_table[i][0] == key:
                return hash_table[1][1]
    return None


print(hash_func('key1'))
print(hash_func('key2'))
print(hash_func('key3'))
print(hash_func('key4'))

store('key1', 'value1')
store('key2', 'value2')
store('key3', 'value3')
store('key4', 'value3')

print(hash_table)

 

5
9
6
6

위와 같은 hash_index가 나왔을 경우 결과입니다.

[0,
 0,
 0,
 0,
 0,
 ['key1', 'value1'],
 ['key3', 'value3'],
 ['key4', 'value3'],
 0, 
 ['key2', 'value2']]

 

 

시간 복잡도

충돌이 없는 경우 O(1)

충돌이 모두 발생하는 경우 O(n)

 

충돌이 없는 경우 key를 통해 바로 value로 접근할 수 있습니다.

하지만 해시 충돌이 모두 발생한다면 결국 n개의 데이터에서 검색해야합니다