HashMap

static final int hash(Object key){
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//扰动，这样前16位和后16位都会对hash值造成影响 
}

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>,Cloneable,Serializable{
    
    static class Node<K,V> implements Map.Entry<K,V>{
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        
        Node(int hash,K key,V value,Node<K,V> next){
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        

    
    transient Node<K,V>[] table;
    transient Set<Map.Entry<K,V>> entrySet;
    
    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)//非空，如果为空resize
            n = (tab = resize()).length;
        if((p = tab[i = (n-1) & hash]) == null)//数组坐标为length-1 与 hash的与（相当于坐标减一做一个掩码），没有被占就创建新节点
            tab[i] = newNode(hash,key,value,null);
        else{
            //该数组节点已经有值
            Node<K,V> e; K k;
            if(p.hash == hash && //节点相同则e=该节点
              ((key = p.key) == key || (key != null && key.equals(k))))
                e= p;
            else if(p instanceof TreeNode) //不同，如果该节点是树节点，新建树节点
                e = ((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value); 
            else{//既不是相同节点，也不是树节点
                for(int binCount = 0; ;  ++binCount){
                    if((e = p.next) == null){//遍历到最后一个节点，新建node
                        p.next = newNode(hash,key,value,null);
                        if(binCount >= TREEIFY_THRESHOLD - 1) //如果节点数大于域值，转红黑树
                            treeifyBin(tab,hash);
                        break;
                    }
                    if(e.hash == hash &&(k = e.key) == key || (key!= null && key.equals(k))))
                        break;//遍历到相同节点，跳出循环
                    p = e;
                }
            }
            if(e!= null){
                V oldValue= e.value;
                if(! onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if(++size > shreshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
}

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

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;
      boolean red;
      TreeNode(int hash,K key,V val,Node<K,V> next){
          super(hash,key,val,next);
      }
            
      final TreeNode<K,V> root(){
            for(TreeNode<K,V> r = this,p;;){
                if((p = r.parent) == null)
                   return r;
                r = p;
            }
        }
     }
        
     public final int hashCode(){
         return Objects.hashCode(key) ^ Objects.hashCode(value);
     }
}
    

/**
* 新增红黑树节点
*/

final TreeNode<K,V> putTreeVal(HashMap<K,V> map,Node<K,V>[] tab
                              ,int h, K k,V v){
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root =  (parent != null) ? root() : this;
    for(TreeNode<K,V> p = root;;){//获取根节点p
        int dir,ph; K pk;
        if((ph = p.hash) > h) //根节点hash大于当前节点hash dir=-1
            dir = -1;
        else if (ph < h)   //根节点hash小于当前节点hash dir=1
            dir = 1;
        else if((pk = p.key) == || (k != null && k.equals(pk))) //根节点和添加节点相同
            return p;
        else if((kc == null && (kc = comparableClassFor(k)) == null) || 
               (dir = compareComparables(kc,k,pk)) == 0){
            if(!searched){
                TreeNode<K,V> q,ch;
                searched = true;
                if(((ch = p.left) != null &&
                   (q = ch.find(h,k,kc)) != null) ||
                  ((ch = p.right) != null && 
                  (q = ch.find(h,k,kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k,pk);
        }
        
        TreeNode<K,V> xp = p;
        if((p = (dir <= 0) ? p.left : p.right) == null){
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h,k,v,xpn);
            if(dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if(xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            moveRootToFront(tab,balanceInsertion(root,x));
            return null;     
        }
    }
}