해시 분포와 해시 충돌, HashMap, LinkedHashMap

Map

Map은 ADT로 다음과 같은 특징을 갖는다.

• key-value 형태로 값을 저장한다.
• key는 중복을 허용하지 않고 value는 중복을 허용한다. 즉, 하나의 key에는 하나의 value만 가진다.
• 저장 순서를 유지하지 않는다.

해시 충돌

자바의 HashMap은 버킷의 위치를 정할 때 객체의 해시 값을 사용한다. 이때 해시 값은 int형으로 32비트이다. 따라서 어떤 데이터에 대해 나올 수 있는 해시 값은 2^32개이며 그 이상의 데이터들을 HashMap에 저장하려고 하면 몇 개의 데이터들은 해시 값이 같을 수밖에 없다. 그리고 2^32개의 해시 값에 따른 각각 다른 버킷을 메모리 공간에 할당한다면 이는 매우 비효율적이다. 

 

따라서 HashMap에서는 메모리를 절약하기 위해 배열의 capacity만큼만 버킷을 생성한다. 즉 어떤 key와 value를 HashMap에 저장할 때 해시 함수를 통해 key에 대한 해시 값을 생성하고, 그 해시 값을 배열의 capacity로 나눈 나머지를 배열의 인덱스로 두어, 해당 위치에 key와 value를 저장한다.

index = key.hashCode() % capacity

 

해시 테이블을 통해 데이터에 접근할 때 O(1)의 시간 복잡도가 소요된다. 데이터의 key와 해시 함수를 통해 데이터가 저장된 배열의 인덱스를 구할 수 있고, 해당 위치에 저장된 데이터에 접근하면 되기 때문이다. 그러나 컴퓨터 자원은 유한하기 때문에 배열의 크기는 유한하다. 즉, 배열의 크기보다 많은 양의 데이터를 배열에 넣으려고 하다 보니 필연적으로 해시 충돌이 발생할 수밖에 없다. 따라서 다음과 같은 상황에서 해시 충돌이 발생할 수 있다.

• key 값이 다르지만 해시 값이 같은 경우
• key 값도 해시 값도 다르지만 (해시 값 % 배열의 크기)가 같은 경우

해시 충돌 해결법

개방 주소법(Open Addressing)

• 개방 주소법은 추가적인 메모리 공간을 사용하는 분리 연결법과 다르게 비어있는 해시 테이블의 공간을 활용하는 방식이다.
• 개방 주소법방식을 구현하기 위한 대표적인 3가지 방식이 있다.
  • Linear Probing: 충돌이 발생하면 바로 다음 버킷이 비어있는지 확인하고, 비어있지 않다면 계속해서 바로 다음 버킷이 비어있는지 확인하는 방식이다.
  • Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하여 데이터를 저장하고, 그 다음 충돌이 발생했을 때는 2^2만큼, 3^2만큼 이동하여 데이터를 저장한다.
  • Double Hashing Probing:  해시된 값을 한 번 더 해싱하여 새로운 주소를 할당하는 방식이다. 따라서 다른 방법들보다 더 많은 연산이 이뤄진다.
• 대표적으로 Linear Probing 방식에 대해 설명하자면,
  • 데이터 삽입: Linear Probing은 해시 충돌이 발생할 때 해당 인덱스 바로 뒤에 있는 버킷 중 비어있는 버킷을 찾아서 데이터를 삽입한다.
  • 데이터 조회: 데이터를 조회할 때는 해당 인덱스의 데이터와 비교하고 key 값이 같지 않으며, Linear Probing 방식이기 때문에 바로 뒤의 인덱스를 탐색해서 해당 key 값이 나올 때까지 탐색한다. 
  • 데이터 삭제: 데이터를 삭제할 때는 해당 인덱스 위치에 더미 데이터를 넣어준다. 만약 데이터 삭제 시 더미 데이터를 넣지 않으면 어떻게 될까? 위 사진에서 John Smith의 데이터를 삭제하고, Sandra Dee 데이터를 조회하는 상황을 예로 들어보자. Sandra Dee의 인덱스인 152에 접근한다. 그러나 해당 위치에는 데이터가 없기 때문에 데이터를 찾지 못하고 탐색을 끝내버린다. 반면, John Smith 데이터를 삭제할 때 삭제 표시를 해주는 더미 데이터를 넣어준다면, Sandra Dee 데이터를 조회할 때 인덱스 152에 접근하고, 삭제 표시가 있기 때문에 Linear Probing 방식인 점을 고려하여 뒤의 인덱스들까지 탐색하게 된다. 그리고 인덱스 153을 탐색할 때 데이터를 찾고 반환한다.
• 해시 충돌이 발생하면 특정 버킷과 그 아래 버킷까지 조회해야 할 수 있기 때문에 더이상 데이터 조회 시 발생하는 시간 복잡도는 O(1)이 아니다. 

분리 연결법(Separating Chaining)

• 분리 연결법은 LinkedList를 사용한다. 즉 각 Bucket들은 LinkedList로 이루어져 해시 충돌이 발생하더라도 해당 인덱스의 LinkedList에 데이터를 추가한다. 
• 데이터 삽입: 인덱스가 충돌될 때 해당 인덱스가 가리키고 있는 LinkedList에 노드를 추가하여 데이터를 추가한다. (위 사진의 경우 152번 인덱스가 충돌되어 152번 인덱스가 가리키는 LinkedList에 노드를 추가하였다.)
• 데이터 조회: 데이터를 조회할 때 해당 인덱스가 가리키고 있는 LinkedList를 선형 탐색하여 해당 key 값의 value를 찾는다.
• 데이터 삭제: 데이터를 삭제할 때도 해당 인덱스가 가리키고 있는 LinkedList에서 해당 노드를 삭제한다.
• LinkedList를 활용하여 해시 충돌이 발생하더라도 데이터를 저장할 수 있지만, 이제 더이상 데이터 조회 시 발생하는 시간 복잡도는 O(1)이 아니다. 배열의 특정 인덱스 위치에 있는 LinkedList를 순차적으로 탐색해야 하기 때문이다. 따라서 Separating Chaining 방식은 충돌이 많이 발생해서 LinkedList 형태로 데이터가 하나의 버킷에 계속 쌓이게 되면 데이터 조회에 걸리는 시간 복잡도가 O(N)까지 발생할 수 있다. 

자바의 HashMap에서의 분리 연결법

자바의 HashMap은 분리 연결법을 사용한다. 그런데 앞서 언급했든이 분리 연결법은 충돌이 많이 발생해서 하나의 버킷에 데이터가 많이 쌓이게 되면 데이터 조회에 걸리는 시간이 많이 걸린다는 단점이 있다. 

 

따라서 Java 8에서는 하나의 버킷에 8개의 데이터(key, value 쌍)가 쌓이면 트리 구조를 사용하여 성능을 개선한다. 이를 통해 조회 성능이 O(N)에서 O(logN)으로 좋아진다. 그리고 다시 하나의 버킷에 데이터가 6개 이하가 되면 트리에서 LinkedList 형태로 바꾼다. 

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

자바에서의 Map

HashMap

자바에서는 Map의 구현체로 HashMap을 제공한다. HashMap의 특징은 다음과 같다.

• HashMap은 각 객체의 hashCode() 메소드가 반환하는 값을 해시 값으로 사용한다.
• HashMap의 초기용량(버킷)은 16이고 로드팩터는 0.75이다. 즉, map의 3/4 이상 데이터가 차면 resize가 발생하고, 이때 resize의 규모는 현재 용량의 2배이다.
• 데이터 조회/삽입/삭제: key를 통해 데이터에 접근하기 때문에 O(1)의 시간 복잡도를 갖는다.
• 해시 충돌 해결 방법: Seperating Chaining 
  • 해시 충돌이 발생하면 해당 버킷에 여러 개의 데이터가 LinkedList 형태로 저장된다.
  • 그리고 데이터를 조회할 때 해당 버킷의 각 노드들(LinkedList에 저장된 데이터들)을 순차적으로 탐색하며, equals() 메소드를 실행한다. 즉, equals() 메소드를 통해 같은 객체인지 아닌지를 판단한다.

Resize, Load Factor

기본적으로 생성되는 HashMap 객체는 초기용량이 16이고 로드팩터가 0.75이다. 그렇다면 로드팩터는 무엇일까?

• 로드팩터는 저장공간이 가득 차기 전에 resize하여 용량을 확보하기 위한 척도이다. 그리고 임계점은 초기용량 * 로드팩터이다.
• 즉, 용량의 로드팩터만큼 차면(=임계점에 도달하면), resize가 일어난다.
• 로드팩터가 사용되는 자바의 컬렉션 프레임워크는 ArrayList, HashMap, ConcurrentHashMap, HashSet 등이 있다. (일반적으로 default 로드팩터는 0.75이지만 ArrayList의 로드팩터는 1이다.)
• resize가 일어나면 용량이 2배로 늘어나고, rehash가 진행되며 key.hashCode() % capacity를 통해 각 데이터가 저장될 배열의 인덱스를 다시 구해주고 해당 인덱스 위치에 데이터를 저장한다. 
• 예를 들어 HashMap을 생성하면, 초기용량은 16이고 로드팩터는 0.75이다. 따라서 Threshold는 16 * 0.75 = 12이다. 즉, map에 12번째 데이터를 추가할 때 map의 용량이 2배 증가하게 된다.

초기용량과 로드팩터에 의해 성능이 좌우된다. 

• 초기용량을 작게 설정하면 메모리 면에서는 좋지만, resize가 자주 일어날 수 있기 때문에 비효율적이다.
• 반대로 초기용량을 크게 설정하면 메모리를 많이 사용한다. 그러나 resize가 상대적으로 적게 일어난다.

다음 생성자들을 통해 초기용량과 로드팩터를 직접 설정할 수도 있다. 그러나 default 값이 최적화되어 있기 때문에 웬만해서는 default로 사용하고, 요구 사항에 맞게 다음 생성자들을 통해 초기용량과 로드팩터를 설정하면 된다. 

    public HashMap(int initialCapacity, float loadFactor) {
        ...
    }
    
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

HashMap vs HashTable

HashTable과 HashMap의 차이점은 다음과 같다.

• Thread-safe 여부
  • HashTable: Thread-safe하다
  • HashMap: Thread-safe 하지 않다. 따라서 멀티스레드 환경이 아니라면 HashTable은 HashMap 보다 성능이 떨어진다.
• Null 값 허용 여부 
  • HashTable: key에 null을 허용하지 않는다.
  • HashMap: key에 null을 허용한다. 

다만 HashMap이 동기화를 지원하지 않는다고 해서 HashTable을 사용하는 것은 좋지 않다. 그 이유는 HashTable 클래스는 자바에서 컬렉션 프레임워크가 만들어지기 전부터 존재하던 것으로, 호환을 위해 남겨준 것이다. 즉 구형인 HashTable을 사용하기보다 동기화를 지원하는 HashMap인 ConcurrentHashMap를 사용하자.

LinkedHashMap

HashMap은 저장 순서를 유지하지 않는다. 따라서 저장 순서를 유지하고자 한다면 LinkedHashMap을 사용하면 된다. LinkedHashMap에 대한 특징은 다음과 같다.

• LinkedHashMap은 HashMap을 상속받는다.

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V> {}

• HashMap과 마찬가지로 버킷에 충돌이 발생하지 않았다면 데이터 조회/삽입/삭제의 시간 복잡도는 O(1)이다.
• 그러나 HashMap과 다르게 순서를 유지해야 하기 때문에 HashMap에 비해서는 성능이 조금 더 떨어진다.
• LinkedHashMap은 HashMap과 마찬가지로 Thread-safe 하지 않다. 따라서 멀티스레드 환경에서 사용하려면 다음과 같이 사용하면 된다. 

Map map = Collections.synchronizedMap(new LinkedHashMap());

---

Reference

• https://github.com/wjdrbs96/Today-I-Learn/blob/master/Java/Collection/Map/Java%20HashMap%20%EB%8F%99%EC%9E%91%EC%9B%90%EB%A6%AC.md