[Java] HashMap

Java 에서 HashMap은 key-value 값으로 이루어져 있고, key를 사용하여, value 값을 얻어낸다.

Key는 중복을 허용하지 않고, Value는 중복을 허용한다.

 

HashMap의 내부구조는 배열로 되어있고, Key는 직접 내부의 인덱스가 될 수 있으며 이를 버킷이라고 한다.

인덱스를 구하기 위해서는, 해시함수를 사용하는데 Hashcode % M 으로 산출할 수 있으나,

동일한 key값이 발생할 수 있고, 이를 해시 충돌이라고 한다.

이를 방지하기 위해서는 Open Addressing 방식과 Separate Chaning 방식이 있고, 해시 맵은 후자를 사용한다.

Separate Chaning(동일한 해시값이 있을 경우, LinkedList로 관리하고, 8개 이상인 경우 Tree로 변경하여 관리한다.)

 

해시 버킷이 적다면, 메모리절약은 되지만 해시 충돌가능성이 높아진다.

따라서 특정값을 넘는다면, 해시버킷을 2배로 확장한다.

해시함수를 구할떄 Java의 경우 int로 되어있어 해시 충돌 빈도가 높고 이를 해결하기 위해 보조 해시 함수를 사용한다.

 

해시충돌 발생시, 다음 노드로 해당 값을 저장한다.

해시값은 해시함수를 통한 값이다. 따라서, 노드의 값들은 다 달라도, 해시함수를 통한 결과값이 같은 경우에 이렇게

노드로 붙인다.

 

Java8 에서는 더 향상된 방법을 쓴다.

링크드 리스트의 개수가 8개가 모이면, 트리로 변경한다. 만약 6개에이르면 다시 링크드리스트로 변경한다.

트리 특성상 순휘시 사용하는 판단 기준이 대소에 대한 구분이 있어야 한다.

이는 레드블랙 트리라는 것을 적용하였다고 한다.