해시 테이블

1. 해시 구조

 Key에 Value를 저장하는 데이터 구조

 Hash Table size만큼의 배열로 생성해서 사용

 파이썬 Dictionary로 사용

2. 용어 정리

• Hash  : 임의 값을 고정 길이로 바꾸는 것
• Hash Table : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• Hashing function : Key로 데이터 위치를 찾을 수 있는 함수
• Hash Value : Key르 hashing function으로 연산해서 찾을 수 있는 값
• Slot : 한 개의 데이터를 저장할 수 있는 공간

출처  : 잔재미 코딩

 

Hash Table에 Value 저장하고 읽어보기

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

def get_data(data):
	key = ord(data[0])
    hash_addres = hash_func(key)
    return hash_table[hash_address]

 

3. 해쉬 언제 씀?

 - 검색이 많이 필요할 때

 - 저장, 삭제, 읽기를 많이 할 때

 - 중복 확인이 쉬운 캐쉬 구현할 때

 

 

충돌(Collision) 피하기

1. Chaning 기법 (충돌 생기면 linked list를 이용해서 추가로 데이터 연결)
2. Linear Probing 기법(Open Addressing 기법 중 하나)
3. Associative Array 기법 (Open Addressing 기법 중 하나)

자세한 코드는 잔재미코딩에서 이미 구현해 두었다.전체 보다 각 주요 코드만 가져와서 설명하겠다. 

 

1. Chaning 기법

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

def save_data(data, value):
	...
    
    #새로운 데이터의 주소가 가리키는 값이 이미 채워져 있다면
    if hash_table[hash_address] != 0:
    	# 같은 인덱스를 가진 곳을 찾아 순회
        for index in range(len(hash_table[hash_address])):
        	#충돌이 일어났던, 동일 키를 가진 슬롯에 연결리스트 구조로 [key, value]를 추가
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        # 가튼 인덱스를 가진건 아닌데 내가 가려는 곳이 어쨋든 0이 아니면 그 곳에 값을 추가
        hash_table[hash_address].append([index_key, value])
    #충돌이 일어나지 않았기 때문에 바로 그 자리에 key, value를 추가
    else:
        hash_table[hash_address] = [[index_key, value]]

 

빈번한 충돌을 개선하기 위해 해쉬 함수를 재정의해 저장공간이 확대된 해시 테이블에 값을 옮기는 기법을 간단하게 구현하면 

 

hash_table = list([None for i in range(16)])

def hash_function(key):
	return SHA-1

해시 함수 : SHA - 안전한 해시 알고리즘

어떠한 데이터도 유일한 고정된 크기의 고정값을 리턴해준다. 

 

 

시간 복잡도 

• collision에 따라 충돌이 없으면 O(1), 모든 데이터랑 충돌 일어나는 최악은 O(n)
• 16개의 배열에 데이터를 저장하고 검색하면 O(n)
• 16개의 데이터 저장공간을 가진 해시테이블에 데이터 저장하고 검색할 때 O(1)

 

결론

배열보다는 딕셔너리가 데이터 저장하고 검색하는 시간 복잡도가 훨 간단하다!

 

 

이 포스트는 파이썬과 컴퓨터 사이언스(자료구조): 대표적인 자료구조: 해쉬 테이블 - 잔재미코딩 (fun-coding.org) 와 파이선 알고리즘 인터뷰 책을 참고하여 만들었습니다!