[자료구조] 해시 테이블(Hash Table) - Linear Probling 기법

Linear Probling 기법

• Close Hashing 기법 중 하나, 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면 해당 hash address의 다음 address부터 맨처음에 나오는 빈공간에 저장하는 기법

https://en.wikipedia.org/wiki/Linear_probing

 

Linear Probling 기법 구현

hash_table = list([0 for i in range(10)]) # 0부터 9까지의 리스트를 0으로 초기화

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 10

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                 # 해시 주소값 안의 key값과 index_key값이 동일하면 데이터를 수정
                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:
        for index in range(hash_address, len(hash_table)):  # 해시 주소값 부터 테이블 끝까지 반복문을 돌며
            if hash_table[index] == 0:                      # 해시 주소안의 키 값이 index_key와 동일한지 찾고
                return None                                 # 동일하다면 해당 value값을 반환
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None