해시맵(HashMap)이란?

1. 해시맵(HashMap)이란?

HashMap은 Java Collection Framework에 속한 구현체 클래스로 Map 인터페이스를 구현하고 있다. 그렇기 때문에 Map의 구조인 key-value쌍으로 구성되어 있다.

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
}

HashMap 클래스의 내부는 위와 같은 상속, 구현 관계를 가지고 있다.

<HashMap의 특징>

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

그렇다면 이런 HashMap은 왜 사용하는 것일까?

 

list 형태를 사용하지 않고 HashMap을 사용하는 이유는 성능 때문이다. 만약에 HashMap을 사용하지 않고 list를 사용했다면 원소를 검색하는데 시간복잡도는 O(n)일 것이다. 만약 정렬되어 있는 원소라면 Binary Search로 O(logN)가 된다.

반면에 HashMap은 삽입, 검색에 시간복잡도 O(1)이라는 이점을 가지고 있다.

 

 

※ 해시(Hash)란? 

해시(Hash)란 데이터를 다루는 기법 중 하나이며, 해시 함수(Hash Function)는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
매핑전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(Hash Value) 또는 해시코드(Hash code) 라고 하며, 키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing) 이라고 한다.

2. 해시맵(HashMap)과 해시테이블(HashTable)

HashTable 또한 Map 인터페이스를 구현하고 있기 때문에, HashMap과 HashTable이 제공하는 기능은 같다.

 

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

 

HashTable과 HashMap의 가장 큰 차이는 동기화(synchronized) 지원 여부이다.

HaspTable은 get()이나 put() 같은 주요 메서드에 synchronized 키워드가 붙어있어, 쓰레드 세이프(Thread safe)를 보장한다.

반면, HashMap은 쓰레드 세이프를 보장하지 않는다.

 

또, HashTable의 구현은 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있다.

 

3. 해시맵(HashMap) 내부 동작구조

3.1 hashCode()

Java의 최상위 객체인 Object에는 기본적으로 hashcode()가 정의돼있다. 즉, 모든 객체는 hashCode()를 갖는다.

여기서 hashCode()는 객체를 식별할 수 있는 식별값이다.

 

HashMap의 key로 저장할 객체는 hashCode()를 재정의하고, key 객체에서 재정의된 hashCode()는 해당 key에 대한 해시값을 얻는데 사용된다. 즉, hashCode()는 hash 함수로 사용되는 것이다.

 

hashCode()의 반환타입은 int이며, 총 32bit 정수 자료형으로 나타낼 수 있다.

내부적으로 값을 저장하기 위한 배열을 가지며, 이 배열을 가리켜 해시 버킷이라고 부른다.

3.2 hash 충돌

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

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

  int index = key.hashCode() % M;

 

이럴 경우, 서로 다른 hash 값을 갖는 객체라 할지라도 1 / M 확률로 충돌이 발생한다. 이러한 현상을, hash 충돌이라고 부른다.

이렇게 충돌이 발생하면, 완벽한 O(1)의 저장 및 조회 성능을 보장할 수 없다.

 

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

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

 

4. hash 충돌 해결방법

그렇다면 hash 충돌 현상을 어떻게 해결할 수 있을까? 대표적으로, 다음과 같은 방법들이 있다.

4.1 Open Addressing

• Linear Probing, Quadratic Probing, Double hashing 등이 있다
• Open Addressing은 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식
• 배열의 크기가 작을수록 유리한 방식        

4.2 Separate Chaining

• 충돌 시 해시 버킷 인덱스에 링크드 리스트를 이용해서 여러 value를 연결한 형태로 저장하는 방식
• Java의 HashMap에서 사용하는 hash 충돌 해결 방법
• 배열의 크기가 크면 클수록 유리한 방식

Java 7까지는 Separate Chaining을 구현하기 위해 링크드 리스트(Linked List)를 사용했다.

Java 8부터는 Separate Chaining을 구현하기 위해 링크드 리스트(Linked List) 혹은 트리(Tree)를 사용한다.(트리를 사용하는 이유는 성능상의 이점을 얻기 위해서이다.)

 

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

일반적으로, 트리는 링크드 리스트보다 메모리를 많이 사용하는 자료구조이다. 즉, 트리와 링크드 리스트 사이에는 메모리 공간과 성능 사이에 trade-off가 발생한다.

만약, HashMap에 저장할 데이터가 적은 상황이라면, 트리나 리스트간의 성능비교는 큰 의미가 없기 때문에, 상대적으로 메모리를 적게 쓰는 링크드 리스트를 사용하는 것이 좋다.

그렇지만, 저장할 데이터가 많을수록 성능상 트리가 유리할 것이다.

 

링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다.

즉, 하나의 배열 인덱스 내에 들어있는 데이터 개수가 기준이 됨.

 

하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 아래와 같이 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 또한, 데이터가 삭제되어 키-값 쌍이 6개가 되면 다시 트리를 링크드 리스트로 변경한다.

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

 

5. 해시 버킷 동적 확장

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 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의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.

 

이 때문에 보조 해시 함수가 필요하다.

 

6. 보조 해시 함수(supplement hash function)

index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있다.

그러나 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 해야 한다.

즉, 보조 해시 함수의 목적은 key에 대한 해시 값을 변형하여, 해시 충돌 가능성을 줄이는 것이다.

 

 

 

참고

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