Map은 Key와 Value의 쌍으로 데이터를 저장하는 방식을 말한다.
HashMap은 Hash Table을 기반으로 구현한 Map이다.
1. 주요 용어 및 기능
Hash Function
임의의 데이터를 정수로 변환하는 함수
해시 알고리즘을 통해 결과를 반환
Bucket(Slot)
HashTable의 각각의 공간을 의미
Key와 Value, Hash 값이 저장되며, 충돌 해결 방식에 따라 LinkedList와 같이 다음 노드의 주소 포인터가 저장될 수 있다.
Capacity
HashTable의 크기
2. 동작 방식
Key와 Value가 주어졌을 때, Key를 Hash Function에 넣어 나온 정수 값을 Capacity로 모듈러 연산을 진행하여 나온 값의 위치로 Key와 Value를 저장한다.
3. Hash 충돌
간혹 서로 다른 Key 값의 해시 값이 중복되는 충돌이 일어날 수 있다.
이 경우 충돌을 해결해줘야 하는데 방법은 다음과 같다.
1. Separate Chaining
Bucket을 LinkedList 또는 레드 블랙 트리를 같이 혼용하여 다음 노드에 중복되는 key 데이터를 저장하는 방식
2. Open Addressing
중복이 일어난 Bucket을 기준으로 다음 Bucket들을 순회하며 빈 Bucket에 중복되는 Key 데이터를 저장하는 방식
해당 방식을 사용하는 경우, HashMap의 삭제 연산 시 삭제 된 Bucket에 더미 데이터를 넣어 해당 Bucket이 삭제되었음을 명시해줘야 한다.
중복으로 다른 Bucket에 저장 된 데이터를 찾기 위함
4. HashTable Resizing
일정량 이상의 Capacity를 사용하면 Bucket 사이즈를 늘려줘야 한다.
이를 HashTable Resizing이라 한다.
Key를 통해 HashFunction에서 나온 해쉬 값을 Bucket에 같이 저장해두는데, 이를 통해 저장 된 Hash 값에 늘어난 HashTable의 Capicity로 모듈러 연산을 하여 데이터를 다시 저장하는 과정을 거친다.
Java의 기본 Capacity는 16 Capacity의 3/4를 사용하면 자동으로 2배로 늘려준다.