자료구조 1 Page 노트 정리_Hash Map 해시맵

Map

- key-value pair들을 저장하는 ADT
- 같은 key를 가지는 pair는 최대 한 개만 존재
- Map의 구현체: hash table, tree-based

Hash Table(Hash Map)

- 배열과 해시 함수를 사용하여 map을 구현한 자료구조
- 일반적으로 상수 시간으로 데이터에 접근하기 때문에 빠름
- 해시 함수: 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수, 해시테이블에서 임의의 데이터를 정수로 변환하는 함수
- hash tale resizing: 데이터가 많이 차게 되면 크기를 늘려줘야 함
- default initial capa: 16
- hash table capa: power of 2
- F(key) -> HashCode -> Index  -> Value

Hash Collision(해시 충돌)

- key값은 무한한 것에 비해 hash code는 정수로 한정되어 있기 때문에 충돌이 불가피함
- key는 다른데 hash가 같을 때 (different keys -> same code)
- key도 hash도 다른데 hash%map_capa 결과가 같을 때  (different code -> same index)
- 해결 방법: open addressing(linear probing, CPython), seperate chaining (자바)