자바 Hashtable, HashMap

HashMap과 HashTable을 정의한다면, '키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array이다

(Hashtable = 쓰레드 세이프함, HashMap = 쓰레드 세이프 하지 않음)

HashMap은 각 객체에 기본적으로 hashCode() 메서드가 반환하는 값을 사용하는데 결과 자료형은 32int이다.

논리적으로 생성 가능한 객체의 수가 2^32보다 많을 수 있다.

따라서 많은 해시 함수를 이용하는 associative array구현에서는 메모리를 절약하기 위해서 실제 해시 함수 표현 정수 보다 작은 원소가 있는 배열만을 사용한다.

int index = X.hashCode() % M;  

 

Open Addressing

 

연속된 공간에 데이터를 저장하기 때문에 SC보다 캐시효율이 높다. 따라서 데이터 갯수가 충분히 적다면 OA가 더 성능이 높다.

하지만 배열의 크기가 커질수록 캐시효율이라는 OA의 장점이 사라진다. 배열이 커지면 L1,L2 적중률이 낮아지기 때문이다.

 

위 코드는 1/M의 확률로 같은 해쉬 버킷을 사용하게 된다. 이는 해시 함수가 얼마나 해시 충돌을 잘 회피하도록 구현되었느냐에 상관없이 발생할 수 있는 또 다른 종류의 해시 충돌이다 . 이렇게 해시 충돌이 발생하더라도 키-값 쌍 데이터를 잘 저장하고 조회할 수 있게 하는 방식에는 대표적으로 두가지가 있다.

 

Open-Addressing : 이미 사용중인 버킷이 있을 경우 다른 버킷을 찾아 데이터를 삽입하는 방식, 찾는 방식에는 Linear Probing, Quadratic Probing 등의 방법을 사용함.

Sperate Chaning : 데이터를 저장/조회할 때. 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분

 

L1 : CPU에 내장된 캐시로서 데이터 사용 및 참조에 먼저 사용된다 8~64KB정도의 용량으로 CPU가 

L2 : L1과 비슷한 용도이지만 그보다 느리고, 일반적으로  64KB~4MB 정도가 사용된다. L2캐시는 CPU회로판에 별도의 칩으로 내장된다.

HashMap, Hashtable은 Map 인터페이스를 상속받아 구현되어 데이터를 키와 밸류로 관리하는 자료구조

둘다 Map인터페이스를 구현하고 있어서 제공되는 기능은 같다.

해시테이블의 관건은 어떻게 해시 충돌을 줄일지가 핵심이다.

 

해쉬맵은 Additional HashFunction을 사용하여 성능상 유리하다

해쉬맵은 Seperate Chaning을 사용하여 OpenAddressing의 Clustering에 따른 삭제, 탐색 연산이 비효율적이고, Sepertae Chaning이 충돌을 줄이고 충돌시 발생한 체인에 대한 속도를 잘 조정한다면 더 효율적이기 때문이다.

 

 

 

특히 get, put에서 해시 충돌을 어떻게 해결하는지 살펴보자

 

주석 설명 : 매핑된 특정 키값을 리턴한다. 키값이 없는 경우 null값을 리턴한다.

 

 

해시 테이블의 Seperate Chaning 을 통한 put, get

 

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     * 키를 찾으면 밸류를 리턴하고 찾지 못하면 null을 리턴함
     
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key.equals(k))},
     * then this method returns {@code v}; otherwise it returns
     * {@code null}.  (There can be at most one such mapping.)
     * 
     * @param key the key whose associated value is to be returned
     * @return the value to which the specified key is mapped, or
     *         {@code null} if this map contains no mapping for the key
     * @throws NullPointerException if the specified key is null
     * @see     #put(Object, Object)
     */
     
     
    @SuppressWarnings("unchecked")
    public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        // 해당 해시값을 찾을 때 까지 선형적으로 순회한다. 
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

 

    /**
     * Maps the specified <code>key</code> to the specified
     * <code>value</code> in this hashtable. Neither the key nor the
     * value can be <code>null</code>. <p>
     *
     * The value can be retrieved by calling the <code>get</code> method
     * with a key that is equal to the original key.
     *
     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or <code>null</code> if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               <code>null</code>
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
     
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        
        // 비어있는 버킷이 있을 때 까지 선형적으로 순회한다.
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

 

 

Hashmap에서 Seperate Chaning 방식을 이용한 put()

 

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); // table 배열 생성 } // HashMap에서는 null을 키로 사용할 수 있다. if (key == null) return putForNullKey(value); // value.hashCode() 메서드를 사용하는 것이 아니라, 보조 해시 함수를 이용하여 // 변형된 해시 함수를 사용한다. "보조 해시 함수" 단락에서 설명한다.  
        int hash = hash(key);

        // i 값이 해시 버킷의 인덱스이다.
        // indexFor() 메서드는 hash % table.length와 같은 의도의 메서드다.
        int i = indexFor(hash, table.length);



        // 해시 버킷에 있는 링크드 리스트를 순회한다.
        // 만약 같은 키가 이미 저장되어 있다면 교체한다.
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        // 삽입, 삭제 등으로 이 HashMap 객체가 몇 번이나 변경(modification)되었는지
        // 관리하기 위한 코드다.
        // ConcurrentModificationException를 발생시켜야 하는지 판단할 때 사용한다.
        modCount++;


        // 아직 해당 키-값 쌍 데이터가 삽입된 적이 없다면 새로 Entry를 생성한다. 
        addEntry(hash, key, value, i);
        return null;
    }

 

자바 8에서는 레드블랙 트리를 접목시켰다.

 

레드 블랙 트리 : 각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 맞추려는 트리

 

이진 탐색트리에서 최악의 경우를 막기 위해서 고안됨.

 

 

데이터 갯수가 많아지면 리스트 대신 트리를 사용하여 데이터 갯수가 많아지면 더욱 유리하다. 또한 일부 해시 버킷에 몇개의 데이터가 집중될 수 있기 때문에(비둘기집의 원리), 트리를 사용한는 것이 성능상 이점이 있다.

 

 

링크드리스트냐 트리냐에 대한 기준은 하나의 해시 버킷에 할당된 키-값의 갯수이다.

Java8은 상수 형태로 기준을 정하고 있다.

 

하나의 해시 버킷에 8개의 키밸류 쌍이 모이면 링크드 리스트 트리로 변경.

데이터를 삭제하여 갯수가 6개 이르면 다시 링크드 리스트로 변경

 

트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터 갯수가 적을 때 트리와 링크드 리스트의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문이다. 8과 6으로 2이상의 차이를 둔 것은. 만약 차이가 1이라면 한 키-밸류 쌍이 반복되어 삽입/삭제 되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능저하가 있을 수 있기 때문이다.

 

 

 

 

해시 버킷 동적 확장

 

 

해시 버킷의 갯수가 적으면 충돌로 인한 성능상 손실이 발생함. 따라서 키-값 쌍 데이터 갯수가 일정 갯수 이상이면 버킷의 수를 두ㅐ로 늘린다.

기본값은 16개 이고 -> 2^30개 까지 늘어날 수 있다.

 

하지만 이 키-밸류 데이터를 읽어 새로운 SC을 구성해야 하는 문제가 있다.

HashMap 생성자의 인자로 초기 해시 버킷 갯수를 지정할 수 있으므로 데이터의 갯수가 어느정도인지 예측 가능하면 불필요하게 SC를 재구성하지 않게 할 수 있다.

 

 

 

보조 해시 함수

 

키의 해시값을 변경하여 해시 충돌 가능성을 줄이는 것이다.

이 보조 해시 함수는 1.4에 등장했고, 8에서는 새로운 보조 해시 함수를 사용한다.

 

자바7에서는 

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

 

그 이유는 8에서 해시 충돌이 많이 발생하면 링크드 리스트 대신 트리를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화되었기 때문

 

두번쨰로는 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, 7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다.

 

개념상 해시 버킷 인덱스를 계산할 때는 나머지 연산을 하는 것이 맞지만, M값이 2^a일때는 해시 함수의 하위 a비트 만들 취한 것과 값이 같다. 따라서 나머지 연산 대신 비트 논리곱 연산을 사용하면 수행이 훨씬 빠르다

 

 

 

 

 

 

 

 

 

 

 

해쉬맵에서 사용방식는 SC이다. OA는 데이터를 삭제할 때 처리가 효율적이기 어려운데, remove가 매우 빈번하게 호출될 수 있기 때문이다. 게다가 키-밸류 쌍이 일정 갯수 이상이되면 OA는 SA보다 느리다. OA의 경우 해시버킷을 채운 밀도가 높을수록 WorstCase 발생 빈도가 더 높다

SA에서는 보조 해시함수를 통해서 Worst Case를 줄일 수 있다.

 

요약 : 데이터의 갯수가 적을때 (버킷의 밀도가 낮을 때는) OA, 데이터가 많아지면 SC이 유리하다

 

 

Cache를 이용한 성능 향상

 

해쉬테이블에 대한 성능 향상 방법은 여러가지가 있지만, 눈에 띄는 쉬운 방식이 하나 있어서 마지막으로 간략하게 짚고 넘어가자. 해쉬테이블의 get(key)과 put(key)에 간단하게, 캐쉬 로직을 추가하게 되면, 자주 hit 하는 데이타에 대해서 바로 데이타를 찾게 함으로써, 성능을 간단하게 향상 시킬 수 있다.  

웹앱의 경우 HTTPRequest가 생성될 때마다, 여러개의 해쉬맵이 생성된다. 수 많은 해쉬맵 객체가 1초도 안되는 시간에 생성되고 도 GC의 대상이 된다. 메모리 크기가 보편적으로 증가하게 됨에 따라 메모리 중심적인 앱 제작도 늘었다. 따라서 갈수록 HashMap에 더 많은 데이터를 저장하고 있다.