자료구조 (해쉬테이블 2) 충돌 해결 알고리즘

해쉬 테이블의 가장 큰 문제는 충돌 이를 해쉬충돌이라고 한다.

 

Chaining기법

개방 해싱, 오픈 해싱 기법 

-해쉬 테이블 저장공간 외의 공간을 활용한다.

-충돌이 일어나면 링크드 리스트라는 자료구조 사용해 충돌에 대응한다.

 

Linear Probing 기법

폐쇄 해싱 또는 클로즈 해싱 기법

-해쉬 테이블 저장공간 내의 공간을 활용한다.

-충돌이 일어나면 해당 해시 값의 다음 값부터 맨 처음 나오는 빈공간에 저장한다.

 

위와 같이 크게 두 가지 전략으로 충돌에 대해 대처한다.

 

우선 오픈 해싱 기법에 대해 구체적으로 알아보자

 

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:  # 기본 값이 0이고 값이 채워진 값이 0이 아니라는 전제 
    	for index in range(len(hash_table[hash_address])):
        	if hash_table[hash_address][index][0] == index_key:
            	hash_table[hash_address][index][i] = value
                return
        hash_table[table_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][index][0] == index_key:
        	return hash_table[hash_address][index][1]
        return None
    else:
    	return None

save_data('Dd', '156151565')
save_data('Data', '45645456')
print(read_data('Dd'))
print(hash_table)

 

 

특이점

hash_table 의 list 2차 배열을 사용함

따라서 index_key를 별로 구하여

해당 hash_address 안에서 index_key로 구분하여

값을 저장하고 조회하는 데 사용한다.

 

즉 단순 해쉬테이블과 달리 충돌을 피하기 위해서

배열 안에 또 다시 배열을 만들어 해쉬 address가 충돌되는 경우에 key 값으로 구분한다.