해시 충돌(hash collision) 해결(1) - 링크드 리스트 사용

1. Chaining 기법
  - 개방 해싱(Open Hasing): 충돌시, 링크드 리스트를 이용해 데이터를 연쇄적으로 연결시켜 저장하는 기법

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

def get_key(data):
    return ord(data[0]) + ord(data[1]) 
           # address는 같아도 key값은 다르게 함

def hash_func(key):
    return key % 6

def save(data, value):
    index_key = get_key(data)
    address = hash_func(index_key)
    if hash_table[address] != 0: # 0이 아니면 주소에 data가 들어가 있다!
        for x in range(len(hash_table[address])):
            if hash_table[address][x][0] == index_key:
                hash_table[address][x][1] = value
                return
        hash_table[address].append([index_key, value])
    else:
        hash_table[address] = [[index_key, value]]

def value_of_(data):
    index_key = get_key(data)
    address = hash_func(index_key)
    if hash_table[address] != 0:
        for x in range(len(hash_table[address])):
            if hash_table[address][x][0] == index_key:
                return hash_table[address][x][1]
        return None
    else:
        return None

    return hash_table[address]

save('South Korea', 'Kimchi')
save('Turkey', 'Kebab')
save('United Kingdom', 'Roast Beef')
save('Sudan', 'Kamounia')

print(value_of_('South Korea')) # Kimchi
print(value_of_('Turkey')) # Kebab
print(value_of_('United Kingdom')) # Roast Beef
print(value_of_('Sudan')) # Kamounia(커민)

print(hash_table)
""" 
    [0, 
     0, 
     [[194, 'Kimchi'], [200, 'Kamounia']], # 링크드 리스트
     [[201, 'Kebab'], [195, 'Roast Beef']], # 링크드 리스트
     0, 
     0] 

"""

출처 : FASTCAMPUS