[자료구조] 해시테이블(Hash Table)이란?

 

해시테이블의 필요성을 이해하기 위해 먼저 상반되는 개념인 Direct-adress Table를 알아보자!

 

Direct-adress Table?

키 값이 인덱스가 되는 테이블

ex) list 자료구조에서 student[0] = "김구글" 입력 시 0번 index에 바로 저장. 즉, key 값이 index가 됌

 

Direct-adress의 단점?

1) 내가 원하는 인덱스가 만일 2022일 경우, 해당 값 이전 인덱스 0~2021 의 메모리가 생성되어야하므로 메모리 낭비가 심함

2) 만일 index가 문자열로 들어올 경우 처리가 불가

hash 테이블의 필요성 대두!

 

 

Hash Table?

저장, 삭제, 검색의 시간복잡도 모두 O(1)인 빠른 탐색을 위한 자료구조.

key-value 데이터를 입력받고 해당 데이터 쌍을 저장한다.

 

index	key	value
0	20220100	김구글
1	20200046	윤애플
2
3
4	20181389	강다음

key-value쌍을 저장해야하기 때문에 결국 리스트를 저장하는 것이므로 인덱스 지정이 필요하다. 

인덱스 지정하는 방법은 hashfunction에 넣고 리턴 된 값을 index로 갖는다.

 

hashfunction 예시

def hash_function(key):
	return key % 5
    
# 20220100 return값 -> 0 (인덱스 0번에 저장)
# 20200046 return값 -> 1 (인덱스 1번에 저장)
# 20181389 return값 -> 4 (인덱스 4번에 저장)

 

만약 문자열을 key입력으로 받게된다면 아래와 같은 hashfunction으로 가공을 거치면 된다

def hash_function(key):
	return stringToInteger(key) % 5

 

해시테이블의 Collision(충돌) 문제

만약 key가 20200002 와 20200004를 입력받게 되면 해당 index는 모두 0이 되는데,
인덱스 0에 이미 데이터가 저장되어 있을 경우 인덱스 충돌이 일어나 저장을 할 수 없게된다

 

Collision 해결방법 

* OpenAdressing 방법을 사용한다

OpenAdressing
:해시테이블에서 인덱스 충돌이 날 경우 다음 index에 저장하는 방법 

파이썬에서는 hash Table이 Dictionary 라는 자료 구조형으로 정의되어 있다. 

 

↓ ↓ ↓  Dictionary에 대해 알고 싶다면 여기로!  ↓ ↓ ↓ 

 

https://2days.tistory.com/57

[자료구조] 딕셔너리(Dictionary)란?