기본기 톺아보기 #2 - Hash Table

이동욱·2022년 1월 10일

Hash Table 자료구조

기본기 톺아보기

목록 보기

2/5

Hash Table

Intro

자료구조는 매우 중요하지만 실제로 코딩할 때는 이미 잘 구현된 것을 사용하는 경우가 많기때문에 따로 공부해 주어야 합니다.
Hash Table은 저장, 삭제, 검색이 빈번할 경우 유리한 자료구조 입니다.

Hash Table은 키를 해시함수에 입력으로 넣어서 Hash Address값을 얻습니다.

시간복잡도 O(1)

Key값을 Hash function에 넣어 데이터가 저장된 주소값을 얻습니다.
얻은 주소값을 바탕으로 바로 데이터에 접근할 수 있습니다.
최악의 경우 시간복잡도 O(n)이 될 수도 있다고 합니다. -> Hash Collision때문에 발생

Hash Collision

Key는 무한하지만 Hash function의 결과인 주소값은 유한하기때문에 발생합니다.
그림처럼 Key2와 Key3의 Hash Function 연산 결과가 같은 address를 반환하는 경우입니다.

hash_table = list([0 for i in range(2)])

def custom_hash_function(val):
    ascii_sum = ord(val[0]) + ord(val[-1])
    return ascii_sum % 2

def store_data(key, value):
    hash_address = custom_hash_function(key)
    hash_table[hash_address] = value

def get_data(val):
    hash_address = custom_hash_function(val)
    return hash_table[hash_address]
    
name1 = 'choonsik'
name2 = 'lion'

store_data(name1, '배가고픔')
store_data(name2, '배부름')

print(get_data(name1)) # 배부름
print(get_data(name2)) # 배부름
print(hash_table) # ['배부름', 0, 0]

각각 다른 이름 name1과 name2를 생성합니다.
custom hash function을 거쳐 name을 바탕으로 hash address를 생성해서 그 주소로 hash_table에 저장합니다.
다른 이름이었지만 hash function의 결과가 같은 주소 0 을 가리키기 때문에 name1의 결과값을 name2가 덮어써버렸습니다.

해결책1 (Chaining)

Key2와 Key3의 결과가 같은 주소 1을 가리킵니다.
나중에 들어온 Key3결과 같은 경우는 Linked List를 활용해 Key1결과 뒤에 붙여서 자리합니다.

hash_table = list([0 for i in range(3)])

def custom_hash_function(val):
    ascii_sum = ord(val[0]) + ord(val[-1])
    return ascii_sum, ascii_sum % 2

def get_data(val):
    ascii_sum, hash_address = custom_hash_function(val)
    if hash_table[hash_address] != 0:
        for idx in range(len(hash_table[hash_address])):
            if hash_table[hash_address][idx][0] == ascii_sum:
                return hash_table[hash_address][idx][1]
        return None
    else:
        return None

def store_data(key, val):
    ascii_sum, hash_address = custom_hash_function(key)
    if hash_table[hash_address] != 0:
        for idx in range(len(hash_table[hash_address])):
            if hash_table[hash_address][idx][0] == ascii_sum:
                hash_table[hash_address][idx][1] = val
                return
        hash_table[hash_address].append([ascii_sum, val])
    else:
        hash_table[hash_address] = [[ascii_sum, val]]

name1 = 'choonsik'
name2 = 'lion'

store_data(name1, '배가고픔')
store_data(name2, '배부름')

print(get_data(name1)) # 배가고픔
print(get_data(name2)) # 배부름
print(hash_table) # [[[206, '배가고픔'], [218, '배부름']], 0, 0]

원래는 print된 결과를 보면 name1과 name2가 같은 주소를 가리켜 같은 결과를 출력했습니다.
현재는 나중에 들어온 name2가 가리키는 주소에서 결과를 기존것에 추가하여 붙임으로써 의도한 바 대로 동작합니다.

해결책2 (Linear Probing)

Key2와 Key3의 결과가 같은 주소 1을 가리킵니다.
나중에 들어온 Key3결과 같은 경우는 한칸 이동하여 빈칸인 2에 위치하게 합니다.

hash_table = list([0 for i in range(3)])

def custom_hash_function(val):
    ascii_sum = ord(val[0]) + ord(val[-1])
    return ascii_sum, ascii_sum % 2

def get_data(val):
    ascii_sum, hash_address = custom_hash_function(val)
    if hash_table[hash_address] != 0:
        for idx in range(hash_address, len(hash_table)):
            if hash_table[idx] == 0:
                return None
            elif hash_table[idx][0] == ascii_sum:
                return hash_table[idx][1]
        return None
    else:
        return None

def store_data(key, val):
    ascii_sum, hash_address = custom_hash_function(key)
    if hash_table[hash_address] != 0:
        for idx in range(hash_address, len(hash_table)):
            if hash_table[idx] == 0:
                hash_table[idx] = [ascii_sum, val]
                return
            elif hash_table[idx][0] == ascii_sum: # 수정
                hash_table[idx][1] = val
    else:
        hash_table[hash_address] = [ascii_sum, val]

name1 = 'choonsik'
name2 = 'lion'

store_data(name1, '배가고픔')
store_data(name2, '배부름')

print(get_data(name1)) # 배가고픔
print(get_data(name2)) # 배부름
print(hash_table) # [[206, '배가고픔'], [218, '배부름'], 0]