해시테이블(Hash Table) 4

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

해시테이블(Hash Table) 3

---

6-1. Chaining 기법

해시 테이블 밖에 충돌이 일어났을 경우, 밖에 데이터를 저장할 수 있는 공간을 링크드 리스트로 만든 것.

 

6-2. Linear Probing 기법 (가장 많이 언급되는 기법)

해시 테이블 안에 충돌이 일어났을 경우, 안에 빈 공간에 충돌된 데이터를 저장하는 기법

- 폐쇄 해싱 또는 Close Hashing 기법 중 하나 : 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

- 충돌이 일어나면, 해당 Hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법

( 저장공간 활용도를 높이기 위한 기법 )

빈 공간이 최초로 나타나는 시점의 주소에 데이터를 저장.

- 장점 : 해시 테이블의 빈 공간을 충돌된 데이터로 채움 -> 저장공간의 활용도를 높일 수 있다.

Linear Probing 기법

 

연습 3 : 이전 포스팅에 있는 해시 테이블 코드에 Linear Probing 기법으로 충돌 해결 코드를 추가해보기

1. 해시 함수 : key % 8

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

hash_table = list([0 for i 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:
        # hash_address는 인덱스번호. 주소 공간은 0번부터 시작해서 1씩 증가하면서 다른 주소 공간을 가리킬 수 있다.
        for index in range(hash_address, len(hash_table)): 
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            # 데이터의 주소의 index_key가 동일한 index_key라고 한다면
            elif hash_table[index][0] == index_key:
                # hash_table에 index에 있는 1번은 value 값을 저장
                hash_table[index][1] = value
                return
    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:
        # hash_address 위에서부터 순회
        for index in range(hash_address, len(hash_table)):
            # 데이터가 저장이 되어있지 않은 빈공간이면 None을 return
            if hash_table[index] == 0:
                return None
            # 내가 원하는 key 라면 해당 데이터를 return
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

 

Linear Probing 기법은 테이블 해당 주소에 저장이 되어있을 때 해당 key 값을 가지고 판단한다.

충돌이 일어날 경우 동일한 주소에 해당하는 데이터라 할지라도 그다음 빈 슬롯에 저장을 하게 되고

데이터를 찾을 때에도 데이터가 있다고 해서 바로 꺼내오는 것이 아니라

key 값을 확인하고 key 값이 맞을 때까지, 빈 슬롯이 나타날 때까지 데이터를 계속 순회한다.

빈 슬롯이 나타난다는 것은 데이터가 저장된 적이 없다는 것이기 때문에 해당 데이터가 저장되지 않았음을 return 한다.

key 값이 매칭이 되는 곳을 찾게 되면 해당 데이터를 return 하게 된다.

 

print(hash('dk') % 8)
print(hash('da') % 8)
print(hash('dc') % 8)

save_data('dk', '01200123123')
save_data('da', '3333333333')
read_data('dc')