HashMap의 동작 구조

자, HashMap의 동작 구조에 대해 알아보자.

 

HashMap vs HashTable

둘다 Java의 API의 이름이다. 또한 둘다 Map 인터페이스를 구현하고 있기에 제공하는 기능은 전반적으로 비슷하다. 다만 HashMap은 지속적으로 개선중에 있다는 점과 보조 해시 함수를 사용해 충돌을 덜 발생시킨다는 점에서 성능적인 면에서 유리하다.

아무튼! 둘다, key에 대한 해시값을 이용해 값을 저장하고 조회하며 동적으로 크기가 변하는 배열이라고 할 수 있다.

 

 

해시 분포 , 해시 충돌

 

완전한 해시함수란?

X와 Y가 다를때, H(X)와 H(Y)의 값 다른 해시함수를 완전한 해시함수라고 한다. Boolean, Integer, Long, Double과 같은 객체는 완전한 해시함수 대상으로 삼을 수 있지만, String과 POJO에 대해 완전한 해시함수를 만드는 것은 불가능하다.

 

또한, HashCode는 기본적으로 32bit int 형을 반환하는데 빠른 연산을 위해선( O(1)을 위해선 ), 2^32의 결과를 저장하고 있어야되고 메모리..에 대한 문제가 생긴다. 따라서, 해시함수를 이용한 associative array에선 |N|보다 작은 M개의 원소가 있는 배열만 사용한다. 아무튼! 완전한 해시함수는 구현이 어렵다!

 

이를 위해선 해시값을 M개의 버킷으로 나누기 위한 다음 연산을 실행하는데 Open Addressing과 Seperate Chaining 두 가지 방법이 존재한다.

int index = X.hashoCode()%M;

 

 

Open Addressing: 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식

Separate Chaining: 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한다.

 

두 방법 모두 최악의 경우 O(M)의 시간 복잡도를 띄지만 차이가 있다.

Open Addressing은 연속된 공간에 데이터를 저장하기에 캐시효율 높아 데이터 개수가 적을때 유리하다. 하지만 데이터 개수가 많아질수록 찾기가.. 어렵고 삭제하기에도 비효율적이다.

 

따라서, Java HashMap에서 사용하는 방식은 Separate Chaining이다. Java에서 빈번하게 사용하는 메서드는 remove()메서드이고, 많은 데이터를 저장하는데 OpenAddressing 보다 빠르기 때문이다.

 

앞서, HashMap은 지속적으로 개선되었다고 했다. Java8에선 보다 더 나은 효율성을 띈다.

만약 해시값이 균등하게 분포되어있을때 값을 찾는 get() 메서드를 실행하면 E(N/M)이었지만, java8은 E(log N/M)을 보장한다.

 

그 이유는 일정 개수이상의 데이터가 증가하면 링크드 리스트 대신 트리를 사용하기 때문이다.

java8에 8개의 키,값 쌍이 한 버킷에 모이면 링크드리스트 대신 트리를 사용한다. 만약 6개로 줄이면 다시 링크드리스트로 변환한다.

 

그 이유는 트리는 링크드리스트보다 메모리 사용량이 많은데 worst case에서의 효율이 비슷하기 때문이다.

 

java8 HashMap에선 Entry 클래스 대신 노드를 사용하며, Red-Black Tree를 사용한다. 트리를 순회할땐 해시값을 기준으로 하는데 이때 Total Ordering의 문제가 생겨 tieBreakOrder()를 사용한다.

 

해시 버킷 동적 확장

버킷에 값을 지속적으로 넣다보면, 해시 충돌이 발생해 성능상 문제가 생길 수 있다. 이때 버킷을 늘려 충돌을 피할 수 있다. 기본적으로 해시 버킷 개수의 기본값은 16인데 3/4지점의 임계점에 도달할때마다 버킷을 두 배로 확장해 최대 2^30까지 확장시킬 수 있다. 물론, 이렇게 버킷을 확장할때는 다시 키-값 쌍을 읽어 Separate Chaining을 해야한다. 이 또한 비용이 들고 따라서, HashMap 생성자의 인자로 초기 버킷 개수를 적절히 선정할 수 있다.

 

보조 해시 함수

해시 버킷을 확장해도 결국 %M 연산을 하게 되면 하위의 특정 비트만 활용한다. 32bit를 골고루 사용하기 위해 만들어진 해시가 제대로 동작하지 않고 결국 충돌이 일어날 것이다. 따라서 보조 해시함수가 등장했다.

자바 8 에서의 보조 해시함수는 상위 16비트 값을 XOR 연산하는 보조 해시함수를 사용한다. 비교적 단순하게 만들었는데 그 이유는 링크드 리스트 대신 트리의 사용으로 충돌 시 성능 문제가 줄었으며, 최근 해시 함수가 균등하게 분포를 잘내서 복잡한 구현이 필요없기 때문이다.

 

String에 대한 해시

String 객체에 대한 해시함수는 문자열 길이에 비례해 처리시간이 달라지는데 JDK1.1에선 빠른 해시함수 수행을 위해 일정 간격의 문자열에 대한 해시함수를 사용했다.

 

하지만, 이 방법은 길이가 긴 url에 대해 앞부분이 동일해 해시충돌이 일어나는등의 문제가 발생했다. 현재 java8 이후에는 Horner's Method를 구현해 다항식을 단항식으로 쪼개 재귀적으로 사용하고 있다.