HashMap putVal removeNode 해석 공부중

짬날때 해석 공부용이라 틀릴수도있다.

해시(Hash-map)란?
해시는 key-value쌍으로 데이터를 저장하는 자료구조
key값을 넣으면 해시 함수를 통해 저장소의 적당한 위치에 value를 저장하는 자료구조이다

해시 함수(Hash-function)
 

 

해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 

 

• 해시 테이블(hash table) : 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조
• 해싱(Hashing) : 해시 테이블을 이용한 탐색

 

 

출처:https://www.fun-coding.org/DS&AL1-6.html

 

• 해싱 : 어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스(주소)를 결정하는 기법
• 해시 함수 : 키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시 주소를 해시 테이블(hash table)의 인덱스로 사용 

이 배열의 인데스 위취에 자료를 저장할 수도 있고 거기에 저장된 자료를 꺼낼수도 있다. 

 

 

 

출처 : https://mattlee.tistory.com/62

 

 

키값 k를 입력받아 해시 함수 h(k)로 연산한 결과인 해시 주소 h(k)를 인덱스로 사용하여 해시 테이블에 있는 항목에 접근한다. 해시 테이블 ht는 M개의 버킷(bucket)으로 이루어지는 테이블로서 ht[0], ht[1], ..... , ht[M-1]의 원소를 가진다.

 

 

Hash And HashCollision

• 해싱(Hashing) 이란? 특정 데이터를 일관된 절차를 통해 고정된 크기의 데이터로 변환하는 과정을 말한다.

int index = X.hashCode()

• 자바에서는 데이터에 대한 해쉬 값이 2^32가지의 정수형을 가질 수 있다.
• 문제는 데이터의 종류는 사실상 무한하기 때문에 서로다른 데이터가 같은 해쉬 값을 가지는 경우가 생기고 이 경우를 hash Collision(해쉬 충돌)이라고 한다. 일반적으로 해쉬 함수는 해쉬 충돌을 줄일 수 있는 방향을 추구해야한다.
• 해시맵은 Seperate Chaining을 활용한다 
• 하지만 하나의 버킷에 몰려서 체인의 길이가 비약적으로 늘수있어서 검색삽입삭제 시, 시간복잡도가발생..O(1)에서 O(N)로..

• 이 문제를 해결하기 위해 HashMap은 해쉬 충돌이 적은 해쉬함수활용, 보조 해쉬함수 사용, 해시 버켓 확장 재할당, chain을 tree(레드 블랙 트리)로 바꾸는 등의 여러 방식을 활용하고 있다.트리로인해 O(logN)으로 어느정도 최적화 할 수 있다

https://velog.io/@xogml951/Java-HashMap%EC%9D%98-%EB%8F%99%EC%9E%91-%EC%9B%90%EB%A6%AC

Java HashMap의 동작 원리

 

//HashMap.put

  public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);

    }

//hash(key) : 두 object의 key가 동일한 해시코드를 갖는다면 충돌을 일으킨다. key값이 다르더라도 hashcode메소드로 인해 해시값이 같을 수 있다고한다. 나중에 hashCode를 파봐야겟다 

 

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

   }

//해당key의 Object에 있는 해시코드메소드를 실행하고 해시코드를 가져와서 16번 오른쪽쉬프트하고

//xor를 해서 hash값을 반환  //왜16번째오른쪽쉬프트하고 xor를 할까? 모르겠다.

 

 /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key 
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value   //onlyIfAbsent 가 true라면 기존값을 변경하지 않음
     * @param evict if false, the table is in creation mode.          //evict가 false라면 테이블은 생성 모드 
     * @return previous value, or null if none                              //이전 값 또는 값이 없으면 null
     // onlyIfAbsent가 false로 주니까 기존값을 변경한다는의미
     // evict 는 true니까 테이블은 생성모드가 아니다

 */

//    transient Node<k,v>[] table;</k,v> //멤버변수

 

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; 

        Node<K,V> p;

        int n, i;
        if ((tab = table) == null || (n = tab.length) == 0) //멤버변수 노드에 값이 있는지 
            n = (tab = resize()).length; //처음 put하게되면 resize 16

 
        if ((p = tab[i = (n - 1) & hash]) == null)    //해당 인덱스(주소) (n-1)&hash 에 노드값 없으면  
            tab[i] = newNode(hash, key, value, null);

            //새로운 노드를 생성 해서 노드배열에 넣어줌 newNode는링크드리스트구현객체
        else {//인덱스에 값이 있으면?
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))    //해시값이 같고 키값이 같으면 
                e = p; //기존에 있던 값을 교체한다. if (e != null)로감 
            else if (p instanceof TreeNode) //Node<K,V> p 버킷이 이미 트리로 변경되었을때 트리노드라면 
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //트리노드라면 트리에 풋한다.
            else {
                for (int binCount = 0; ; ++binCount) { //binCount:버킷에 담긴 노드의 개수, 해당버킷에서 순차적으로 읽는다  
                    if ((e = p.next) == null) {  //현재노드의 다음포인터에 데이터가없다면 
                        p.next = newNode(hash, key, value, null); // 현재존재하는 노드의 다음포인터에 노드를 추가 링크드리스트 
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  //8 기존 링크드리스트를 트리노드로 변경기준 
                            treeifyBin(tab, hash); //레드블랙트리로변경, 8개보다 많고 맵의 크기가 64이상이어야함!
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) //위소스와같이 해시값같고키값같으면 교체 
                        break; 
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key 기존매핑이 존재한다면 교체
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);//? key 중복이 존재할때 Node Link 교체한다는메서드라함..
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold) //0>12  13>12 
            resize();
        afterNodeInsertion(evict); //? 노드추가후 정리한다는 메서드라함
        return null;
    }

 

 

//resize

 /**
     * Initializes or doubles table size.  If null, allocates in

//* 테이블 크기를 초기화하거나 두 배로 늘립니다. null인 경우 다음에 할당합니다.
     * accord with initial capacity target held in field threshold.

//* 현장 임계값에 설정된 초기 용량 목표와 일치합니다.

     * Otherwise, because we are using power-of-two expansion, the
//* 그렇지 않으면 2의 거듭제곱 확장을 사용하기 때문에
     * elements from each bin must either stay at same index, or move
// * 각 bin의 요소는 동일한 인덱스에 유지되거나 이동되어야 합니다.

    * with a power of two offset in the new table.

//* 새 테이블에서 오프셋 2의 거듭제곱을 사용합니다

용량은 16 으로주고, 12(threshold 멤버변수에=  12 즉 75%일때마다 리사이징하기위해)  

75퍼센트 차면 제곱으로 용량을 준다.

 

   * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length; //처음put경우0 : 원래있던거
        int oldThr = threshold;  //맴버변수 int threshold;재구축기준 
        int newCap, newThr = 0;
        if (oldCap > 0) { //원래용량이 >0 
            if (oldCap >= MAXIMUM_CAPACITY) { //용량이 맥시멈이라면 1073741824 
                threshold = Integer.MAX_VALUE; //한계점에 21억
                return oldTab; //기존table return   
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY) //용량이 꽉차지않았으면
                newThr = oldThr << 1; // double threshold  //왼쪽으로 1칸이동
        }
        else if (oldThr > 0) // initial capacity was placed in threshold 초기용량에 임계값이 배치되어있으면
            newCap = oldThr;  
        else {               // zero initial threshold signifies using defaults 1. 처음풋장소, 초기임계값이 0이면 기본값 세팅 
            newCap = DEFAULT_INITIAL_CAPACITY; //16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12.0 //0.75*16 
             //capicity는 16이고 loadfactor는 0.75 만약 용량을 크게 설정하면 공간이 매우 낭비

             //로드팩터가 작다면 그만큼 리해싱이 일어나 전체크기가 빠르게 늘어나서 메모리낭비가됨

             //로드팩터가 크다면 데이터가 많이 저장되어도 리해싱이 일어나지는 않더라도 검색속도가 느려짐 

         }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr; //처음 12 

        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //초기화 확인 후 새로운 배열 생성 첫put은 16크기   
        table = newTab; //새로 배열을 생성 초기화 후 
        if (oldTab != null) { //기존 테이블에 데이터가 있다면 넣어준다.. 
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null) //기존테이블의 다음포인터가 없을경우 
                        newTab[e.hash & (newCap - 1)] = e;  //새로운배열에 값을 넣어준다
                    else if (e instanceof TreeNode) //잇는데 트리노드형태 인경우 
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //트리에잘넣어준다? 
                    else { // preserve order 연결리스트로 잘 넣어주는거같음(?)
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

 

출처 https://sabarada.tistory.com/57

resize()를 거친 후 우리는 hash & (n - 1)의 index 즉 (hash % n - 1)의 index에 아무런 값이 들어 있지 않으면 아래와 같이 새로운 노드를 아래와 같이 집어넣게됩니다. Hashmap의 시간복잡도가 O(1)인 이유는 key값을 (hashing & n - 1)으로 직접 index를 가져오기 때문

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

newNode를 들여다 보면 아래와 같이 새로운 Node를 만들어 해당 배열에 넣는 것을 알 수 있습니다.

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
}

Node는 LinkedList를 구현한 객체라고 보시면 되며 구셩요소는 아래와 같습니다.

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
}

 

   /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //64 해시맵의크기가 64보다 작으면 리사이즈하 트리화하지않는다
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

 

 

해시맵의 크기가 64가 되고 버킷에 담긴 노드의 개수가 8개 이상이면 트리화 됨

이렇게 하면 상대적으로 해쉬 충돌이 많이 일어나서 한 해쉬버켓에 여러 노드가 들어와도 O(N)에서 O(logN)으로 어느정도 최적화 할 수 있다

 

*해시맵은 해시 충돌을 어떻게 처리하고 해시맵은 어떻게 성능 저하를 해소하는가?
해시값이 충돌이 일어낫을때 세퍼렛 체이닝 방식을 통해 이미 인덱스기 존재할경우 링크드 리스트를 만들어 순차적으로 저장한다. 이것도 최악의 경우 한 인덱스에 연결리스트 노드에 몰릴수잇기때문에 (시간복잡도가 빅O오브N이 발생) 자바 8부터 한버킷에 8개 노드이상이고 해시맵이 64크기이상이면 트리구조로 바뀜 시간복잡도는 빅오오브로그앤이 되어 빨라진다

리사이즈하는 시점에 왜 로드팩터가 중요할까? 
로드팩터는 부하율인데 용량을 늘릴 시기의 척도라 한다. 기본은 0.75 이며 초기용량 16에 75퍼센트가 차면 용량이 두배로 늘린 새 배열을 생성하고 해시를 다시 계산해서 복사한다. 

 

로드팩터에 따라 용량과 리해싱이 달라지는데 

로드팩터가 낮으면 해시테이블은 넉넉한 공간을 갖고 잇어서 해시충돌이 발생률이 낮아지지지만 리사이즈시 공간이 두배씩 추가확보되기때문에 공간복잡도가 늘어난다 시간복잡도는 빅오오브원을 보장 메모리 낭비지만 검색속도가 빠름 

로드팩터가 높으면 해시충돌이 빈번해 시간복잡도가 늘어난다 즉 검색속도가 느려진다 

 

Rehashing
해시 테이블의 크기를 늘리고, 늘어난 해시테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것

 

https://sabarada.tistory.com/57

https://ohtaeg.tistory.com/7

https://woodcock.tistory.com/24

https://velog.io/@xogml951/Java-HashMap%EC%9D%98-%EB%8F%99%EC%9E%91-%EC%9B%90%EB%A6%AC        

 

 public boolean remove(Object key, Object value) {
      return removeNode(hash(key), key, value, true, true) != null;
 }

 

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;

        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {  //인덱스에 값이 존재하면 사실 수식이 이해가안가지만 그 키에대한 인덱스가나오나봄

// node 구하기 시작---------------

            Node<K,V> node = null, e; K k; V v;  
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) //해시값이 같고 키가 일치하면 
                node = p; //노드에 해당노드를 넣어준다.
            else if ((e = p.next) != null) { 
                if (p instanceof TreeNode) //트리라면 
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key); //트리에서 가져온다
                else {
                    do { 
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) { //2.해시값이 같고 키값이 일치할때까지 
                            node = e; //노드에 해당 노드를 넣어준다.
                            break;
                        }
                        p = e;    //p는 break 되기 전인 해당 키의 노드를 구하기 바로 이전 노드일거다! (아래서 p.next로 지워준다)
                    } while ((e = e.next) != null); //1.다음포인터가 있을때까지 순회한다.
                }
            }

// node 구하기 끝---------------

            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) { //값이잇으면  
                if (node instanceof TreeNode)//트리구조면 트리에서 remove
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p) 
                    tab[index] = node.next; //null을 준다는의미인듯?
                else
                    p.next = node.next; //p는 break 되기 전의 해당키의 노드를 구하기 바로 이전노드이므로 이전.next는 해당키의 노드 = null 
                ++modCount;
                --size;
                afterNodeRemoval(node); //node날리기 
                return node;
            }
        }
        return null;
    }