Map과 Hash Table

Hash Table (Hash map)

배열과 해시 함수 (Hash function)을 사용하여 map을 구현한 자료 구조

일반적으로 상수 시간으로 데이터에 접근하기 때문에 빠름

 

 

Hash function이란?

임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수

(hash table에서) 임의의 데이터를 정수로 변환하는 함수

hash function의 output은 hash라고 부름

 

Hash table은 어떻게 동작하는가?

 

hash collision

key는 다른데 hash가 같을 때

key도 hash도 다른데 hash% map_capa 결과가 같을 때

hash function에서 hash collision은 필연적임

최대한 hash가 큰 범위에서 계산이 되게끔 해야함

 

 

Hash collision 해결 방법

1) open addressing

 

 

 

 

 

 

 

 

 

2) separate chaining

 

 

 

 

 

 

참고

https://www.youtube.com/watch?v=ZBu_slSH5Sk