HashMap & HashTable

Hash Algorithm

데이터를 다루는 기법 중에 하나로, 검색과 저장이 아주 빠르게 진행되는 자료구조입니다.

해쉬는 데이터를 검색할 때, 사용할 key 와 value(실제 데이터)가 한 쌍으로 존재하고, key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도는 O(1)에 수렴하게 됩니다.

 

해시가 왜 생겼을까요?

가장 기본적인 자료구조인 배열의 경우, 내부 인덱스를 이용하여 자료의 검색이 한 번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면

데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈 자리를 채우기 위해 이동해야 하므로 많은 시간이 소요됩니다.

또한, 연결리스트는 삽입, 삭제 시 인근 노드들의 참조 값만 수정해줌으로 써 빠른 처리가 가능했지만? 처음노드와 마지막 노드 이외의 위치에서 데이터를 삽입 또는 삭제할 경우나 데이터를 검색할 경우에 해당 노드를 찾기 위하여, 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수 밖에 없는 구조입니다.

 

 

Hash & Hash Function

해시와 해시 테이블을 알기 전에, Hash Function (해시함수) 라는 것을 잘 알고 있어야합니다.

데이터를 최대한 빠르게 찾기 위해서는 저장하는 위치도 잘 생각해서 저장을 해야합니다.

해시 함수의 정의는 'Key를 고정된 길이의 hash로 변경해주는 역할을 한다. 이 과정을 hashing이라고 한다.' 입니다.

key를 해시함수에 Input으로 넣어, Output으로 나오는 것을 해시라고 생각하면 됩니다.

이 해시가 저장위치가 된다고 생각하면 됩니다.

결국 해시 함수를 이용하여,  hashing 과정을 거쳐, key로 해시를 만들어내는 함수를 해시 함수입니다.

 

 

해시는 해시테이블(bucket+index)을 이용하여 데이터를 저장하게 됩니다.

해시함수를 이용하여, 반환된 데이터 고유 숫자 값을 Hash Code (해시코드) 라고하는데, 이 해시코드를 이용하여 테이블의 크기로 나머지 연산 작업할 한 뒤 결과를 buckets의 인덱스로 사용하게 됩니다. 

index = key % data.length
value = HashTable[index]

해시는 내부적으로 위와 같이 배열(Hash Table)을 사용하여 데이터를 저장하기 때문에 빠른 검색속도를 갖게되는 것입니다.

그리고 데이터 삽입과 삭제 시, 기존 데이터를 밀어내거나, 채우는 작업이 필요 없도록 해시 알고리즘을 이용하여, 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 Index 로 사용하게 됩니다.

즉, 삽입, 삭제 시에도 데이터의 이동이 없도록 만들어 구조다 보니 빠른 속도를 갖습니다. 

하지만, 해시테이블 크기에 따라서 성능 차이가 많이 날 수 있다는 점을 알고 계셔야합니다.

 

---

HashMap 과 HashTable

 

HashMap 과 HashTable 은 Java의 API 이름입니다.

HashTable 이란?

JDK 1.0 부터 있던 Java API 이고, HashMap은 Java 2에서 처음 선보인 Java Collections Framework 에 속한 API 입니다.

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

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

보조 해시 함수가 아니더라도, HashTable 구현에는 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있습니다.

HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다고 할 수 있습니다.

 

HashMap과 Hash Table을 정의한다면, '키에 대한 해기 값을 사용하여 값을 저장하고 조회하며, 키-밸류 쌍의 개수에 따라 동적으로 크키가 증가하는 연관 배열 (Associative array)' 라고 할 수 있습니다. 이 associate array 를 지칭하는 다른 용어가 있는데, 대표적으로 Map, Dictionary, Symbol Table 등이 있습니다.

 

// HashTable, HashMap의 선언부

public class 8ccce55530bc3477c678dd9921b60f3e.gifHashtable<K,V> extends Dictionary<K,V>  
    implements Map<K,V>, Cloneable, java.io.Serializable {

public class 928b3cc3fe40d69cd06cbe7f5f3767f8.gifHashMap<K,V> extends AbstractMap<K,V>  
    implements Map<K,V>, Cloneable, Serializable {

 

연관 배열 (Associative array) 을 지칭하기 위하여 HashTable 에서는 Dictionary 라는 이름을 사용하고, HashMap 에서는 그 명칭 그대로 Map 이라는 용어를 사용하고 있습니다.

 

Map은 원래 수학 함수에서 대응 관계를 지칭하는 용어로, 경우에 따라 함수 자체를 의미하기도 합니다.

즉, HashMap 이란 이름에서 알 수 있듯이, HashMap 은 키 집합인 정의역과 값 집합인 공역의 대응에 해시 함수를 이용합니다.

https://d2.naver.com/

 

해시 분포와 해시 충돌

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

 

Boolean 같이 서로 구별되는 객체의 종류가 적거나, Integer, Long, Double 같은 Number 객체는 객체가 나타내려는 값 자체를 해기 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있습니다.

하지만, String 이나, POJO(plain old java object) 에 대하여 완전한 해시 함수를 제작하는 것은 사실상 불가능합니다.

 

적은 연산만으로 빠르게 동작할 수 있는 완전한 해시 함수가 있다고 하더라도,

그것을 HashMap 에서 사용할 수 있는 것은 아닙니다.

HashMap은 기본적으로 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는데, 결과 자료형은 int 입니다. 32비트 정수 자료형으로는 완전한 자료 해시 함수를 만들 수 없습니다.

논리적으로 생성 가능한 객체의 수가 2³² 보다 많을 수 있기 때문이며, 또한 모든 HashMap 객체에서 O(1)을 보장하기 위해 랜덤 접근이 가능하게 하려면, 원소가 2³²인 배열을 모든 HashMap 이 가지고 있어야 하기 때문입니다.

 

따라서, HashMap 을 비롯한 많은 해시 함수를 이용하는 연관 배열 구현체에서는 메모리 절약하기 위하여 실제 해시 함수의 표현 정수 범위보다 작은 M개의 원소가 있는 배열만 사용합니다. 따라서, 다음과 같이 객체에 대한 해시 코드의 나머지 값을 해시 버킷 인덱스 값으로 사용하게 됩니다.

int index = X.hashCode() % M;

위 코드와 같은 방식을 사용하면, 서로 다른 해시 코드를 가지는 서로 다른 객체가 1 / M 의 확률로 같은 해시 버킷을 사용하게 됩니다. 이는 해시 함수가 얼마나 해시 충돌을 회피하도록 잘 구현되었느냐에 상관없이 발생할 수 있는 또 다른 종류의 해시 충돌입니다.

이렇게 해시 충돌이 발생하더라도, 키 - 밸류 쌍 데이터를 잘 저장하고 조회할 수 있게 하는 방식에는 대표적으로 두 가지가 있습니다.

또한 이 대표적인 둘 이외에도 해시 충돌을 하기 위한 다양한 자료구조가 있지만, 거의 이 둘을 응용한 것입니다.

• Open Addressing
  • Linear Probing (linear search)
  • Quadratic Probing (nonlinear search)
  • Double Hashing (uses two hash functions)
  • Rehasing
• Separate Chaining
  • Separate Chaining with String Keys
  • The class hierarchy of Hash Tables
  • Implementation of Separate Chaining

더 깊고 보고싶다면, 아래 링크를 확인해주시면 될 거 같아요

https://slidetodoc.com/hashing-collision-resolution-schemes-collision-resolution-techniques-separate/

Hashing Collision Resolution Schemes Collision Resolution Techniques Separate

 

 

 

대표적인 두 가지에 대해서 설명을 드리겠습니다.

Open Addressing 은 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식입니다.

데이터를 저장 또는 조회 할 해시 버킷을 찾을 때, Linear Probing, Quadaratic Probing 등의 방법을 사용합니다.

Separate Chaining 에서 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분(head) 입니다.

 

둘 모두 Worst Case O(M) 입니다.

하지만, Open Addressing 은 연속된 공간에 데이터를 저장하기 때문에, Separate Chaining 에 비하여 캐시 효율이 높습니다.

따라서 데이터 개수가 충분히 적다면, Open Addressing 이 Separate Chaining 보다 더 성능이 좋습니다.

하지만,

배열의 크기가 커질수록 캐시 효율이라는 Open Addressing 의 장점은 사라집니다. 배열의 크기가 커지면, L1, L2 캐시 적중률(hit ratio) 이 낮아지기 때문입니다.

 

Java의 HashMap 에서 사용하는 방식은 Separate Chaining 입니다. Open Addressing 은 데이터를 삭제할 때, 처리가 효율적이기 어려운데, HashMap 에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문입니다.

게다가, HashMap 에 저장된 키-밸류 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing 은 Separate Chaining 보다 느립니다. Open Addressing 의 경우, 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문입니다.

반면,

Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정' 할 수 있다면, Worst Case 에 가까운 일이 발생하는 것을 줄일 수 있습니다.

 

transient Node<K,V>[] table;


static class Node<K,V> implements Map.Entry<K,V> {  
  // 클래스 이름은 다르지만, Java 7의 Entry 클래스와 구현 내용은 같다. 
}


// LinkedHashMap.Entry는 HashMap.Node를 상속한 클래스다.
// 따라서 TreeNode 객체를 table 배열에 저장할 수 있다.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {


        TreeNode<K,V> parent;  
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;   

        // Red Black Tree에서 노드는 Red이거나 Black이다.
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        final TreeNode<K,V> root() {
        // Tree 노드의 root를 반환한다. 
        }

        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        // 해시 버킷에 트리를 저장할 때에는, root 노드에 가장 먼저 접근해야 한다.
        }


        // 순회하며 트리 노드 조회 
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
        final TreeNode<K,V> getTreeNode(int h, Object k) {}


        static int tieBreakOrder(Object a, Object b) {
         // TreeNode에서 어떤 두 키의comparator 값이 같다면 서로 동등하게 취급된다.
         // 그런데 어떤 두 개의 키의 hash 값이 서로 같아도 이 둘은 서로 동등하지 
         // 않을 수 있다. 따라서 어떤 두 개의 키에 대한 해시 함수 값이 같을 경우, 
         // 임의로 대소 관계를 지정할 필요가 있는 경우가 있다. 
        }


        final void treeify(Node<K,V>[] tab) {
          // 링크드 리스트를 트리로 변환한다.
        }



        final Node<K,V> untreeify(HashMap<K,V> map) {
          // 트리를 링크드 리스트로 변환한다.
        }

        // 다음 두 개 메서드의 역할은 메서드 이름만 읽어도 알 수 있다.
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {}
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {}


        // Red Black 구성 규칙에 따라 균형을 유지하기 위한 것이다.
        final void split (…)
        static <K,V> TreeNode<K,V> rotateLeft(…)
        static <K,V> TreeNode<K,V> rotateRight(…)
        static <K,V> TreeNode<K,V> balanceInsertion(…)
        static <K,V> TreeNode<K,V> balanceDeletion(…)



        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
        // Tree가 규칙에 맞게 잘 생성된 것인지 판단하는 메서드다.
        }
    }

 

해시 버킷 동적 확장

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만, 해시 충돌로 인해 성능상 손실이 발생합니다.

그래서, HashMap은 키-밸류 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘립니다.

이렇게 해시 버킷 개수를 늘리면 값도 작아져, 해시 충돌로 인한 성능 손실 문제를 어느정도 해결 할 수 있습니다.

 

해시 버킷 개수의 기본 값은 16이고, 데이터의 개수가 임계점에 이를 때마다 해시 버킷 개수의 크기를 두 배씩 증가시킵니다.

버킷의 최대 개수는 2³⁰개 입니다.

그런데, 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-밸류 데이터를 읽어 새로운 Separate Chaining 을 구성해야하는 문제가 있습니다. HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느정도 인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면, 불 필요하게 Separate Chaining 을 재 구성하지 않게 할 수 있습니다.

 

// 인자로 사용하는 newCapacity는 언제나 2a이다.
void resize(int newCapacity) {  
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;

        // MAXIMIM_CAPACITY는 230이다.
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];


        // 새 해시 버킷을 생성한 다음 기존의 모든 키-값 데이터들을
        // 새 해시 버킷에 저장한다.
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }


    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        // 모든 해시 버킷을 순회하면서
        for (Entry<K,V> e : table) {
            // 각 해시 버킷에 있는 링크드 리스트를 순회하면서
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 해시 버킷 개수가 변경되었기 때문에
                // index 값(hashCode % M)을 다시 계산해야 한다. 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

 

해시 버킷 크기를 두 배로 확장하는 임계점은 현재의 데이터 개수가 'load factor * 현재의 해시 버킷 개수' 에 이를 때입니다.

이 load factor는 0.75 즉 3/4 입니다. 

이 또한 HashMap의 생성자에서 지정할 수 있습니다.

임계점에 이르면 항상 해시 버킷 크기를 두 배로 확장하게 됩니다. 

 

즉, 기본 생성자로 생성한 HashMap 을 이용하여 많은 양의 데이터를 삽입할 때에는, 최적의 해시 버킷 개수를 지정한 것보다 약 2.5배 많이 키-밸류 쌍 데이터에 접근해야합니다. 이는 곧 수행시간이 2.5배 길어진다고 할 수 있습니다.

따라서, 성능을 높이려면 HashMap 객체를 생성할 때, 적정한 버킷 개수를 지정하면 됩니다.

 

그런데, 

이렇게 해시 버킷 크기를 두 배로 확장하는 것에는 결정적인 문제가 있습니다.

해시 버킷의 개수 M이 2의 N승 형태가 되기 때문에, indx = X.hashCode() % M 을 계산할 때, X.hashCode() 의 하위 N 개의 비트만 사용하게 된다는 것입니다. 즉, 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하여도, 해시 값을 2의 승수로 나우면 해시 충돌이 쉽게 발생할 수 있습니다.

그래서 보조 해시 함수가 필요합니다.

 

보조 해시 함수

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

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

 

보조 해시 함수(supplement hash function) 의 목적은 '키' 의 해시값을 변형하여, 해시 충돌 가능성을 줄이는 것입니다. 

JDK 1.4 에 처음 등장하여, Java ver 5~7 은 같은 방식의 보조 해시 함수를 사용하고, Java 8부터는 다시 새로운 방식의 보조 해시 함수를 사용하고 있습니다.

 

Java 7 HashMap 에서의 보조 해시 함수

final int hash(Object k) {  
        // Java 7부터는 JRE를 실행할 때, 데이터 개수가 일정 이상이면
        // String 객체에 대해서 JVM에서 제공하는 별도의 옵션으로
        // 해시 함수를 사용하도록 할 수 있다.
        // 만약 이 옵션을 사용하지 않으면 hashSeed의 값은 0이다.
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        // 해시 버킷의 개수가 2a이기 때문에 해시 값의 a비트 값만을 
        // 해시 버킷의 인덱스로 사용한다. 따라서 상위 비트의 값이 
        // 해시 버킷의 인덱스 값을 결정할 때 반영될 수 있도록
        // shift 연산과 XOR 연산을 사용하여, 원래의 해시 값이 a비트 내에서 
        // 최대한 값이 겹치지 않고 구별되게 한다.
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

 

그 이후 Java 8 부터는 훨씬 단순한 형태의 보조 해시 함수를 사용합니다.

static final int hash(Object key) { 
    int h; 	
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}

Java 8 에서는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용합니다.

그 이유로는 두 가지가 있습니다.

• Java 8 에서는 해시 충돌이 많이 발생하면 링드르 리스트 대신, 트리를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화 되었기 때문입니다.
• 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7 까지 사용했던 보조 해시 함수의 효과가 크지 않습니다.

위 두 가지 경우 중, 두 번째 경우가 더 결정적인 원인이 되어 함수 구현이 바뀌었습니다.

 

 

String 객체에 대한 해시 함수

String 객체에 대한 해시 함수 수행시간은 문자열 길이에 비례합니다.

때문에 String 객체에 대해서 빠르게 해시 함수를 수행하기 위해, 일정 간격의 문자에 대한 해시를 누적한 값을 문자열에 대한 해시 함수로 사용했습니다.

 

JDK 1.1 에선,

public int hashCode() {  
    int hash = 0;
     int skip = Math.max(1, length() / 8);
     for (int i = 0; i < length(): i+= skip) 
           hash = s[i] + (37 * hash);
    return hash;
}

위 코드르 보신바와 같이 모든 문자에 대한 해시 함수를 계산하는 게 아니라, 문자열의 길이가 16을 넘으면 최소 하나의 문자를 건너가며 해시 함수를 계산했습니다.

 

그러나, 이 방식은 심각한 문제가 있었습니다.

웹 상의 URL 길이가 수십 글자에 이르면서 앞 부분은 동일하게 구성되는 경우가 많습니다.

이 경우, 서로 다른 URL의 해시 값이 같아지는 빈도가 매우 높아질 수 있는 문제가 되어 이 방식은 곧 폐기가 되었습니다.

 

이 후에 JDK 1.8 에선,

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;
    }

Horner's 메소드를 구현하였습니다. 다항식을 계산하기 쉽도록 단항식으로 이루어진 식으로 표현하는 것입니다.

 

👇 String 객체 해시 함수에서 31을 사용하는 이유

String 객체 해시 함수에서 31을 사용하는 이유는, 31이 소수이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다. 31N=32N-N인데, 32는 2⁵ 이니 어떤 수에 대한 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은, (N << 5) – N과 같다. 31을 곱하는 연산은 이렇게 최적화된 머신 코드로 생성할 수 있기 때문에, String 클래스에서 해시 값을 계산할 때에는 31을 승수로 사용한다.

 

 

 

글을 마치며,

Java HashMap 에서는 해시 충돌을 방지하기 위하여, Separate Chaining 과 보조 해시 함수를 사용한 다는 것과,

Java 8에서는 Separate Chaining에서 링크드 리스트 대신 트리를 사용하기도 한다는 것, 그리고 String 클래스의 hashCode() 메서드에서 31을 승수로 사용하는 이유는 성능 향상 도모를 위한 것이라고 정리할 수 있다.

 

 

 

참고 링크

https://d2.naver.com

https://bcho.tistory.com/1072

Hashtable의 이해와 구현 #1

https://selina-park.tistory.com/51

[자료구조] 해시 Hash, 해시맵 HashMap