알고리즘/자료구조 - Hash Table(해쉬 테이블)

 

해쉬 테이블

Hash Table은 Key(키)에 Value(데이터)를 저장하는 자료 구조

파이썬에서는 { "key" : "Value" }형식으로 나타내면 된다. 

검색이 많이 필요한 경우, 저장/읽기/삭제가 많을 경우, 캐쉬 구현시(중복 확인이 쉽기 때문) 해쉬 테이블을 많이 사용함

 

장/단점

장점

데이터의 저장과 읽는 속도가 빠름(검색속도 Fast!)

키에 대한 중복된 데이터가 존재하는지 쉽게 확인 가능

단점

저장 공간이 다른 자료구조에 비해 더 많이 필요함

여러 키에 해당하는 주소가 동일하게 된다면 충돌이 일어나기에 충돌을 해결할 자료구조가 필요함

 

해쉬테이블 용어 

해쉬(Hash) - 임의로 설정한 값을 고정된 길이로 변환 시키는 것 

해쉬 테이블(Hash Talbe) - 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 

해싱 함수(Hashing Function) - Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 

해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address) - Key를 해싱 함수로 연산해서 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음 

슬롯(Slot) - 한 개의 데이터를 저장할 수 있는 공간 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음

시간 복잡도

일반적인 경우 = O(1)

최악의 경우 = O(N)

 

해쉬 테이블 만들기

hash = list([i for i in range(10)])
print(hash) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

data = [1, 49, "디반", 31.43, True, 10]
int_data = [num for num in data if type(num)==int]

print(int_data)
#[1,49,10]