HashMap과 해시 충돌

HashMap과 HashTable 관계

• HashTable
  • JDK 1.0부터 있던 Java의 API
  • Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable이 제공하는 기능은 같다.
  • JDK 버전에 따른 구현에 거의 변화가 없다.
• HashMap
  • Java 2에서 처음 선보인 Java Collections Framework에 속한 API
  • 보조 해시 함수(Additional Hash Function) (~> hashCode) 를 사용
    • 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있음
  • JDK 버전에 따라 지속적으로 개선되고 있다.
• HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기 때문에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다. (HashMap을 사용하자)

HashMap

• 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array
  • associate array의 다른 이름으로는 Map, Dictionary, Symbol Table이 있다.
  • HashTable에서는 Dictionary라는 이름을 사용하고, HashMap에서는 그 명칭이 그대로 말하듯이 Map이라는 용어를 사용
• bucketSize를 가지고 key를 저장하는 배열, value를 저장하는 배열로 구성이 된다.
• 저장되는 key값을 hash 알고리즘을 통해서 작은 범위의 값들로 바꿔서 이용하는 것이 HashMap이다.

해시 분포와 해시 충돌

• 해시 분포
  • 서로 다른 객체 X와 Y가 존재할 때(X.equals(Y) == false) ~> X.hashCode() != Y.hashCode() 라면, 이 때 사용하는 해시 함수는 완전한 해시 함수(perfect hash fucntions)라고 함
  • 완전한 해시 함수의 대상
    • Boolean과 같이 구별되는 객체 종류가 적거나, Number와 관련된 객체는 값 자체를 해시 값으로 사용할 수 있는 객체
    • String이나 POJO(plain old java object)는 사실상 불가능
  • 적은 연산으로 빠르게 동작하는 완전한 해시 함수가 있다해도, HashMap에 바로 적용할 수 없다.
    • HashMap은 기본적으로 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는 데, 결과 자료형은 int
    • 32 비트 정수형으로는 완전한 해시 함수를 만들기 힘들다.
      • 논리적으로 생성 가능한 객체의 수가 2^32 보다 많을 수 있고 접근에 대해 O(1)을 보장해야 하는데, 랜덤 접근이 가능하게 하려면 원소가 2^32인 배열을 모든 HashMap이 가지고 있어야 하기 때문
    • 따라서, 해시 함수를 이용하는 associative array 구현체에서는 메모리를 절약하기 위해 실제 해시 함수의 표현 정수 범위보다 작은 원소(M개)의 배열만 사용한다.
      •  
      • int index = X.hashCode() % M;
• 해시 충돌
  • hashing된 값의 인덱스가 서로 같은 경우 key값이 중복되는데, 이를 해시 충돌이라 한다.
  • 해결 방법
    • Open Addressing (개방 주소 방법)
      • 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식
      • 해시 테이블 내의 새로운 주소를 탐사(Probe)하여 데이터를 입력
      • Linear Probing(선형 탐사)
        • 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동(+1)
        • Cluster(클러스터) 현상 발생
      • Quadratic Probing(제곱 탐사)
        • 선형 탐사가 고정폭만큼 이동하는데 비해 제곱 탐사는 이동폭이 제곱수로 늘어남
        • 서로 다른 해시 값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않도록 하는 효과가 어느 정도 있지만, 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 발생
      • Double Hashing(이중 해싱)
        • 클러스터 방지를 위해 2개의 해시 함수를 사용
        • 하나는 최초의 주소를 얻을 때 사용
        • 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용
      • Rehashing(재해싱)
        • 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것
    • Separate Chaining (분리 연결 방법)
      • 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분(head)
  • 위의 두 방법 모두, Worst Case O(M)
    • Open Addressing은 연속된 공간에 데이터를 저장 ~> 캐시 효율이 높음
      • 데이터 개수가 충분히 적다면 성능이 더 좋다.
      • 배열의 크기가 커질수록(M이 증가할수록) 캐시 효율성이 사라짐
    • 자바에서는 Separate Chaning을 사용함
      • Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문
      • 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리기 때문
      • Open Addressing은 해시 버킷의 밀도가 높을수록 Worst Case 발생 빈도가 높아지는 반면, Separate Chaning 방식은 해시 충돌이 잘 발생하지 않도록 조정할 수 있으면 Worst Case를 최대한 방지할 수 있음
• Java 8 HashMap 에서의 Separate Chaining
  • Java 2~7까지의 알고리즘은 같았음
    • 객체의 해시 함수 값이 균등 분포 상태면, get() 호출에 대한 기댓값은
  • Java 8에서는
    • Java 8의 Separate Chaining은 데이터 개수가 일정 이상으로 증가하면 LinkedList 대신 Tree를 사용하기 때문
    • LinkedList를 사용할지 Tree를 사용할지 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수
    • Entry 클래스 대신 Node 클래스를 사용 <- Java 7과 차이점
    • 여기서 사용하는 트리는 Red-Black Tree이며, Java Collections의 TreeMap과 구현이 거의 같음
    • 트리 순회 시 대소 판단 기준은 해시 함수 값인데, Total Ordering에 문제가 생긴다.
      • Total Ordering => 임의의 두 원소를 비교할 수 있는 부분 순서 집합이다
    • 그래서 Java8의 HashMap에서는 tieBreakOrder() 메소드를 사용해서 해결하고 있음

해시 버킷 동적 확장

• 해시 버킷의 개수가 적으면 메모리를 아낄 수 있지만, 해시 충돌의 성능 손실이 발생
• HashMap은 Key-Value 데이터 개수가 일정 이상 되면, 해시 버킷을 두배로 늘린다.
  • 버킷 개수를 늘리면 N / M으로 값이 작아져서 해시 충돌로 인한 성능 손실을 어느정도 해결
  • 하지만 버킷 개수를 두 배로 증가시키면, 모든 Key-Value를 읽어서 새로운 Separate Chaning을 해줘야는 문제 발생
  • HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있기 때문에, 해당 HashMap 객체에 저장될 데이터의 개수가 대략 예상이 가능하다면 생성자의 인자로 지정해서 불필요한 재구성을 회피할 수 있음

String 객체에 대한 해시 함수

•    public int hashCode() {
      int h = hash;
      if (h == 0 && value.length > 0) {
          char val[] = value;
  
          for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
  }

  • 31을 사용하는 이유는, 31이 소수이며 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문
  • 31N == 32N-N, 32 == 2^5 ~> 어떤 수에 대한 32를 곱한 값은 shift 연산으로 쉽게 구현

Reference

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

https://wodonggun.github.io/wodonggun.github.io/algorithm/%ED%95%B4%EC%8B%9C-%EC%A0%95%EB%A6%AC.html

https://ko.wikipedia.org/wiki/%EC%A0%84%EC%88%9C%EC%84%9C_%EC%A7%91%ED%95%A9