자바의 HashMap에 대해

5 분 소요

업데이트:


Map의 필요성

  • 일반적으로 List내의 데이터 조회 성능은 O(N).
  • 만약, List 내의 데이터들이 정렬돼있다면!
    • binary search를 통해 O(logN)의 조회 가능.
  • 물론 O(logN)도 뛰어난 시간복잡도 이지만…
  • 저장된 데이터 수에 상관없이 상수시간의 시간복잡도로 데이터를 조회할 수는 없을까?? 라는 고민이 생길 것이다.
  • 이러한 고민을 해결해 줄 수 있는 자료구조가 바로 Map 이다.


HashMap이란?

  • HashMap은 Java Collection Framework에 속한 구현체 클래스.
  • HashMap은 key, value로 이루어진 특수한 자료구조이다.
    • key를 이용해 value값을 조회한다.
  • key에 대한 해시 값을 이용해 값을 저장하고 조회한다.


HashMap의 특징

  • 하나의 HashMap에서 key는 중복을 허용하지 않고, value는 중복을 허용한다.
  • HashMap은 key, value에 모두 null 값을 할당 할 수 있다.
  • HashMap은 데이터 저장에 있어 순서를 보장하지 않는다.
  • key, value 모두에 primitive type을 허용하지 않는다.
    • wrapper class를 이용하면, 숫자 타입의 key, value 저장 가능.
  • HashMap은 멀티쓰레드 환경에서 쓰레드 세이프를 보장하지 않는다.
  • 동적으로 크키가 증가한다.


HashMap과 HashTable

  • HashTable 또한 Map 인터페이스를 구현하고 있기 때문에, HashMap과 HashTable이 제공하는 기능은 같다.
    • 다만, HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비해 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
  • HaspTable은 get()이나 put() 같은 주요 메서드에 synchronized 키워드가 붙어있어, 쓰레드 세이프를 보장한다.
  • 반면, HashMap은 쓰레드 세이프를 보장하지 않는다.
  • HashTable의 구현은 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있다.


HashMap 내부 동작구조

hashCode()

  • Java의 최상위 객체인 Object에는 기본적으로 hashcode()가 정의돼있다.
    • 즉, 모든 객체는 hashCode()를 갖는다.
    • hashCode()는 객체를 식별할 수 있는 식별값이다.
  • HashMap의 key로 저장할 객체는 hashCode()를 재정의하고, key 객체에서 재정의된 hashCode()는 해당 key에 대한 해시값을 얻는데 사용된다.
    • 즉, hashCode()는 hash 함수로 사용되는 것이다.
  • hashCode()의 반환타입은 int이며, 총 32bit 정수 자료형으로 나타낼 수 있다.
  • 내부적으로 값을 저장하기 위한 배열을 가지며, 이 배열을 가리켜 해시 버킷이라고 부른다.

hash 충돌

  • hashCode()의 범위는 2^32 지만, 모든 HashMap마다 2^32 만큼의 버킷을 가지고 있으려면 많은 메모리가 요구될 것이다.

  • 그렇기 때문에, HashMap은 내부적으로 2^32 보다는 작은, 크기 M 만큼의 버킷을 갖고 있으며, 아래와 같은 식을 통해 버킷에 대한 인덱스를 구한다.

      int index = key.hashCode() % M;
  • 이럴 경우, 서로 다른 hash 값을 갖는 객체라 할지라도 1 / M 확률로 충돌이 발생한다.
    • 이러한 현상을, hash 충돌이라고 부른다.
    • 이렇게 충돌이 발생하면, 완벽한 O(1)의 저장 및 조회 성능을 보장할 수 없다.

      Q. 만약, 모든 객체의 hashCode()가 0을 반환하도록 재정의 돼있으면 어떻게 될까?

      • 모든 객체의 해시값이 0이되어, HashMap에 저장하고자하는 모든 객체에 대해 충돌이 발생할 것.
      • 즉, HashMap이 마치 리스트처럼 동작할 것이다.

hash 충돌 해결방법

  • 그렇다면 hash 충돌 현상을 어떻게 해결할 수 있을까?
  • 대표적으로, 다음과 같은 방법들이 있다.
  • Open Addressing
    • linear probing
    • Open Addressing은 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다.

    • 배열의 크기가 작을수록 유리한 방식.

  • Separate Chaining
    • 충돌 시 해시 버킷 인덱스에 링크드 리스트를 이용해서 여러 value를 연결한 형태로 저장하는 방식.
    • Java의 HashMap에서 사용하는 hash 충돌 해결 방법

    • 배열의 크기가 크면 클수록 유리한 방식.

    • Java 7까지는 Separate Chaining을 구현하기 위해 링크드 리스트를 사용했다.
    • Java 8부터는 Separate Chaining을 구현하기 위해 링크드 리스트 혹은 트리를 사용한다.
      • 트리를 사용하는 이유는 성능상의 이점을 얻기 위해서이다.

        Q. 그럼 무조건 트리를 사용하지 왜 링크드 리스트를 혼합해서 사용하나?

        • 일반적으로, 트리는 링크드 리스트보다 메모리를 많이 사용하는 자료구조이다.
        • 즉, 트리와 링크드 리스트 사이에는 메모리 공간과 성능 사이에 trade-off가 발생한다.
        • 만약, HashMap에 저장할 데이터가 적은 상황이라면, 트리나 리스트간의 성능비교는 큰 의미가 없기 때문에, 상대적으로 메모리를 적게 쓰는 링크드 리스트를 사용하는 것이 좋다.
        • 그렇지만, 저장할 데이터가 많을수록 성능상 트리가 유리할 것이다.
      • 링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다.
        • 즉, 하나의 배열 인덱스 내에 들어있는 데이터 개수가 기준이 됨.
      • 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다.
      • 아래와 같이 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다.

      • 또한, 데이터가 삭제되어 키-값 쌍이 6개가 되면 다시 트리를 링크드 리스트로 변경한다.

            static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;


해시 버킷 동적 확장

  • 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다.
  • 그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다.
    • 일정 개수에 대한 임계점은 HashMap의 load factor 값에 의해 결정된다.
  • 기본 해시 버킷 수는 16이고, 기본 load factor는 0.75f 이다.

    • 즉, 별다른 capacity와 load factor을 지정하지 않고, default로 HashMap을 생성하면 기본 해시 버킷의 크기는 16이고, 12만큼 차면 재해싱을 통해 해시 버킷의 크기가 2배 증가한다는 것이다.

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //  16
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  • 다만, 버킷 크기가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다.
    • 이를 재해싱(re-hashing) 이라고 한다.
  • 그러므로, HashMap에 저장될 데이터의 개수가 예측 가능한 경우에는 HashMap 객체 생성 시 버킷 개수를 지정해서 재해싱을 최소화 시키는 것이 성능상 유리할 것이다.
    • 버킷 개수는 HashMap 객체 생성 시, 파라미터로 값(capacity)으로 조절 가능.
  • 하지만, 이렇게 해시 버킷 크기를 두 배로 확장하는 것에는 결정적인 문제가 있다.
  • 해시 버킷의 개수 M이 2^a 형태가 되기 때문에, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다는 것이다.
    • 아무리 hashCode()로 32비트 영역을 고르게 분포했다고 하더라도, 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.

좋은 해시 함수란?

  • 모든 버킷에 균등하고, 불규칙적으로 분포될 수록 좋은 해시 함수!
  • 즉, key의 특정부분으로 인해 key의 hashCode()값이 결정되면 안된다.
  • 만약, 위처럼 M 값을 2의 승수로 한다면 해쉬값이 홀수일 경우 결과는 홀수, 짝수일 경우 결과는 짝수를 도출할 것이다.
  • 그런데, 만약 내가 만든 서비스의 모든 객체들의 hashCode()값이 짝수라면 어떻게 될까?
  • 짝수 버킷으로만 데이터가 편향될 것이고, 홀수버킷의 공간은 효율적으로 사용하지 못하게 될 것이다.
    • 이러면, 충돌 확률도 높아진다…

  • 또한, M 값을 2의 승수로 하면 해시값을 예측할 수 있다는 문제점도 발생할 수 있다.
  • 예를들어, 특정 객체의 hashCode() 값이 50이고 M이 2^2이라고 가정해보자.
    • 해시값은 2이다.
    • 50을 이진수로 바꾸면 110010 이다.
    • 2^2으로 나눴을 때, 50과 동일한 결과를 내는 값으로는 14, 46, 62 등이 있다.
    • 이들을 모두 이진수로 바꿔보자!
    • 14 -> 001110, 46 -> 101110, 62 -> 111110
    • 규칙이 보이는가?
    • 2의 승수로 나머지 연산을 수행하면, 오른쪽 비트 2개(나누는 값이 2의 2승이므로)에 의해 해시값이 결정된다.
    • 이렇게 규칙이 존재하면, 버킷이 한쪽으로 편향될 가능성이 높아진다.
      • 하필 내 서비스에서 사용되는 객체들의 hashCode()값이 전부 이진수 ...10으로 끝난다고 생각해보자.
  • 따라서 짝수, 특히 2의 승수값으로 나누는 것은 좋은 선택이 아니다.
  • 그래서 전통적으로 해시함수에서는 나누는 값을 홀수, 특히 홀수중에서도 소수를 자주 사용한다.

보조 해시 함수

  • supplement hash function
  • index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있다.
  • 그러나 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 해야 한다.
  • 즉, 보조 해시 함수의 목적은 key에 대한 해시 값을 변형하여, 해시 충돌 가능성을 줄이는 것이다.


참고

댓글남기기

참고