해시 충돌(hash collision) 해결(2) - 해시테이블 저장 공간 사용

2. Linear Probing 기법
  - 폐쇄 해싱(Close Hashing): 충돌시, 해시테이블 저장 공간을 이용해 데이터를 연쇄적으로 연결시켜 저장하는 기법

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(address, len(hash_table)):
            if hash_table[x] == 0:
                hash_table[x] = [index_key, value]
                return
            elif hash_table[x][0] == index_key:
                hash_table[x][1] = value
                return
    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(address, len(hash_table)):
            if hash_table[x] == 0:
                return None
            elif hash_table[x][0] == index_key:
                return hash_table[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(value_of_('Denmark')) # None

print(hash_table)
""" 
    [0, 
     0, 
     [194, 'Kimchi'], 
     [201, 'Kebab'],
     [195, 'Roast Beef'],
     [200, 'Kamounia'],
    ] 

"""

출처 : FASTCAMPUS