[Python] Hash Table에 Linear Probing 기법 적용하기

학습내용

• Hash Table의 단점 중 하나인 충돌 문제를 Linear Probing 기법으로 해결하기
• 제한된 Hash Table의 저장공간 활용하기

🧨 저장공간 충돌을 막아주는 Linear Probing 기법

해쉬 테이블 자료구조를 사용하다 보면, 같은 주소값을 가진 데이터들로 인해 충돌문제가 발생하곤 합니다.
이때 Chaining 기법을 활용해서 저장공간 외의 공간을 활용할 수 도 있는 데요.
상황에 따라 한정된 저장 공간이 주어진 상황속에서는 Linear Probing 기법을 적용할 수 있습니다.

Linear Probing 기법은 '폐쇄 해싱' 또는 'Close Hashing' 기법 중 하나로,
충돌이 일어나면 해당 hash address의 다음 address부터 순회를 통해 빈공간을 찾아 저장합니다.
이 방법을 활용하면 Hahs Table의 공간을 좀 더 효율적으로 사용할 수 있습니다.

📌 해쉬 테이블 코드에 Linear Probing 기법 적용으로 충돌 예방하기

Hash 테이블 생성

• get_key : hash의 데이터를 구분하는 index key 값 생성
• hash_function : hash address(주소값) 생성

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

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

빈공간을 찾아 저장해주는 save_data

먼저, 받은 data와 value값을 통해 key값과 address를 생성합니다.
해쉬 테이블에서 해당 주소값에 데이터가 있는 지 확인하고 없다면, 새로 저장해줍니다.
만약, 데이터가 있다면 충돌을 방지하기 위해 해당 주소부터 순회를 돌며 데이터 유무와 key값을 검토 합니다.
데이터가 없다면 value를 저장해주고, 만약 데이터가 있는데 index_key값이 같다면 해당 주소의 value값을 덮어씌워 업데이트 해줍니다.

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(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

해당 주소 + index_key값을 비교하여 같다면 출력하는 read_data

전달받은 data를 기준으로 index_key값과 address를 생성합니다.
테이블의 데이터가 없다면 바로 None을 리턴하고,
데이터가 있다면 해당 주소값 부터 순회를 돌며 index가 0이면 리턴하고,
index값이 있다면 data의 index와 비교하여 일치하면 해당 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(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None