[자료구조] 해쉬 테이블 (Hash Table) - 2

충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용)

- 해쉬 테이블에서 가장 큰 문제는 충돌(Collision)의 경우이다.

 

① Chaining 기법

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

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

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:
        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)

2
0
1

save_data('Dd', '1201023010')
save_data('Data', '3301023010')
read_data('Dd')

'1201023010'

hash_table

[[[-7654392602558696976, '1201023010']],
 [[-9146221194023993367, '3301023010']],
 0,
 0,
 0,
 0,
 0,
 0]

 

② Linear Probing 기법

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

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

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

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:
        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

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

3
5
2

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