(Java 소스 분석) HashMap

네이버 D2글 : http://d2.naver.com/helloworld/831311



* HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대으로 성능상 이점이 있다.

Java 8 HashMap에서의 Separate Chaining

Java2 부터 Java 7까지의 HashMap에서 Seperate Chanining 구현 코드는 조금씩 다르지만, 

구현 알고리즘 자체는 같았다. 만약 객체의 해시 함수 값이 균등 분포(uniform distribution)이라고 할 때, get()메소드에 대한 기대값은 

이다.  자바에서는 이보다 더 나은 

을 보장한다. 데이터의 개수가 많아지면, Seperate Chaning에서 링크드 리스트 대신 트리를 

사용하기 때문이다.

데이터의 개수가 많아지면과의 차이는 무시할 수 없다. 게다가 실제 해시 값은 균등 분포가 아닐뿐더러, 설사 균등 분포를 따른다고 하더라도 birthday problem이 설명하듯 일부 해시 버킷 몇 개에 데이터가 집중될 수 있다. 그래서 데이터의 개수가 일정 이상일 때에는 링크드 리스트 대신 트리를 사용하는 것이 성능상 이점이 있다.

링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다. 예제 5에서 보듯 Java 8 HashMap에서는 상수 형태로 기준을 정하고 있다. 즉 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경한다. 트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문이다. 8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.

Java 8 HashMap에서는 Entry 클래스 대신 Node 클래스를 사용한다. Node 클래스 자체는 사실상 Java 7의 Entry 클래스와 내용이 같지만, 링크드 리스트 대신 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 것이 Java 7 HashMap과 다르다.

이때 사용하는 트리는 Red-Black Tree인데, Java Collections Framework의 TreeMap과 구현이 거의 같다. 트리 순회 시 사용하는 대소 판단 기준은 해시 함수 값이다. 해시 값을 대소 판단 기준으로 사용하면 Total Ordering에 문제가 생기는데, Java 8 HashMap에서는 이를 tieBreakOrder() 메서드로 해결한다.

해시 버킷 동적 확장

해시 버킷 개수의 기본값은 16이고, 데이터의 개수가 임계점에 이를 때마다 해시 버킷 개수의 크기를 두배씩 증가 시킨다. 버킷의 최대 개수는 2^30개다. 그런데 이렇게 버킷 개수가 두배로 증가할 때마다 , 모든 키-값 데이터를 읽어 새로운 Seperate Chaining를 구성해야 하는 문제가 있다. HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Seperate Chaning을 재구성하지 않게 할 수 있다.

String 객체에 대한 해시 함수

String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례한다.

때문에 JDK 1.1에서는 String 객체에 대해서 빠르게 해시 함수를 수행하기 위해, 일정 간격의 문자에 대한 해시를 누적한 값을 문자열에 대한 해시 함수로 사용했다.

마치며

지금까지 설명한 내용을 요약하면, Java HashMap에서는 해시 충돌을 방지하기 위하여 Separate Chaining과 보조 해시 함수를 사용한다는 것, Java 8에서는 Separate Chaining에서 링크드 리스트 대신 트리를 사용하기도 한다는 것, 그리고 String 클래스의 hashCode() 메서드에서 31을 승수로 사용하는 이유는 성능 향상 도모를 위한 것이라고 정리할 수 있다.

HashMap은 첫 등장 이후, 성능 향상을 위하여 꾸준하게 개선되어 왔다. JDK 1.4에서 처음 등장한 보조 해시 함수와 Java 8의 트리 노드가 대표적인 예다.

그러나 Java 7의 일부 버전에서 사용했던 MurMur 해시처럼 성능 향상을 위하여 시도했던 것이, 결과적으로 좋지 않아 결국에는 삭제되기도 하고, 많은 해시 함수가 균등 분포 결과 값을 내도록 잘 작성됨에 따라 기존보다 더 단순한 형태의 보조 해시 함수를 사용하도록 변화하기도 했다.

웹 애플리케이션 서버의 경우에는 HTTPRequest가 생성될 때마다, 여러 개의 HashMap이 생성된다. 수많은 HashMap 객체가 1초도 안 되는 시간에 생성되고 또 GC(garbage collection) 대상이 된다. 컴퓨터 메모리 크기가 보편적으로 증가하게 됨에 따라, 메모리 중심적인 애플리케이션 제작도 늘었다. 따라서 갈수록 HashMap에 더 많은 데이터를 저장하고 있다고 할 수 있다.

Java 9, Java 10의 HashMap이 어떤 모습일지 지금은 알 수 없지만, 컴퓨팅 환경은 계속 변하고 그에 맞춰 HashMap 구현도 계속 변할 수밖에 없다는 것은 자명하다.