[데이터 구조] - jdk 1.8 에서 HashMap 소스 코드 분석

HashMap
Hashmap 는 자바 집합 에서 비교적 중요 한 집합 프레임 워 크 입 니 다. 특징: 키 값 은 저장 소, key 는 null 로 검색 속도 가 빠 르 지만 스 레 드 는 안전 하지 않 습 니 다.
hashMap 의 클래스 관계

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

Map

hashMap 의 데이터 구조
jdk 1.6 에서 HashMap 은 table 배열 (비트 통) + 단 방향 링크 로 이 루어 집 니 다. 돌, 같은 hash 값 의 링크 는 모두 하나의 링크 에 저 장 됩 니 다.그러나 한 통 에 있 는 요소 가 비교적 많다. 즉, hash 값 이 같은 요소 가 많 을 때 key 값 을 통 해 순서대로 찾 는 효율 이 비교적 낮다.
한편, JDK 1.8 에서 HashMap 은 비트 통 + 링크 + 레 드 블랙 트 리 로 이 루어 졌 고 링크 길이 가 한도 값 (8) 을 초과 할 때 링크 를 레 드 블랙 트 리 로 전환 하여 검색 시간 을 크게 줄 였 다.
알고리즘 구현
1. 우선 hash 알고리즘
hash 알고리즘 정밀 설명, 링크 전송 문

   public native int hashCode();       

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

2. node 노드

  static class Node implements Map.Entry {
        final int hash; //hash hash for key
        final K key; //key
        V value; //value
        Node next;//    

3. 알고리즘 삽입
키 가 비어 있 을 때 jdk 1.6 의 방법 은 putForNullKey 입 니 다. 1.8 에서 정책 을 찾 지 못 했 습 니 다.

키 값 이 배열 tab [] 에 비어 있 거나 null 인지 판단 합 니 다. 그렇지 않 으 면 resize ();

키 키 키 키 에 따라 hash 가 삽입 할 수 있 는 배열 색인 i 를 계산 합 니 다. tab [i] = null 이 있 으 면 새 노드 를 추가 합 니 다. 그렇지 않 으 면 3

으로 넘 어 갑 니 다.

현재 배열 에서 hash 충돌 을 처리 하 는 방식 이 링크 인지 빨 간 검 은 나무 인지 판단 하고 각각 처리 합 니 다.

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

  
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //  tab      0，     resize()
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
             //(n - 1) & hash  put  ，    ,   put
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                //    AVL   ，                             ，           。
                 //         
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
              //       
               for (int binCount = 0; ; ++binCount) {
                   //p       ,      
                   if ((e = p.next) == null) {
                       //e  ，           key     ，     
                       p.next = newNode(hash, key, value, null);
                       //               ，           ,         ,
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
                           treeifyBin(tab, hash); 
                       break;
                   }
                   //  null==null
                   if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                       break;
                   p = e;//  p       
               }
           }
           //  hash  key       Value 
           if (e != null) { // existing mapping for key
               V oldValue = e.value;
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
               afterNodeAccess(e);
               return oldValue;
           }
       }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

찾다

       index,  
    //     Key
    //    object
     * 
    public V get(Object key) {
        Node e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
     * 
     * final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
         //hash & (length-1)        ,
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)//      ,               ，     
                    return ((TreeNode)first).getTreeNode(hash, key);
                do {//     ,    table  key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

 *
 */