HashMap과 HashTable

• Map이란 ‘키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array’를 부르는 용어 중 하나입니다. HashMap, HashTable도 이에 포함되며 다른 용어로는 Map, Dictionary, Symbol Table이 있습니다.
• HashMap은 보조 해시 함수(Additional Hash Function)를 사용하지만, HashTable은 보조 해시 함수를 사용하지 않습니다. 따라서 보조 함수를 통해 해시 충돌(hash collision)의 빈도를 낮출 수 있는 HashMap이 상대적으로 성능상 이점이 있습니다.

해시 분포와 해시 충돌

동일하지 않은 어떤 객체 X와 Y가 있을 때, 즉 X.equals(Y)가 '거짓'일 때 X.hashCode() != Y.hashCode()가 같지 않다면, 이때 사용하는 해시 함수는 완전한 해시 함수(perfect hash functions)라고 한다.

• *X.equals(Y)* 가 성립하지 않는 서로 다른 객체에 대해 hashcode() 의 결과값이 동일하지 않은 경우 이 때 사용되는 해시 함수를 우린 **완전한 해시 함수(perfact hash funcitons)**라고 합니다.
  • 역으로 객체의 동일성을 판단하기 위해선 equals, hashcode 모두 만족시켜야 한다는 의미입니다.
  • 서로 구별되는 객체의 종류가 적은 Boolean이나 Integer, Long, Double 같은 Number 값 객체는 값 자체를 해시 값으로 사용할 수 있어 완전한 해시 함수 대상이 됩니다.
  • 하지만 일반적으로 String이나 POJO(plain old java object)은 이를 표현하는 메모리의 크기보다 더 많은 수의 객체가 생성될 수 있기 때문에 논리적으로 완전한 해시 함수를 제작하는 것은 불가능합니다.
• 모든 HashMap 객체에서 검색의 시간 복잡도 $O(1)$를 만족하기 위해선 원소가 $2^{32}$인 배열을 모든 HashMap이 가져야 합니다.
  • 하지만 이는 사실상 공간 효율 측면에서 만족시키기 어렵기 때문에 메모리 절약을 위해 해시함수를 이용하는 associative array 구현체에서는 해시 함수의 표현 정수 범위보다 적은 M개의 원소 배열을 사용합니다.
  • int index = X.hashCode() % M; 공식을 통해 객체가 삽입될 버킷이 정해집니다.
    • 이는 hashcode() 함수가 얼마나 해시 충돌을 피할 수 있느냐와 다른 원소 공간에 따른 또 다른 종류의 해시 충돌입니다.
    • 이 경우 우리는 해시 충돌을 피할 수 있도록 2가지의 방법을 취합니다.
• 해시 충돌을 피해 키-값 쌍 데이터를 저장하는 방식에는 2가지가 있습니다. 버킷이 사용중인 경우 다른 해시 버킷을 사용하는 Open Addressing과 사용중이더라도 해당 버킷에 들어있는 자료구조에 값을 추가하는 Separate Chaining 입니다. Java HashMap은 Seperate Chaning을 사용합니다.
  • Open Addressing에서 버킷이 사용중인 경우 Linear Probing(n칸 옆을 검사하여 저장)이나 Quadratic Probing(n제곱 칸 옆을 검사하여 저장)을 통해 데이터를 저장합니다.
    • 충돌이 발생해 데이터를 다음 인덱스에 저장한 경우 조회는 일치하는 키가 나오거나 키가 없을 때까지 진행됩니다. 이 때문에 삭제가 발생할 경우 검색이 불가능한 케이스(데이터는 3번 인덱스에 존재하지만 2번 인덱스가 삭제되어 검색 중지)가 발생합니다. 이를 방지하기 위해 Dummy node를 삽입해 검색 프로세스가 연장되도록 만듭니다. 더미 노드가 일정 수를 넘어 너무 많아지는 경우 새로운 array를 만들어 hash를 리빌딩해줍니다. 이렇게 더미 노드를 주기적으로 제거해줘야 검색 성능이 유지됩니다.
    • 하지만 두 방법은 특정 영역에 데이터가 물리적으로 집중되는 단점이 있습니다. 따라서 이를 해결하기 위해 이중 해쉬 방법을 사용합니다.
  • 둘다 검색 시 Worst Case는 $O(M)$입니다. 또한 Open addressing은 고정 크기 배열을, Seperate Chaning은 버킷이 가득찬 경우 List의 길이가 늘어나기 때문에 resizing이 필요합니다.
  • Open Addressing은 버킷의 크기 자체를 늘리기 때문에 캐싱 적중률이 높습니다. 따라서 데이터의 크기가 작을 때는 Seperate Chaning보다 성능 상 이점이 있습니다. 하지만 배열이 커질 경우 캐싱 적중률이 떨어지고 삭제의 효율이 좋지 않습니다.
    • 하지만 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느립니다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문입니다.
    • 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있습니다. 자바에서는 이를 보조 해시 함수를 통해 해결합니다.

Java 8 HashMap에서의 Separate Chaining

• 동일 index에 대해서 데이타를 저장하는 자료 구조는 Linked List 뿐 아니라, Tree를 이용하여 저장함으로써, select의 성능을 높일 수 있다. 실제로, JDK 1.8의 경우에는 index에 노드가 8개 이하(static final int UNTREEIFY_THRESHOLD = 6;)일 경우에는 Linked List를 사용하며, 8개 이상(static final int TREEIFY_THRESHOLD = 8;)으로 늘어날때는 Tree 구조로 데이타 저장 구조를 바꾸도록 되어 있다.

  

  • Java 8에서는 기존 Entry 클래스 대신 Node 클래스를 사용합니다. 내부적으로 Node는 링크드 리스트 대신 트리를 사용하도록 TreeNode 클래스를 갖고 있습니다.
  • 트리 순회 시 사용하는 대소 판단 기준은 해시 함수 값입니다. 이 때 해시값은 해시 충돌에 있어서 같아질 수 있어 Total Ordering에 문제가 생깁니다. 따라서 Java 8 HashMap에서는 이를 tieBreakOrder() 메서드로 해결합니다.

해시 버킷 동적 확장

• Hashmap의 기본 버킷 사이즈는 16($2^4$), 최대 크기는 1,073,741,824($2^{30}$)입니다. 이 상태에서 버킷 사이즈가 늘어나지 않는다면 메모리를 아낄 수 있겠지만 이는 하나의 버킷에 저장되는 데이터가 증가해 성능이 감소하는 역풍이 생깁니다.
  • HashMap에서는 버킷 크기를 oldCap << 1 연산을 통해 2배로 증가시킵니다.
    • 버킷 크기를 늘리는 기준은 현재 데이터 개수가 load factor * 현재 해시 버킷 개수보다 많을 때입니다.
    • 사이즈를 늘릴 때 모든 버킷의 모든 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는데 이는 성능 손실로 이어집니다. 따라서 저장될 데이터 크기를 예측해 초기 해시 버킷 개수를 지정하면 불필요한 Separate Chaining을 방지할 수 있습니다.
  • HashMap.java 237라인의 static final int *DEFAULT_INITIAL_CAPACITY* = 1 << 4; // aka 16 , static final int *MAXIMUM_CAPACITY* = 1 << 30; 구문을 통해 확인할 수 있습니다.
• 기본 생성자는 16개의 버킷 사이즈와 0.75의 로드 팩터값을 갖는데 이 때 데이터를 2배씩 증가시키게 되면 전체 버킷 수가 $2^M$로 수렴합니다. 이렇게 되면 해시 버킷의 개수 M이 $2^a$ 형태가 되기 때문에, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 됩니다.
  • 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.
  • 이 문제를 해결하기 위해 우린 보조 해시 함수를 사용합니다.

보조 해시 함수

• index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 가장 균등한 분포를 갖습니다. 아닌 경우라면 보조 해시 함수를 사용해 키의 해시 값을 변경해 해시 충돌 가능성을 낮춥니다.
  • JDK 1.4부터 등장했으며 java 7과 8버전에서 상이합니다.
    • Java 8부터는 해시 함수의 성능이 좋아 조금 덜 복잡한 해시 함수를 사용합니다
• String 클래스의 해시 코드 성능을 높히기 위해 M 값을 31로 사용합니다
  • 31은 32N-N과 같습니다. 32N은 $2^{5}$*N과 같습니다. $2^{5}$은 << 5와 같으니 32N은 N << 5로 표현할 수 있고 결국 (N << 5) - N이 성립합니다.