해쉬 테이블

Hash Table : 키(key)에 데이터(value)를 저장하는 구조

• Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
• 파이썬 딕셔너리 타입이 해쉬 테이블의 예시이다.
• 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용한다 (공간과 탐색 시간을 맞바꾸는 기법이다.

기본 예시

# 간단한 해쉬 함수를 만들기 (나무기를 통해 나머지 값을 사용하기)
def custom_hash_func(key):
    return key % 5


def storage_data(data, value):
    key = ord(data[0])
    hash_address = custom_hash_func(key)
    hash_table[hash_address] = value


def get_value(data):
    key = ord(data[0])
    hash_address = custom_hash_func(key)
    return hash_table[hash_address]


if __name__ == '__main__':
    hash_table = list([0 for i in range(10)])

    storage_data('Andy', '01012341234')
    storage_data('Dave', '01033332222')
    storage_data('Trump', '01055556666')

    print(hash_table)
    print(get_value('Andy'))

 

해시 테이블의 가장 큰 문제는 해시 충돌이다. 이것을 해결하는 방법은 아래와 같다.

• Chaining 기법
  • 개방 해싱 또는 Open Hashing 기법 중 하나이다. 
  • 충돌이 일어나면, 링크드 리스트를 사용하여 데이터를 추가로 뒤에 연결시켜 저장한다.

  • 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] = list([index_key, value])
        hash_table[hash_address] = 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
    
    
    if __name__ == "__main__":
        ## 해시 충돌 해결 해보기
        hash_table = list([0 for i in range(8)])
    

• Linear Probing 기법
  • 폐쇄 해슁 또는 Close Hashing 기법중 하나이다.
  • 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법

  • 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(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]
    
    
    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
    
    
    if __name__ == "__main__":
        ## 해시 충돌 해결 해보기
        hash_table = list([0 for i in range(8)])