해시테이블(Hash Table) 3

https://zuha.tistory.com/entry/해시테이블HashTable2

해시테이블(Hash Table) 2

---

6. 충돌(Collision) 해결 알고리즘 (좋은 해시 함수 사용하기)

해시 테이블의 가장 큰 문제는 충돌(Collision)이 있는 것이다. 이러한 문제를 충돌(Collision) 또는 해시 충돌(Hash Collision)이라고 부른다.

 

6-1. Chaining 기법

- 개방 해싱 또는 Open Hashing 기법 중 하나 : 해시 테이블 저장 공간 외의 공간을 활용하는 기법

- 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서 링크드 리스트로 데이터를 추가하여 뒤에 연결시켜서 저장하는 기법이다.

 

연습 2 : 연습 1의 해시 테이블 코드에 Chaining 기법으로 충돌 해결 코드를 추가해보기

1. 해시 함수 : key % 8

2. 해시 키 생성 : hash(data)

hash_table = list([0 for in range(8)])

def get_key(data):
    return hash(data)
    
def hash_function(key):
    return key % 8
    
def save_data(data,value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address]!=0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key, value])
    else:
        hash_table[hash_address] = [[index_key, value]]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address]!=0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None
    else:
        return None

print(hash('Dave')%8)
print(hash('Dd')%8)
print(hash('Data')%8)

save_data('Dave','1201023010')
save_data('David','3301023010')
read_data('Dd')

hash_table