개요
Java의 대표 자료구조인 HashMap에 대해 간단하게 알아보자. HashMap이지만 핵심 메커니즘인 Hashing에 대해 조금 더 자세히 알아볼 것이다.
HashMap
- (key, value) 쌍으로 값을 이루는 자료구조
- 자료구조내 값을 검색하는데 유리하다.
- hash function으로 생성된 hashCode 값을 가진 buckets의 index에 (Node)의 key, value가 지정됨. 그러므로 key값으로 index를 계산하여 한번에 접근이 가능.(O(1))
buckets은 아래 이미지를 보면 뭔지 이해감.
HashMap Hierarchy
출처 : https://www.geeksforgeeks.org/java-util-hashmap-in-java-with-examples/
- HashMap implements Serializable, Cloneable, Map<K, V> interfaces.
HashMap, HashTable
- HashMap
- Non-thread-safe
- key에 null 허용
- 보조 해시 사용 (Collision 대비)
- HashTable
- Thread-safe
- key에 null 허용하지 않음
- 보조 해시 없음
Collision
- hash function에 의한 index 값이 중복 될 가능성이 있다.
- HashMap 에선 buckets 사이즈를 기본 사이즈에서 두배씩 늘리는 과정을 진행하는데 일정 사이즈를 늘리고 그래도 중복되면 보조 해시를 사용. (간략하게 정리하자면 그렇다…)
기본적인 collision 해결법
- Separate chaining
- 쉽게 말해 중복되면 해당 인덱스에 linkedlist로 꼬리를 달아서 저장. 저장 용량 불리
![Separate chaining]()
- Java HashMap에서 사용하며 8 버전부터는 linkedlist 대신 tree를 사용.
- Open addressing
- 중복이면 다음 index에 추가. 해당 index에 값이 있으면 그 값도 한칸 밀어버림.
![Open addressing]()
이미지 출처 : https://en.wikipedia.org/wiki/Hash_table
마무리
깊이 들어갈 필요는 없다고 생각한다. Hashing 알고리즘에 대해 어느정도 이해만 하고 넘어가면 필요할 때 찾아보면 더 쉽게 이해 가능할 듯.