【大数据】学习笔记 1 Java SE 第12章集合的重要接口 12.6 哈希表(了解)

小鱼儿 2024-03-22 14:06 58阅读 0赞

### 【大数据】学习笔记 ###

#### 文章目录 ####

*   *  【大数据】学习笔记
     *   *  1 Java SE
         *   *  第12章 集合的重要接口
             *   *  12.6 哈希表(了解)
                 *   *  12.6.1 hashCode值
                     *  12.6.2 哈希表的物理结构
             *  
             *   *   *  12.6.3 JDK1.7的put方法源码分析
                     *  12.6.4 JDK1.8的put方法源码分析
                     *  12.6.5 关于映射关系的key是否可以修改？

![在这里插入图片描述][9ea25366b09e44eebaa88a805e43cd01.png_pic_center]

#### 1 Java SE ####

##### 第12章 集合的重要接口 #####

###### 12.6 哈希表(了解) ######

HashMap和Hashtable都是哈希表。

###### 12.6.1 hashCode值 ######

hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意大小的数据映射到一个固定大小的序列上，这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的，唯一性是指相同的“对象”产生的hash code永远是一样的。

###### 12.6.2 哈希表的物理结构 ######

HashMap和Hashtable是散列表，其中维护了一个长度为**2的幂次方**的Entry类型的数组table，数组的每一个元素被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到了某个table\[index\]桶中。使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table\[index\]。

【1】数组元素类型：Map.Entry

JDK1.7：

映射关系被封装为HashMap.Entry类型，而这个类型实现了Map.Entry接口。

观察HashMap.Entry类型是个结点类型，即table\[index\]下的映射关系可能串起来一个链表。因此我们把table\[index\]称为“桶bucket"。

public class HashMap<K,V>{
        
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
        static class Entry<K,V> implements Map.Entry<K,V> {
        
                final K key;
                V value;
                Entry<K,V> next;
                int hash;
                //...省略
        }
        //...
    }

![在这里插入图片描述][416c514250024574974f6276dc28db60.png_pic_center]

JDK1.8：

映射关系被封装为HashMap.Node类型或HashMap.TreeNode类型，它俩都直接或间接的实现了Map.Entry接口。

存储到table数组的可能是Node结点对象，也可能是TreeNode结点对象，它们也是Map.Entry接口的实现类。即table\[index\]下的映射关系可能串起来一个链表或一棵红黑树。

public class HashMap<K,V>{
        
        transient Node<K,V>[] table;
        static class Node<K,V> implements Map.Entry<K,V> {
        
                final int hash;
                final K key;
                V value;
                Node<K,V> next;
                //...省略
        }
        static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;
            boolean red;//是红结点还是黑结点
            //...省略
        }
        //....
    }

public class LinkedHashMap<K,V>{
        
    	static class Entry<K,V> extends HashMap.Node<K,V> {
        
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
        
                super(hash, key, value, next);
            }
        }
        //...
    }

![在这里插入图片描述][701a1749feac469482560970d5a2f101.png_pic_center]

【2】那么HashMap是如何决定某个映射关系存在哪个桶的呢？

因为hash值是一个整数，而数组的长度也是一个整数，有两种思路：

①hash 值 % table.length会得到一个\[0,table.length-1\]范围的值，正好是下标范围，但是用%运算效率没有位运算符&高。

②hash 值 & (table.length-1)，任何数 & (table.length-1)的结果也一定在\[0, table.length-1\]范围。

hashCode值是   ？
    table.length是10
    table.length-1是9
    
    ？   ????????
    9	 00001001
    &_____________
    	 00000000	[0]
    	 00000001	[1]
    	 00001000	[8]
    	 00001001	[9]
    	 一定[0]~[9]

hashCode值是   ？
    table.length是16
    table.length-1是15
    
    ？   ????????
    15	 00001111
    &_____________
    	 00000000	[0]
    	 00000001	[1]
    	 00000010	[2]
    	 00000011	[3]
    	 ...
    	 00001111    [15]
    	 范围是[0,15]，一定在[0,table.length-1]范围内

JDK1.7：

static int indexFor(int h, int length) {
        
            // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
            return h & (length-1); //此处h就是hash
        }

JDK1.8：

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;
            if ((p = tab[i = (n - 1) & hash]) == null)  // i = (n - 1) & hash
                tab[i] = newNode(hash, key, value, null);
            //....省略大量代码
    }

【3】数组的长度始终是2的n次幂

table数组的默认初始化长度：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

如果你手动指定的table长度不是2的n次幂，会通过如下方法给你纠正为2的n次幂

JDK1.7：

HashMap处理容量方法：

private static int roundUpToPowerOf2(int number) {
        
            // assert number >= 0 : "number must be non-negative";
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }

Integer包装类：

public static int highestOneBit(int i) {
        
            // HD, Figure 3-1
            i |= (i >>  1);
            i |= (i >>  2);
            i |= (i >>  4);
            i |= (i >>  8);
            i |= (i >> 16);
            return i - (i >>> 1);
        }

JDK1.8：

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

如果数组不够了，扩容了怎么办？扩容了还是2的n次幂，因为每次数组扩容为原来的2倍

JDK1.7：

void addEntry(int hash, K key, V value, int bucketIndex) {
        
            if ((size >= threshold) && (null != table[bucketIndex])) {
        
                resize(2 * table.length);//扩容为原来的2倍
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
            createEntry(hash, key, value, bucketIndex);
        }

JDK1.8：

final Node<K,V>[] resize() {
        
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap原来的容量
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
        
                if (oldCap >= MAXIMUM_CAPACITY) {
        
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }//newCap = oldCap << 1  新容量=旧容量扩容为原来的2倍
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            	}
       		//......此处省略其他代码
    	}

那么为什么要保持table数组一直是2的n次幂呢？

因为如果数组的长度为2的n次幂，那么table.length-1的二进制就是一个高位全是0，低位全是1的数字，这样才能保证每一个下标位置都有机会被用到。

【4】hash是hashCode的再运算

不管是JDK1.7还是JDK1.8中，都不是直接用key的hashCode值直接与table.length-1计算求下标的，而是先对key的hashCode值进行了一个运算，JDK1.7和JDK1.8关于hash()的实现代码不一样，但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果，尽量的均匀分布。

JDK1.7：

final int hash(Object k) {
        
            int h = hashSeed;
            if (0 != h && k instanceof String) {
        
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
            h ^= k.hashCode();
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

JDK1.8：

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

虽然算法不同，但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或，然高位二进制参与到index的计算中。

为什么要hashCode值的二进制的高位参与到index计算呢？

因为一个HashMap的table数组一般不会特别大，至少在不断扩容之前，那么table.length-1的大部分高位都是0，直接用hashCode和table.length-1进行&运算的话，就会导致总是只有最低的几位是有效的，那么就算你的hashCode()实现的再好也难以避免发生碰撞，这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。

【5】解决\[index\]冲突问题

虽然从设计hashCode()到上面HashMap的hash()函数，都尽量减少冲突，但是仍然存在两个不同的对象返回的hashCode值相同，或者hashCode值就算不同，通过hash()函数计算后，得到的index也会存在大量的相同，因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办？

JDK1.8之间使用：数组+链表的结构。

JDK1.8之后使用：数组+链表/红黑树的结构。

即hash相同或hash&(table.lengt-1)的值相同，那么就存入同一个“桶”table\[index\]中，使用链表或红黑树连接起来。

![在这里插入图片描述][e6b032ffefc54c30bcbf041b4fa49807.png_pic_center]

【6】为什么JDK1.8会出现红黑树和链表共存呢？

因为当冲突比较严重时，table\[index\]下面的链表就会很长，那么会导致查找效率大大降低，而如果此时选用二叉树可以大大提高查询效率。

但是二叉树的结构又过于复杂，如果结点个数比较少的时候，那么选择链表反而更简单。

所以会出现红黑树和链表共存。

【7】什么时候树化？什么时候反树化？

#####  #####

static final int TREEIFY_THRESHOLD = 8;//树化阈值
    static final int UNTREEIFY_THRESHOLD = 6;//反树化阈值
    static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量

*  当某table\[index\]下的链表的结点个数达到8，并且table.length>=64，那么如果新Entry对象还添加到该table\[index\]中，那么就会将table\[index\]的链表进行树化。
 *  当某table\[index\]下的红黑树结点个数少于6个，此时，
    
     *  当继续删除table\[index\]下的树结点，最后这个根结点的左右结点有null，或根结点的左结点的左结点为null，会反树化
     *  当重新添加新的映射关系到map中，导致了map重新扩容了，这个时候如果table\[index\]下面还是小于等于6的个数，那么会反树化

package com.dingjiaxiong.map;
    
    /**
     * @Projectname: BigDataStudy
     * @Classname: MyKey
     * @Author: Ding Jiaxiong
     * @Date:2023/4/27 20:08
     */
    
    public class MyKey {
        
        int num;
    
        public MyKey(int num) {
        
            super();
            this.num = num;
        }
    
        @Override
        public int hashCode() {
        
            if (num <= 20) {
        
                return 1;
            } else {
        
                final int prime = 31;
                int result = 1;
                result = prime * result + num;
                return result;
            }
        }
    
        @Override
        public boolean equals(Object obj) {
        
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            MyKey other = (MyKey) obj;
            if (num != other.num)
                return false;
            return true;
        }
    
    }

测试类：

package com.dingjiaxiong.map;
    
    import org.junit.Test;
    
    import java.util.HashMap;
    
    /**
     * @Projectname: BigDataStudy
     * @Classname: TestHashMapMyKey
     * @Author: Ding Jiaxiong
     * @Date:2023/4/27 20:09
     */
    
    public class TestHashMapMyKey {
        
        @Test
        public void test1() {
        
            //这里为了演示的效果，我们造一个特殊的类，这个类的hashCode（）方法返回固定值1
            //因为这样就可以造成冲突问题，使得它们都存到table[1]中
            HashMap<MyKey, String> map = new HashMap<>();
            for (int i = 1; i <= 11; i++) {
        
                map.put(new MyKey(i), "value" + i);//树化演示
            }
        }
    
        @Test
        public void test2() {
        
            HashMap<MyKey, String> map = new HashMap<>();
            for (int i = 1; i <= 11; i++) {
        
                map.put(new MyKey(i), "value" + i);
            }
            for (int i = 1; i <= 11; i++) {
        
                map.remove(new MyKey(i));//反树化演示
            }
        }
    
        @Test
        public void test3() {
        
            HashMap<MyKey, String> map = new HashMap<>();
            for (int i = 1; i <= 11; i++) {
        
                map.put(new MyKey(i), "value" + i);
            }
    
            for (int i = 1; i <= 5; i++) {
        
                map.remove(new MyKey(i));
            }//table[1]下剩余6个结点
    
            for (int i = 21; i <= 100; i++) {
        
                map.put(new MyKey(i), "value" + i);//添加到扩容时，反树化
            }
        }
    }

###### 12.6.3 JDK1.7的put方法源码分析 ######

（1）几个关键的常量和变量值的作用：

初始化容量：

int DEFAULT_INITIAL_CAPACITY = 1 << 4;//16  目的是体现2的n次方

①默认负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

②阈值：扩容的临界值

int threshold;

threshold = table.length * loadFactor;

③负载因子

final float loadFactor;

负载因子的值大小有什么关系？

如果太大，threshold就会很大，那么如果冲突比较严重的话，就会导致table\[index\]下面的结点个数很多，影响效率。

如果太小，threshold就会很小，那么数组扩容的频率就会提高，数组的使用率也会降低，那么会造成空间的浪费。

public HashMap() {
        
        	//DEFAULT_INITIAL_CAPACITY：默认初始容量16
        	//DEFAULT_LOAD_FACTOR：默认加载因子0.75
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        }
        public HashMap(int initialCapacity, float loadFactor) {
        
            //校验initialCapacity合法性
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
            //校验initialCapacity合法性                                       initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            //校验loadFactor合法性
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    		//加载因子，初始化为0.75
            this.loadFactor = loadFactor;
            // threshold 初始为初始容量                                  
            threshold = initialCapacity;
            init();
        }

public V put(K key, V value) {
        
            //如果table数组是空的，那么先创建数组
            if (table == EMPTY_TABLE) {
        
                //threshold一开始是初始容量的值
                inflateTable(threshold);
            }
            //如果key是null，单独处理，存储到table[0]中，如果有另一个key为null，value覆盖
            if (key == null)
                return putForNullKey(value);
            
            //对key的hashCode进行干扰，算出一个hash值
        /*
        hashCode值      xxxxxxxxxx
       table.length-1   000001111
       
       hashCode值 xxxxxxxxxx  无符号右移几位和原来的hashCode值做^运算，使得hashCode高位二进制值参与计算，也发挥作用，降低index冲突的概率。
        */
            int hash = hash(key);
            
            //计算新的映射关系应该存到table[i]位置，
            //i = hash & table.length-1，可以保证i在[0,table.length-1]范围内
            int i = indexFor(hash, table.length);
            
            //检查table[i]下面有没有key与我新的映射关系的key重复，如果重复替换value
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            //添加新的映射关系
            addEntry(hash, key, value, i);
            return null;
        }
        private void inflateTable(int toSize) {
        
            // Find a power of 2 >= toSize
            int capacity = roundUpToPowerOf2(toSize);//容量是等于toSize值的最接近的2的n次方
    		//计算阈值 = 容量 * 加载因子
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            //创建Entry[]数组，长度为capacity
            table = new Entry[capacity];
            initHashSeedAsNeeded(capacity);
        }
    	//如果key是null，直接存入[0]的位置
        private V putForNullKey(V value) {
        
            //判断是否有重复的key，如果有重复的，就替换value
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        
                if (e.key == null) {
        
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            //把新的映射关系存入[0]的位置，而且key的hash值用0表示
            addEntry(0, null, value, 0);
            return null;
        }
        void addEntry(int hash, K key, V value, int bucketIndex) {
        
            //判断是否需要库容
            //扩容：（1）size达到阈值（2）table[i]正好非空
            if ((size >= threshold) && (null != table[bucketIndex])) {
        
                //table扩容为原来的2倍，并且扩容后，会重新调整所有映射关系的存储位置
                resize(2 * table.length);
                //新的映射关系的hash和index也会重新计算
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    		//存入table中
            createEntry(hash, key, value, bucketIndex);
        }
        void createEntry(int hash, K key, V value, int bucketIndex) {
        
            Entry<K,V> e = table[bucketIndex];
            //原来table[i]下面的映射关系作为新的映射关系next
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;//个数增加
        }

1、put(key,value)

（1）当第一次添加映射关系时，数组初始化为一个长度为**16**的\*\*HashMap E n t r y ∗ ∗ 的 数 组 ， 这 个 H a s h M a p Entry\*\*的数组，这个HashMap Entry∗∗的数组，这个HashMapEntry类型是实现了java.util.**Map.Entry**接口

（2）特殊考虑：如果key为null，index直接是\[0\],hash也是0

（3）如果key不为null，在计算index之前，会对key的hashCode()值，做一个hash(key)再次哈希的运算，这样可以使得Entry对象更加散列的存储到table中

（4）计算index = table.length-1 & hash;

（5）如果table\[index\]下面，已经有映射关系的key与我要添加的新的映射关系的key相同了，会用新的value替换旧的value。

（6）如果没有相同的，会把新的映射关系添加到链表的头，原来table\[index\]下面的Entry对象连接到新的映射关系的next中。

（7）添加之前先判断if(size >= threshold && table\[index\]!=null)如果该条件为true，会扩容

if(size >= threshold  &&  table[index]!=null){
        
    
    	①会扩容
    
    	②会重新计算key的hash
    
    	③会重新计算index
    
    }

（8）size++

![在这里插入图片描述][81866c658ea546cd8cc6c138cf8931de.png_pic_center]

2、get(key)

（1）计算key的hash值，用这个方法hash(key)

（2）找index = table.length-1 & hash;

（3）如果table\[index\]不为空，那么就挨个比较哪个Entry的key与它相同，就返回它的value

3、remove(key)

（1）计算key的hash值，用这个方法hash(key)

（2）找index = table.length-1 & hash;

（3）如果table\[index\]不为空，那么就挨个比较哪个Entry的key与它相同，就删除它，把它前面的Entry的next的值修改为被删除Entry的next

###### 12.6.4 JDK1.8的put方法源码分析 ######

几个常量和变量：
    （1）DEFAULT_INITIAL_CAPACITY：默认的初始容量 16
    （2）MAXIMUM_CAPACITY：最大容量  1 << 30
    （3）DEFAULT_LOAD_FACTOR：默认加载因子 0.75
    （4）TREEIFY_THRESHOLD：默认树化阈值8，当链表的长度达到这个值后，要考虑树化
    （5）UNTREEIFY_THRESHOLD：默认反树化阈值6，当树中的结点的个数达到这个阈值后，要考虑变为链表
    （6）MIN_TREEIFY_CAPACITY：最小树化容量64
    		当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。
    		当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容
    （7）Node<K,V>[] table：数组
    （8）size：记录有效映射关系的对数，也是Entry对象的个数
    （9）int threshold：阈值，当size达到阈值时，考虑扩容
    （10）double loadFactor：加载因子，影响扩容的频率

public HashMap() {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR; 
            // all other fields defaulted，其他字段都是默认值
        }

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }
    	//目的：干扰hashCode值
        static final int hash(Object key) {
        
            int h;
    		//如果key是null，hash是0
    		//如果key非null，用key的hashCode值 与 key的hashCode值高16进行异或
    		//		即就是用key的hashCode值高16位与低16位进行了异或的干扰运算
    		
    		/*
    		index = hash & table.length-1
    		如果用key的原始的hashCode值  与 table.length-1 进行按位与，那么基本上高16没机会用上。
    		这样就会增加冲突的概率，为了降低冲突的概率，把高16位加入到hash信息中。
    		*/
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        
            Node<K,V>[] tab; //数组
    		Node<K,V> p; //一个结点
    		int n, i;//n是数组的长度   i是下标
    		
    		//tab和table等价
    		//如果table是空的
            if ((tab = table) == null || (n = tab.length) == 0){
        
                n = (tab = resize()).length;
                /*
    			tab = resize();
    			n = tab.length;*/
    			/*
    			如果table是空的，resize()完成了①创建了一个长度为16的数组②threshold = 12
    			n = 16
    			*/
            }
    		//i = (n - 1) & hash ，下标 = 数组长度-1 & hash
    		//p = tab[i] 第1个结点
    		//if(p==null) 条件满足的话说明 table[i]还没有元素
    		if ((p = tab[i = (n - 1) & hash]) == null){
        
    			//把新的映射关系直接放入table[i]
                tab[i] = newNode(hash, key, value, null);
    			//newNode（）方法就创建了一个Node类型的新结点，新结点的next是null
            }else {
        
                Node<K,V> e; 
    			K k;
    			//p是table[i]中第一个结点
    			//if(table[i]的第一个结点与新的映射关系的key重复)
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k)))){
        
                    e = p;//用e记录这个table[i]的第一个结点
    			}else if (p instanceof TreeNode){
        //如果table[i]第一个结点是一个树结点
                    //单独处理树结点
                    //如果树结点中，有key重复的，就返回那个重复的结点用e接收，即e!=null
                    //如果树结点中，没有key重复的，就把新结点放到树中，并且返回null，即e=null
    				e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                }else {
        
    				//table[i]的第一个结点不是树结点，也与新的映射关系的key不重复
    				//binCount记录了table[i]下面的结点的个数
                    for (int binCount = 0; ; ++binCount) {
        
    					//如果p的下一个结点是空的，说明当前的p是最后一个结点
                        if ((e = p.next) == null) {
        
    						//把新的结点连接到table[i]的最后
                            p.next = newNode(hash, key, value, null);
    						
    						//如果binCount>=8-1，达到7个时
                            if (binCount >= TREEIFY_THRESHOLD - 1){
         // -1 for 1st
                                //要么扩容，要么树化
    							treeifyBin(tab, hash);
    						}
                            break;
                        }
    					//如果key重复了，就跳出for循环，此时e结点记录的就是那个key重复的结点
                if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))){
        
                            break;
    					}
                        p = e;//下一次循环，e=p.next，就类似于e=e.next，往链表下移动
                    }
                }
    			//如果这个e不是null，说明有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;
    		
    		//元素个数增加
    		//size达到阈值
            if (++size > threshold){
        
                resize();//一旦扩容，重新调整所有映射关系的位置
    		}
            afterNodeInsertion(evict);//什么也没干
            return null;
        }	
    	
       final Node<K,V>[] resize() {
        
            Node<K,V>[] oldTab = table;//oldTab原来的table
    		//oldCap：原来数组的长度
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
    		
    		//oldThr：原来的阈值
            int oldThr = threshold;//最开始threshold是0
    		
    		//newCap，新容量
    		//newThr：新阈值
            int newCap, newThr = 0;
            if (oldCap > 0) {
        //说明原来不是空数组
                if (oldCap >= MAXIMUM_CAPACITY) {
        //是否达到数组最大限制
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY){
        
    				//newCap = 旧的容量*2 ，新容量<最大数组容量限制
    				//新容量：32,64，...
    				//oldCap >= 初始容量16
    				//新阈值重新算 = 24，48 ....
                    newThr = oldThr << 1; // double threshold
    			}
            }else if (oldThr > 0){
         // initial capacity was placed in threshold
                newCap = oldThr;
            }else {
                       // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;//新容量是默认初始化容量16
    			//新阈值= 默认的加载因子 * 默认的初始化容量 = 0.75*16 = 12
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
        
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;//阈值赋值为新阈值12，24.。。。
    		
    		//创建了一个新数组，长度为newCap，16，32,64.。。
            @SuppressWarnings({
        "rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
    		
    		
            if (oldTab != null) {
        //原来不是空数组
    			//把原来的table中映射关系，倒腾到新的table中
                for (int j = 0; j < oldCap; ++j) {
        
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
        //e是table下面的结点
                        oldTab[j] = null;//把旧的table[j]位置清空
                        if (e.next == null)//如果是最后一个结点
                            newTab[e.hash & (newCap - 1)] = e;//重新计算e的在新table中的存储位置，然后放入
                        else if (e instanceof TreeNode)//如果e是树结点
    						//把原来的树拆解，放到新的table
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else {
         // preserve order
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
    						/*
    						把原来table[i]下面的整个链表，重新挪到了新的table中
    						*/
                            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;
        }	
    	
        Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        
    		//创建一个新结点
    	   return new Node<>(hash, key, value, next);
        }
    
        final void treeifyBin(Node<K,V>[] tab, int hash) {
        
            int n, index; 
    		Node<K,V> e;
    		//MIN_TREEIFY_CAPACITY：最小树化容量64
    		//如果table是空的，或者  table的长度没有达到64
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();//先扩容
            else if ((e = tab[index = (n - 1) & hash]) != null) {
        
    			//用e记录table[index]的结点的地址
                TreeNode<K,V> hd = null, tl = null;
    			/*
    			do...while，把table[index]链表的Node结点变为TreeNode类型的结点
    			*/
                do {
        
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;//hd记录根结点
                    else {
        
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
    			
                //如果table[index]下面不是空
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);//将table[index]下面的链表进行树化
            }
        }

1、添加过程

A. 先计算key的hash值，如果key是null，hash值就是0，如果为null，使用(h = key.hashCode()) ^ (h >>> 16)得到hash值；

B. 如果table是空的，先初始化table数组；

C. 通过hash值计算存储的索引位置index = hash & (table.length-1)

D. 如果table\[index\]==null，那么直接创建一个Node结点存储到table\[index\]中即可

E. 如果table\[index\]!=null

a) 判断table\[index\]的根结点的key是否与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），如果是那么用e记录这个根结点

b) 如果table\[index\]的根结点的key与新的key“不相同”，而且table\[index\]是一个TreeNode结点，说明table\[index\]下是一棵红黑树，如果该树的某个结点的key与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），那么用e记录这个相同的结点，否则将(key,value)封装为一个TreeNode结点，连接到红黑树中

c) 如果table\[index\]的根结点的key与新的key“不相同”，并且table\[index\]不是一个TreeNode结点，说明table\[index\]下是一个链表，如果该链表中的某个结点的key与新的key“相同”，那么用e记录这个相同的结点，否则将新的映射关系封装为一个Node结点直接链接到链表尾部，并且判断table\[index\]下结点个数达到**TREEIFY\_THRESHOLD(8)个，如果table\[index\]下结点个数已经达到，那么再判断table.length是否达到MIN\_TREEIFY\_CAPACITY(64)**，如果没达到，那么先扩容，扩容会导致所有元素重新计算index，并调整位置，如果table\[index\]下结点个数已经达到**TREEIFY\_THRESHOLD(8)个并table.length也已经达到MIN\_TREEIFY\_CAPACITY(64)**，那么会将该链表转成一棵自平衡的红黑树。

F. 如果在table\[index\]下找到了新的key“相同”的结点，即e不为空，那么用新的value替换原来的value，并返回旧的value，结束put方法

G. 如果新增结点而不是替换，那么size++，并且还要重新判断size是否达到threshold阈值，如果达到，还要扩容。

if(size > threshold ){
        
    	①会扩容
    
    	②会重新计算key的hash
    
    	③会重新计算index
    
    }

![在这里插入图片描述][c4fe1f17ce3d4bbfb11ebc43cd4c1729.png_pic_center]

2、remove(key)

（1）计算key的hash值，用这个方法hash(key)

（2）找index = table.length-1 & hash;

（3）如果table\[index\]不为空，那么就挨个比较哪个Entry的key与它相同，就删除它，把它前面的Entry的next的值修改为被删除Entry的next

（4）如果table\[index\]下面原来是红黑树，结点删除后，个数小于等于6，会把红黑树变为链表

###### 12.6.5 关于映射关系的key是否可以修改？ ######

映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。

这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。

JDK1.7：

public class HashMap<K,V>{
        
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
        static class Entry<K,V> implements Map.Entry<K,V> {
        
                final K key;
                V value;
                Entry<K,V> next;
                int hash; //记录Entry映射关系的key的hash(key.hashCode())值
                //...省略
        }
        //...
    }

JDK1.8：

public class HashMap<K,V>{
        
        transient Node<K,V>[] table;
        static class Node<K,V> implements Map.Entry<K,V> {
        
                final int hash;//记录Node映射关系的key的hash(key.hashCode())值
                final K key;
                V value;
                Node<K,V> next;
                //...省略
        }
        //....
    }

示例代码：

package com.dingjiaxiong.map;
    
    /**
     * @Projectname: BigDataStudy
     * @Classname: ID
     * @Author: Ding Jiaxiong
     * @Date:2023/4/27 20:12
     */
    
    public class ID {
        
        private int id;
    
        public ID(int id) {
        
            super();
            this.id = id;
        }
    
        @Override
        public int hashCode() {
        
            final int prime = 31;
            int result = 1;
            result = prime * result + id;
            return result;
        }
    
        @Override
        public boolean equals(Object obj) {
        
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            ID other = (ID) obj;
            if (id != other.id)
                return false;
            return true;
        }
    
        public int getId() {
        
            return id;
        }
    
        public void setId(int id) {
        
            this.id = id;
        }
    
    }

测试类：

package com.dingjiaxiong.map;
    
    import java.util.HashMap;
    
    /**
     * @Projectname: BigDataStudy
     * @Classname: TestHashMapID
     * @Author: Ding Jiaxiong
     * @Date:2023/4/27 20:12
     */
    
    public class TestHashMapID {
        
        public static void main(String[] args) {
        
            HashMap<ID, String> map = new HashMap<>();
            ID i1 = new ID(1);
            ID i2 = new ID(2);
            ID i3 = new ID(3);
    
            map.put(i1, "haha");
            map.put(i2, "hehe");
            map.put(i3, "xixi");
    
            System.out.println(map.get(i1));//haha
            i1.setId(10);
            System.out.println(map.get(i1));//null
        }
    }

![在这里插入图片描述][b3b3474caed2436cbc589582a8ee4848.png_pic_center]

> 所以实际开发中，经常选用String，Integer等作为key，因为它们都是不可变对象。

[9ea25366b09e44eebaa88a805e43cd01.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/5a21d2d8940d4d76befc093cdab5ca3c.png
[416c514250024574974f6276dc28db60.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3a763d2231834623ae41adf50de0891a.png
[701a1749feac469482560970d5a2f101.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/4bf788c64739406b986bf3989b5e41de.png
[e6b032ffefc54c30bcbf041b4fa49807.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/86d378ee838b4d16822f492b84605918.png
[81866c658ea546cd8cc6c138cf8931de.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/99e91246a5f04642ad4204a775056132.png
[c4fe1f17ce3d4bbfb11ebc43cd4c1729.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/648a4d5b1fd54a67b107b413b7ce30fa.png
[b3b3474caed2436cbc589582a8ee4848.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d2ac907660904569a95ef20f1df98ce7.png