HashMap的工作原理 - JDK1.8

二、HashMap数据结构打开HashMap.java文件，找到以下代码块，这个就是HashMap存放数据的对象，可以看出它就是一个“链表”的数组。

/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some Operations to allow * bootstrapping mechanics that are currently not needed.) */transient Node<K,V>[] table;再来看看Node<K,V>（链表）的定义，我将注释直接写在代码上。
/** * Basic hash bin node, used for most entries.  (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */static class Node<K,V> implements Map.Entry<K,V> {        final int hash;//hash(key)返回的值        final K key;//键        V value;//值        Node<K,V> next;//链表的关键，naxt中装载着下一个链表        //类构造方法，初始化操作        Node(int hash, K key, V value, Node<K,V> next) {            this.hash = hash;            this.key = key;            this.value = value;            this.next = next;        }        public final K getKey()        { return key; }        public final V getValue()      { return value; }        public final String toString() { return key + "=" + value; }        //返回hashCode，使用异或算法        public final int hashCode() {            return Objects.hashCode(key) ^ Objects.hashCode(value);        }        public final V setValue(V newValue) {            V oldValue = value;            value = newValue;            return oldValue;        }        public final 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()))                    return true;            }            return false;        }}作者：韦庆明链接：https://zhuanlan.zhihu.com/p/25266385来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。很多人可能不是很理解“链表”这个概念，我们可以想象一下一根链子的特性：
1、一个环套着另外1个圈，串成一条链。
2、一个环只能关联到左右2个环，头、尾部只能关联1个。
而上面的代码中，Node<K,V> next 字段中装载着下一个链表。next 中的 next 又可以装载着下下个链表，一环套一环，这就是链表的实现原理。
三、HashMap的存储和读取
1） 数组元素存储规则HashMap是按什么规则存放到数组中的呢？
在JDK1.8之前貌似是按照 hash(key)%len（除余） 来获取数组下标，并存放到此位置。JDK1.8之后，按照 (len-1) & hash（“与”运算） 来获取数组下标，并存放到此位置，HashMap作者这样做的思路没有表述出来，是因为这个算法的能减少冲突？当然，不管是使用 hash(key)%len还是(len-1) & hash 来计算元素存放位置下标，都会存在一个问题，就是如果数组中这个位置存在数据了，怎么办？这就是HashMap选择使用数组+链表来实现的好处，如数组下标3的位置存在了数据，那么新插入的数据会存放在这个数组位置的链表的末端。注解：len=数组长度图解，数组下标计算公式使用 hash(key)%len（除余） （讲解时候用，比较好找规律）
到此我们大致明白HashMap的数据结构与存放规则了。接下来我们从代码上一步步解读它的具体实现。2） put 代码解读put() 方法代码，注释写在代码中。
/** * Associates the specified value with the specified key in this map. * If the map PReviously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or *         <tt>null</tt> if there was no mapping for <tt>key</tt>. *         (A <tt>null</tt> return can also indicate that the map *         previously associated <tt>null</tt> with <tt>key</tt>.) */public V put(K key, V value) {    //执行putVal方法，并返回相应的结果    //执行方法前，先执行hash()方法获取hash    return putVal(hash(key), key, value, false, true);}hash() 方法代码，注释写在代码中。
/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower.  Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.)  So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */static final int hash(Object key) {    int h;    //使用三目运算，判断key=null则等于0，这就表示key=null值的都存放[0]位置。    //否则等于key.hashCode() ^(异或) (key.hashCode() >>>(右移) 16)后的值。    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}putVal() 方法代码，put的逻辑都写在此方法中，注释写在代码中。吐槽一下JDK1.8 HashMap的作者，把参数赋值和 if 判断放到一起，看着真累。
/** * 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 * @param evict if false, the table is in creation mode. * @return previous value, or null if none */final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    //参数字段注释：    //tab = 主数据集数组对象，p = 主数据集数组中某元素    //n = 主数据集数组长度，i = 新数据插入位置    Node<K,V>[] tab; Node<K,V> p; int n, i;    //判断table等于null 或 table数组长度等于 0     if ((tab = table) == null || (n = tab.length) == 0)        //执行resize()方法，初始化table，给tab参数赋值，并返回长度给 n 参数        n = (tab = resize()).length;    //给 i 赋值为 n-1 &(与运算) hash 后的值，并将 i 位置的元素赋值给 p 参数    //最后判断 p 是否等于null    if ((p = tab[i = (n - 1) & hash]) == null)                // p = null 表示数组中这个位置还没有数据，那么直接插入到这个位置        tab[i] = newNode(hash, key, value, null);    // p != null，那么就说明数组的 i 位置已经有数据了，执行以下操作    else {        //参数字段注释：e = 主数据集数组中某元素，k = 某元素中的key        Node<K,V> e; K k;        //条件标识名称：JudgeExistence（后面可以引用）        //判断规则：必须条件1：p.hash 等于 hash(传入添加)         //条件2：p.key 等于 key(传入添加)        //条件3：key(传入添加) != null 与 key(传入添加)值 等于 p.key值        //只要符合1+2 或 1+3条件，则判定这个key的数据已经存在        //判断期间 k 赋值为 p.key        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            //将 e 赋值为 p            e = p;        //判断 p 是否为 TreeNode 类型        else if (p instanceof TreeNode)            //调用putTreeVal()方法，将返回值赋值 e             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        else {            //执行无条件的 for 循环方法            for (int binCount = 0; ; ++binCount) {                //判断 p.next == null，表示可以在链表中这个位置插入新数据                //并将 e 赋值 为 p.next                if ((e = p.next) == null) {                    //将新数据插入到链表的末端                    p.next = newNode(hash, key, value, null);                    //判断循环次数 >= TREEIFY_THRESHOLD(8)-1                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        //执行 treeifyBin() 方法                        treeifyBin(tab, hash);                    //将新数据插入到链表的末端后，停止循环                    break;                }                //判断条件直接引用条件标识名称：JudgeExistence                //判断期间 k 赋值为 e.key                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    //找到相同key的数据，停止循环                    break;                //将 p 赋值为 e ，用于下一次循环判断                p = e;            }        }        //判断e 是否成功获取到数据        if (e != null) { // existing mapping for key            V oldValue = e.value;            //判断可修改value 标识参数 onlyIfAbsent 是否等于 false            //或 e.value 是否等于 null，只要符合一项条件就可以修改            if (!onlyIfAbsent || oldValue == null)                //覆盖原value                e.value = value;            afterNodeaccess(e);            return oldValue;        }    }    //HashMap结构被修改的次数，此次数不包括相同key被覆盖修改的次数    ++modCount;    //判断 键值映射的数目 > （容量*负载因子）上次设置的最大容量    if (++size > threshold)        //重新设置容量（在原有基础上*2）        //resize()有两个主要功能，一是初始化table，二是将table容量*2        resize();    afterNodeInsertion(evict);    return null;}
总结 put 的工作流程：
检查两个key是否一致的条件：
A = （已经插入的Entity），B = （即将插入的Entity）必须条件1：A.hash 等于 B.hash条件2：A.key 等于 B.key条件3：B.key 不等于 null 与 B.key值.equals(A.key值)只要符合1+2 或 1+3条件，则判定这个key的数据已经存在
1、table数组等于 null 或 table数组长度等于 0 时，会为其执行初始化操作。
2、使用 (len-1) & hash（“与”运算）计算出数组下标后，检查数组此下标位置是否存在数据，不存在则直接插入数据到该位置。
3、如果第 2 步操作检查到数据已经存在，检查即将插入的 key 在 HashMap 中已经存在后，会覆盖此位置原数据的 value，key不会被覆盖 。
4、如果第 3 步判断不成立，那么判断 此下标位置 是否为 TreeNode 类型，是则获取putVal版本树中的数据，并覆盖此位置原数据的 value，key不会被覆盖 。
5、以上判断都不成立，那么循环数组中此下标位置的链表。
5-1、循环链表，检查到 next 值等于 null ，则将数据插入到此位置。最先加入的数据在链头，新加入的数据在链尾。
5-2、循环链表，检查到即将插入的 key 在链表中已经存在后，会覆盖此位置原数据的 value，key不会被覆盖 。
6、判断 键值映射的数目 > （容量*负载因子）上次设置的最大容量值的时候，重新设置容量（在原有基础上*2）。（注：这一步只在数据插入操作时候执行，覆盖操作时候不执行）
3） get 代码解读get() 方法代码，注释写在代码中。
/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}.  (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */public V get(Object key) {    Node<K,V> e;    //e = getNode(hash(key), key)    return (e = getNode(hash(key), key)) == null ? null : e.value;}getNode() 方法代码，get逻辑代码写在此方法内，注释写在代码中。
/** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */final Node<K,V> getNode(int hash, Object key) {    //参数字段注释：    //tab = 主数据集数组对象，first,e = 主数据集数组中某元素    //n = 主数据集数组长度，k = tab[x].key    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;    //判断table不等于null 与 tab.length大于 0 与     //tab[(len-1) & hash] 此下标位置的数据不等于null    //判断期间，tab赋值为table，n 赋值为tab.length，first 赋值为tab[x]    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        //条件标识名称：JudgeExistence（后面可以引用）        //判断必要条件1：first.hash（上一步获取到的） 等于 hash（传入的）        //条件2：first.key 等于 key（传入的）        //条件3：key（传入的） 不等于 null 与 key值（传入的）等于 first.key值        //只要符合1+2 或 1+3条件，则判定这个key的数据存在        //判断期间 k 赋值为 first.key        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            //返回Node<K,V>数据            return first;        //上个判断不成立，则从链表中找这个数据        //判断下一个链表是否存在        //判断期间 e 赋值为 first.next        if ((e = first.next) != null) {            //判断first是否等于TreeNode类型            if (first instanceof TreeNode)                //是则从根节点种获取到这条数据，并返回                return ((TreeNode<K,V>)first).getTreeNode(hash, key);            //使用do... while循环查找链表，直到找到数据或循环到链表末端            do {                //判断条件直接引用条件标识名称：JudgeExistence                //判断期间 k 赋值为 e.key                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    //返回Node<K,V>数据                    return e;            } while ((e = e.next) != null);        }    }    return null;}
总结 get() 的工作流程：
相对于put ，get就要简单很多。
检查两个key是否一致的条件：
A = （已经插入的Entity），B = （即将插入的Entity）必须条件1：A.hash 等于 B.hash条件2：A.key 等于 B.key条件3：B.key 不等于 null 与 B.key值.equals(A.key值)只要符合1+2 或 1+3条件，则判定这个key的数据已经存在
它首先使用 (len-1) & hash 算法获取数组的下标，并使用 key 对比第一个链表的数据，如果匹配，返回该链表的数据。否则循环该数组下标内的所有链表，直至找到匹配的数据。
如果找不到匹配的数据，返回null 。
HashMap工作原理总结：
1、HashMap是链表+数组的结合体，它的核心对象就是一个链表的数组。
2、HashMap可以存储 null 的键值，键=null的时候会默认存放在 数组[0] 位置。
3、HashMap在JDK1.8后使用的数组下标算法为： (len-1) & hash（与运算）。
4、HashMap判断是否存在重复 key 的核心条件代码是：
if (e.hash == hash &&      ((k = e.key) == key || (key != null && key.equals(k))))
5、HashMap在出现重复 hash 值但 key 不同的时候，会将新数据插入到该数组下标中链表的末端。最先加入的数据在链头，新加入的数据在链尾。
6、HashMap在插入数据的时候，如果新数据的 key 已经存在，那么新数据将会覆盖原数据的 value 值，key不会被覆盖。
HashMap就讲到这里了，有时间再研究一下 resize() 方法吧。