HashMap源码解析（JDK1.7和JDK1.8）

ゞ浴缸里的玫瑰 2022-05-19 10:15 268阅读 0赞

### **注意：图片截至他人博客，请谅解，如介意，请联系我删除！** ###

### **参考文档：[http://www.importnew.com/28263.html][http_www.importnew.com_28263.html]** ###

### **                 [https://blog.csdn.net/dou\_yuan/article/details/77675872][https_blog.csdn.net_dou_yuan_article_details_77675872]** ###

### **一、简述各种数据结构在JDK中的使用** ###

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>数据结构</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>存储特点</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>新增时间复杂度</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>删除时间复杂度</strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong>查找时间复杂度</strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong>JDK中使用的该结构的类</strong></h3> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>数组</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>采用一段连续的存储单元来存储数据</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>O(n)</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>O(n)</strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong>O(1)（给定下标查找）/ O(n)（给定值查找）/<span style="color:#333333;"> O(logn)</span><span style="color:#333333;">（使用二分查找）</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong>ArrayList</strong></h3> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>线性链表</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>采用一组地址任意的存储单元存放数据元素</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(1)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(1)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(</span><span style="color:#333333;">n</span><span style="color:#333333;">)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong>LinkedList</strong></h3> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>二叉树</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>进行树状存储</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(logn)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(logn)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(logn)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong>TreeSet、TreeMap</strong></h3> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>哈希表（底层还是数组，使用哈希函数将关键字映射到数组的某个位置）</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong>采用关键码值映射到表中的一个位置来进行存储数据</strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(1)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.5pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(1)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong><span style="color:#333333;">O(1)</span></strong></h3> </td> 
   <td style="vertical-align:top;width:72.55pt;"> <h3 style="margin-left:0mm;"><strong>HashMap</strong></h3> </td> 
  </tr> 
 </tbody> 
</table>

### **二、HashMap(线程不安全类)** ###

### **1）JDK1.7版本的HashMap类** ###

### **①Map结构：key-value结构，常用于在内存中存放数据。** ###

### **②HashMap的底层是基于数组+链表组成的。** ###

### **③HashMap在遇到哈希冲突（对某元素进行哈希运算的时候，得到的存储地址已经被占用了）的时候，HashMap使用了链地址法（使用链表来解决该问题，链表越少，HashMap性能越好）解决该问题** ###

### **④JDK1.7的HashMap的数据结构图：** ###

### **![70][]** ###

### **⑤HashMap底层的数组，在jdk7中使用的默认初始化容量是16，负载因子是0.75，也就是当数量达到了16\*0.75=12的时候，就需要将当前16的容量进行扩容了，扩容需要进行reHash、复制数据等操作（这些操作极其消耗性能，故最好提前预估好HashMap的大小，尽量减少扩容的次数）。** ###

### **⑥jdk7底层中真正用来存储数据的数组** ###

### **   transient Entry<K,V>\[\] table = (Entry<K,V>\[\]) EMPTY\_TABLE;  //创建一个长度为Capacity的Entry数组，这个长度被称为容量(Capacity)。数组中每个存放元素的位置称为“桶”，每一个桶有自己的索引，一个桶存储一个Entry链。** ###

### **注意：Entry是HashMap的一个内部类，Entry类说明** ###

### **          1）实现了Map.Entry<K,V>接口。** ###

### **          2）成员变量：1、key：写入的键。** ###

### **                                  2、value：写入的值。** ###

### **                                  3、next：实现链表结构，存储指向下一个Entry的引用** ###

### **                                  4、hash：当前key的hashcode。** ###

### **⑦存储的规则一般是** ###

### **    hash(key)%len获得，就是元素的key的哈希值对数组的长度取模得到。** ###

### **⑧存储键值对时，实际上是存储在一个Entry对象中，通过key计算出Entry对象的存储位置。** ###

### **    Key -->Value的对应关系，通过key-->Entry--->value实现。** ###

## ##

### **2）JDK1.8版本的HashMap** ###

### **①HashMap的结构，使用了红黑树和链表** ###

### **![70 1][]** ###

### **注意：1、当链表节点较少时仍然是以链表存在，当链表节点较多时（大于8）会转为红黑树。** ###

### **           2、得到key对应的hash值时，hash&(cap-1)得到该hash值对应的位置，故当数组长度不为2的幂次方时，才不会发生冲突。** ###

### **②public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable** ###

### **    HashMap继承了AbstractMap类，并且实现了Map、Cloneable、Serializable接口，故可以被序列化，该类也使用了原型模式** ###

## ##

### **③HashMap类中的常量** ###

//默认初始化容量大小为16    
        static final int DEFAULT_INITIAL_CAPACITY = 16;   
        
        //最大容量为2^30
        static final int MAXIMUM_CAPACITY = 1073741824;
        
        //默认装载因子是0.75，装载因子过大时，填入新的元素时,冲突的机会将很大,查找的成本高
        //装载因子过小时，空间浪费
        static final float DEFAULT_LOAD_FACTOR = 0.75F;
        
        //链表节点转换红黑树节点的阀值，8个节点就转为红黑树
        static final int TREEIFY_THRESHOLD = 8;
        
        //红黑树节点转换链表节点的阀值，6个节点转为链表
        static final int UNTREEIFY_THRESHOLD = 6;
        
        //转红黑树时，table的最小长度为64
        static final int MIN_TREEIFY_CAPACITY = 64;

## ##

### **④HashMap中的定义的变量** ###

//节点表(数组的每一个位置上存储一个节点表)  
         transient Node<K, V>[] table;
        
         //Entry集合
         transient Set<Entry<K, V>> entrySet;
        
         //映射对的数量
         transient int size;
        
         //修改的次数（发生变化的次数）
         transient int modCount;
        
         //resize的临界值(=capacity*loadFactor)
         int threshold;
        
         //装载因子
         final float loadFactor;

### **⑤构造方法** ###

### **    1、四大构造方法** ###

//构造方法参数
    //initialCapacity: 初始化容量
    //loadFactor: 加载因子
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0){
          throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        }else{
           if (initialCapacity > MAXIMUM_CAPACITY){
                initialCapacity = MAXIMUM_CAPACITY;
           }
           if (loadFactor <= 0 || Float.isNaN(loadFactor)){
               throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
           }
           this.loadFactor = loadFactor;
           //调用tableSizeFor方法, 该方法的作用是将输入的initialCapacity修改为相近的2的幂次方数, 因为HashMap的容量必须为2的幂次方，例：15----2^4
           this.threshold = tableSizeFor(initialCapacity);
      }
    }
    
    //采用默认的加载因子
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    //采用默认的capacity、loadFactor
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    
    //创建一个内容为参数m的内容的哈希表
    //采用默认的加载因子
    public HashMap(Map<? extends K, ? extends V> m) {
           this.loadFactor = DEFAULT_LOAD_FACTOR;
           this.putMapEntries(m, false);
    }

### **  2、构造方法中用到得方法** ###

### **    a、putMapEntries方法：将整个集合中的数据放到HashMap中保存** ###

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            //数组还是空，初始化参数
            if (table == null) { 
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            //数组不为空，超过阈值就扩容
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                //先经过 hash() 计算位置，然后复制指定 map 的内容
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

### ** b、tableSizeFor()：HashMap的容量只能是2的幂次方，该方法将传入的参数转为最近的2的幂次方的数作为容量进行初始化。** ###

static final int tableSizeFor(int 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;
    }

### **⑥内部静态类：Node类------保存键值对** ###

//保存key-value的节点类 
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash; //保存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;
            }
    
            public final K getKey(){ 
                  return key; 
            }
            public final V getValue(){ 
                  return value; 
            }
            public final String toString(){ 
                  return key + "=" + value; 
            }
    
            //返回key的hash值和key的hash值的异或结果
            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;
            }
        }

### **⑦HashMap中的添加方法put方法和putVal方法** ###

### **  1、putVal()方法** ###

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;  //当数组table为null时, 调用resize生成数组table, 并令tab指向数组table
            if ((p = tab[i = (n - 1) & hash]) == null)  //如果新存放的hash值没有冲突
                tab[i] = newNode(hash, key, value, null);  //则只需要生成新的Node节点并存放到table数组中即可
            else {  //否则就是产生了hash冲突
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k)))) 
                    e = p;  //如果hash值相等且key值相等, 则令e指向冲突的头节点
                else if (p instanceof TreeNode)  //如果头节点的key值与新插入的key值不等, 并且头结点是TreeNode类型,说明该hash值冲突是采用红黑树进行处理.
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //向红黑树中插入新的Node节点
                else {  //否则就是采用链表处理hash值冲突
                    for (int binCount = 0; ; ++binCount) {  //遍历冲突链表, binCount记录hash值冲突链表中节点个数
                        if ((e = p.next) == null) {  //当遍历到冲突链表的尾部时
                            p.next = newNode(hash, key, value, null);  //生成新节点添加到链表末尾
                            if (binCount >= TREEIFY_THRESHOLD - 1) //如果binCount即冲突节点的个数大于等于 (TREEIFY_THRESHOLD(=8) - 1),便将冲突链表改为红黑树结构, 对冲突进行管理, 否则不需要改为红黑树结构
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))  //如果在冲突链表中找到相同key值的节点, 则直接用新的value覆盖原来的value值即可
                            break;
                        p = e;
                    }
                }
                if (e != null) { // 说明原来已经存在相同key的键值对
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)  //onlyIfAbsent为true表示仅当<key,value>不存在时进行插入, 为false表示强制覆盖;
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;  //修改次数自增
            if (++size > threshold) //当键值对数量size达到临界值threhold后, 需要进行扩容操作.
                resize();
            afterNodeInsertion(evict);
            return null;
        }

### **2、put方法** ###

//添加指定的键值对到 Map 中，如果已经存在，就替换
    public V put(K key, V value) {
        //调用 hash() 计算位置
        //调用putVal()方法进行保存key-value
        return putVal(hash(key), key, value, false, true);
    }

### **⑧扩容方法resize():** ###

### **     注意：1、该方法在size到达阀值时，进行调用。** ###

### **                2、最好在初始化的时候制定好HashMap的场地，避免频繁的resize()扩容。** ###

final Node<K,V>[] resize() {
        //保存当前的节点集合数据
        Node<K,V>[] oldTab = table;
        //保存旧的元素个数
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //保存旧的扩容阀值
        int oldThr = threshold;
        //设置新的容量、扩容阀值
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //旧的容量大于最大容量
            if (oldCap >= MAXIMUM_CAPACITY) {
                //扩容阀值设为Integer的最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //新的容量为旧的容量的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //如果旧容量小于等于16，新的阈值就是旧阈值的两倍
                newThr = oldThr << 1; 
        }
        //如果旧容量为 0 ，并且旧阈值>0，说明之前创建了哈希表但没有添加元素，初始化容量=阈值
        else if (oldThr > 0) 
            newCap = oldThr;
        else {               
            //旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值=容量*加载因子
            newCap = DEFAULT_INITIAL_CAPACITY;  
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //如果新的阈值为 0 ，就得用 新容量*加载因子 重新计算一遍
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //更新阈值
        threshold = newThr;
        //创建新链表数组，容量是原来的两倍
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //将新数组给变量table
        table = newTab;
        //将暂存旧数据的OldTab变量的数据遍历复制回table变量
        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)
                        //e.hash & (newCap - 1)=e.hash % newCap，重新索引
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //如果旧哈希表中这个位置的桶是树形结构，就要把新哈希表里当前桶也变成树形结构
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
                        //保留旧哈希表桶中链表的顺序
                        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;
    }

### **⑨将冲突链表改为红黑树(默认大于等于7的情况下)** ###

//该方法的主要作用是将冲突链表改为红黑树
    final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; 
            Node<K,V> e;
    //当数组的长度<MIN_TREEIFY_CAPACITY(64) 时,只是单纯将数组扩容, 不将冲突链表改为红黑树
    //由于hash数组长度还太小时，导致的多冲突,通过 增大hash数组长度可以改善冲突情况
            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;
                //遍历Node链
                do {
                    //将Node对象转为Node对象
                    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);
            }
        }

### **⑩获取Value** ###

### **   1、getNode()方法** ###

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; 
            Node<K,V> first, e; 
            int n; 
            K k;
            //e.hash & (newCap - 1)=e.hash % newCap ，得到目标的位置
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {  //first指向hash值对应数组位置中的Node节点
                if (first.hash == hash && // 如果first节点对应的hash和key的hash相等(在数组相同位置,只是说明 hash&(n-1) 操作结果相等, 说明hash值的部分低位相等, 并不代表整个hash值相等), 并且first对应的key也相等的话, first节点就是要查找的
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {  //存在hash冲突
                    if (first instanceof TreeNode)  //由红黑树对hash值冲突进行管理
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);  //查找红黑树
                    do {  //hash值冲突是由链表进行管理
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);  //对链表进行遍历
                }
            }
            return null;
        }

### **  2、get()方法** ###

public V get(Object key) {
            Node<K,V> e;
            //调用getNode，通过hash值和key来获得对应的值，如果没有，返回null
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

### **⑪删除某键值对** ###

### **1、removeNode方法** ###

//参数hash为key的hash值;
    //参数key为要删除的key键;
    //参数value为key对应的value;
    //参数matchValue为true表明只有key在HashMap中对应值为value时才删除; 为false表示强制删除;
    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) {   //在table中查找对应hash值
                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) {   //说明hash值存在冲突
                    if (p instanceof TreeNode)   //hash值冲突由红黑树进行管理
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);   //查找红黑树并返回该节点
                    else {   //hash值冲突由链表管理
                        do {
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) {
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) {
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);  //从红黑树中删除该节点
                    else if (node == p)
                        tab[index] = node.next;   //直接修改
                    else
                        p.next = node.next;   //修改冲突链表
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

### **2、remove方法** ###

//删除key对应的键值对
        public V remove(Object key) {
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }

### **⑫hash方法：根据key来计算** ###

static final int hash(Object key) {
        int h;
        //key不为null的情况下，返回key的哈希码异或上key哈希码进行无符号右移16位的结果
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

### **![70 2][]** ###

### **图片来自（[http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/][http_yikun.github.io_2015_04_01_Java-HashMap_E5_B7_A5_E4_BD_9C_E5_8E_9F_E7_90_86_E5_8F_8A_E5_AE_9E_E7_8E_B0]）** ###

### **原因：避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。** ###

## ##

[http_www.importnew.com_28263.html]: http://www.importnew.com/28263.html
[https_blog.csdn.net_dou_yuan_article_details_77675872]: https://blog.csdn.net/dou_yuan/article/details/77675872
[70]: /images/20220519/a3a986df9a3a4fa19660df8466c8c18b.png
[70 1]: /images/20220519/e1393d629a8b458399ccc0a7f0b17fe2.png
[70 2]: /images/20220519/36e2f0e0439342019ce0bd12cc5e61cd.png
[http_yikun.github.io_2015_04_01_Java-HashMap_E5_B7_A5_E4_BD_9C_E5_8E_9F_E7_90_86_E5_8F_8A_E5_AE_9E_E7_8E_B0]: http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/