자바(Java) Map의 동작원리

Map의 기본적인 내용은 이전에 정리했으니 동작 원리에 대해 정리한다.

Map은 내부적인 저장을 배열을 이용하여 저장한다.

Key를 해시함수에 적용하여 나온 값을 이용해 인덱스를 지정한다.

Map은 메모리를 절약하기 위해 처음부터 많은 공간을 차지하고 있지 않고 데이터가 일정이상 늘어나면 그때 배열의 크기를 2배로 늘리는 방식으로 진행한다.

Java에서 해시 버킷의 크기를 확장하는 임계점은 load factor * 현재의 해시 버킷 개수이며, load factor는 0.75이다. 즉 3/4를 넘어가면 확장하게 된다.

배열의 초기 사이즈는 2^4(16)개이며 최대 버킷의 개수는 2^30이다.

인덱스를 구할때는 해시값을 배열의 크기인 M으로 모듈러 연산을 해서 구하게 된다.

java의 경우 int를 사용하여 해시함수에서 나오는 값의 범위가 2^32 이기 때문에 X.hashCode() != Y.hashCode()가 되지 않으므로 완전한 해시 함수가 아니다.

해시값이 똑같이 나오거나 모듈러 연산을 통해 인덱스가 겹치는 상황이 발생할 수 있다. 이러한 문제를 해결하기 위해 해시충돌 회피기법중 Separate Chaning 방식을 이용한다.

Java 버전 8 이상부터는 하나의 해시 버킷에 8개 이상의 키-값 쌍이 모이면 링크드 리스트로 보관하던 것을 트리로 변경하여 저장한다. 이후 6개 이하로 내려간다면 링크드 리스트로 변경한다.

내부적으로 링크드 리스트 대신 트리를 사용할 수 있도록 Entry클래스 대신 Node 클래스를 이용한다.

여기서 사용하는 트리는 Red-Black Tree를 이용하고 있다.

트리 순회시 대소 판단 기준은 해시 함수의 값을 이용한다.

버킷의 개수가 2배로 증가할때마다 모든 키-값을 읽어 새로운 Separate Chaning을 구성해야 하는 문제가 발생한다. 따라서 데이터의 값을 예측할 수 있다면 HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정해 불필요한 재구성을 막을 수 있다.

모듈러 연산시 M이 소수여야 충돌이 적으나 버킷의 크기가 2^n 이기 때문에 충돌이 일어날 확률이 높다. 이를 해결하기 위해 보조 해시 함수를 이용한다.

 

출처 : https://d2.naver.com/helloworld/831311