Map, Hash table

Hash table (Hash map)

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

일반적으로 상수 시간으로 데이터에 접근하기 때문에 조회가 빠르다는 장점을 가지고 있습니다.

 

Hash function

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

아래의 그림을 참고 부탁드립니다.

 

Hash table은 어떻게 동작할까요?

 

hash collision

key는 다른데 hash가 같을때

ket도 hash도 다른데 hash % map_capacity 결과가 같을 때 

 

hash collision 해결 방법

- open addressing (linear probing)

    -> 비어있는 공간에 저장 -> 

- separate chaining

    -> linked list로 처리

 

hash table resizing 

전체 capacity의 75%가 차면 capacity를 2배로 늘려줌

 

 

https://devlog-wjdrbs96.tistory.com/253

[Java] HashMap vs Hashtable 차이는 무엇일까?

 

https://github.com/wjdrbs96/Today-I-Learn/blob/master/Java/Collection/Map/Java%20HashMap%20%EB%8F%99%EC%9E%91%EC%9B%90%EB%A6%AC.md

GitHub - wjdrbs96/Today-I-Learn: Today I Learned. 그날 그날 모든 활동들을 정리

 

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