static class Node<K,V> implements Map.Entry<K,V> {
　　　　　// hash 值
        final int hash;
        final K key;
        V value;
　　　　　 指向下一个节点
        Node<K,1)"> next;

        Node(int hash,K key,V value,Node<K,1)"> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        final V getValue()      {  value; }
        final String toString() { return key + "=" + value; }
　　　　  返回：key的hashCode值和value的hashCode值进行异或运算结果
         hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

         V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
             oldValue;
        }

　　　　  判断相等的依据是，要么是同一个 Node 对象，要么是Map.Entry的一个实例，并且键键、值值都相等就返回True
　　　　 boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key,e.getKey()) &&
                    Objects.equals(value,e.getValue()))
                    ;
            }
            false;
        }
    }

    class HashMap<K,1)">extends AbstractMap<K,V>
         implements Map<K,V>,Cloneable,Serializable {

　　// Object   
　　protected Object clone() throws CloneNotSupportedException {
        if (!(this  Cloneable)) {
            throw new CloneNotSupportedException("Class " + getClass().getName() +
                                                 " doesn't implement Cloneable");
        }
         internalClone();
    }

     1 默认的构造函数
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;  all other fields defaulted
    }

     2 传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
    public HashMap(Map<? extends K,? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m,);
    }

     3 指定容量大小
    public HashMap( initialCapacity) {
        (initialCapacity,DEFAULT_LOAD_FACTOR);
    }

     4 指定容量大小和负载因子大小
    int initialCapacity,float loadFactor) {
        指定的容量大小不可以小于0,否则将抛出IllegalArgumentException异常
        if (initialCapacity < 0)
            new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
         判定指定的容量大小是否大于HashMap的容量极限
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
         指定的负载因子不可以小于0或为Null，若判定成立则抛出IllegalArgumentException异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            new IllegalArgumentException("Illegal load factor: " +
                     loadFactor);

         loadFactor;
         设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
        this.threshold = tableSizeFor(initialCapacity);
    }

int tableSizeFor( cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

;

/**
 * 当桶数组容量小于该值时，优先进行扩容，而不是树化
 */
class TreeNode<K,1)">extends LinkedHashMap.Entry<K,1)"> {
    TreeNode<K,V> parent;   red-black tree links
    TreeNode<K,1)"> left;
    TreeNode<K,1)"> right;
    TreeNode<K,V> prev;     needed to unlink next upon deletion
     red;
    TreeNode( next) {
        super(hash,val,next);
    }
}


 * 将普通节点链表转换成树形节点链表
 void treeifyBin(Node<K,V>[] tab,1)"> hash) {
    int n,index; Node<K,1)"> e;
     桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    if ((e = tab[index = (n - 1) & hash]) != ) {
         hd 为头节点（head），tl 为尾节点（tail）
        TreeNode<K,V> hd =  {
             将普通节点替换成树形节点
            TreeNode<K,V> p = replacementTreeNode(e,1)">);
            if (tl == )
                hd = {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);   将普通链表转成由树形节点链表
        if ((tab[index] = hd) !=  将树形链表转换成红黑树
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p,1)"> next) {
    new TreeNode<>(p.hash,p.key,p.value,next);
}

 红黑树转链表阈值
void split(HashMap<K,V> map,1)">int index,1)"> bit) {
    TreeNode<K,V> b =  Relink into lo and hi lists,preserving order
    TreeNode<K,1)">;
    TreeNode<K,1)">int lc = 0,hc = 0 
     * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
     * 下面的循环是对红黑树节点进行分组，与上面类似
     */
    for (TreeNode<K,V> e = b,next; e != null; e = next) {
        next = (TreeNode<K,1)">)e.next;
        e.next = if ((e.hash & bit) == 0if ((e.prev = loTail) == )
                loHead = e;
            
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        if ((e.prev = hiTail) == )
                hiHead =
                hiTail.next = e;
            hiTail =hc;
        }
    }

    if (loHead !=  如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
         {
            tab[index] = loHead;
             
             * hiHead == null 时，表明扩容后，
             * 所有节点仍在原位置，树结构不变，无需重新树化
             */
            if (hiHead != ) 
                loHead.treeify(tab);
        }
    }
     与上面类似
    if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
         {
            tab[index + bit] = hiHead;
            )
                hiHead.treeify(tab);
        }
    }
}

 map) {
    Node<K,1)"> 遍历 TreeNode 链表，并用 Node 替换
    for (Node<K,V> q = this; q != null; q = q.next) {
         替换节点类型
        Node<K,V> p = map.replacementNode(q,1)">)
            hd = p;
        
            tl.next = p;
        tl = p;
    }
     hd;
}

Node<K,V> replacementNode(Node<K,1)">new Node<>9. get 添加元素

  这里直接调用getNode函数实现方法
   V get(Object key) {
        Node<K,1)"> e;
        经过hash函数运算 获取key的hash值
        return (e = getNode(hash(key),key)) == null ?  : e.value;
    }
   
    hash,Object key) {
        Node<K,V> first,e;  n; K k;
        判定三个条件 table不为Null & table的长度大于0 & table指定的索引值不为Null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != 判定 匹配hash值 & 匹配key值 成功则返回 该值
            if (first.hash == hash && 
                ((k = first.key) == key || (key !=  key.equals(k))))
                 first;
             若 first节点的下一个节点不为Null
            if ((e = first.next) != ) {
                if (first 若first的类型为TreeNode 红黑树
                    通过红黑树查找匹配值 并返回
                    return ((TreeNode<K,1)">)first).getTreeNode(hash,key); 
                若上面判定不成功 则认为下一个节点为单向链表,通过循环匹配值
                 {
                     key.equals(k))))
                       匹配成功后返回该值
                         e;
                } );
            }
        }
        ;
    }


梳理以下 get 函数的执行过程


判定三个条件 table 不为 Null & table 的长度大于 0 & table 指定的索引值不为 Null，否则直接返回 null，这也是可以存储 null?


判定匹配 hash 值 & 匹配 key 值，成功则返回该值，这里用了 == 和 equals 两种方式，对于 int，string，同一个实例对象等可以适用。


若 first 节点的下一个节点不为 Null


若下一个节点类型为 TreeNode 红黑树，通过红黑树查找匹配值，并返回查询值


否则就是单链表，还是通过匹配 hash 值 & 匹配 key 值来获取数据。










































































































































10. remove?删除元素
当你看到了 get 获取元素的细节，在来看删除原理，其实大同小异。
HashMap 的删除操作并不复杂，仅需三个步骤即可完成。第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。相关源码如下：

 V remove(Object key) {
    Node<K,1)">return (e = removeNode(hash(key),1)">true)) == null ?
         : e.value;
}

boolean matchValue,1)"> movable) {
    Node<K,index;
    null && (n = tab.length) > 0 &&
         1. 定位桶位置
        (p = tab[index = (n - 1) & hash]) != ) {
        Node<K,V> node =  如果键的值与链表第一个节点相等，则将 node 指向该节点
        
            ((k = p.key) == key || (key !=  key.equals(k))))
            node =if ((e = p.next) != ) {  
             如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
             TreeNode)
                node = ((TreeNode<K,1)">)p).getTreeNode(hash,key);
             {
                 2. 遍历链表，找到待删除节点
                
                        ((k = e.key) == key ||
                         (key !=  key.equals(k)))) {
                        node = e;
                        ;
                    }
                    p =);
            }
        }
        
         3. 到这里，已经找到了，删除节点，并修复链表或红黑树
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value !=  value.equals(v)))) {
            if (node  TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(if (node == p)
                tab[index] = node.next;
            
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
             node;
        }
    }
　　 // 找不到，或者没有数据，返回 null
    ;
}

删除操作本身并不复杂，有了前面的基础，理解起来也就不难了，这里就不多说了。