【java】HashMap底层实现原理

╰半夏微凉° 2023-09-23 20:03 97阅读 0赞

### 目录 ###

*  一.哈希表(散列)
 *   *  1.什么是哈希表
     *  2.什么是哈希冲突(面试题)
     *  3.解决哈希冲突的方法(面试题)
     *   *  (1) 开放地址法
         *   *  ① 线性探查
             *  ②二次探查
             *  ③随机探查
         *  (2) 再哈希法
         *  (3) 链地址法
         *  (4)建立公共溢出区
 *  二.HashMap
 *   *  1.HashMap的hash()算法(面试)
     *   *  (1)为什么不是\`h = key.hashCode()\`直接返回，而要 \`h = key.hashCode() ^ (h >>> 16)\`来计算哈希值呢？
         *  (2)为什么HashMap的初始容量和扩容都是2的次幂
         *  (3)如果指定了不是2的次幂的容量会发生什么？
     *  2.HashMap为什么线程不安全(面试题)
     *   *  (1) 多线程下扩容造成的死循环和数据丢失(jdk1.7)
         *  (2)数据覆盖(jdk1.8)
     *  3.HashMap解决线程不安全(面试题)
     *   *  (1) 使用HashTable解决线程不安全问题(弃用)
         *  (2)HashMap和HashTable的区别
         *  (3)Collections.synchronizedMap(不常用)
         *  (4)ConcurrentHashMap(常用)
     *  4.为什么使用synchronized替换ReentrantLock锁呢？
     *  4.HashMap底层 数组 + 链表 / 红黑树(面试题)
     *   *  (1)HashMap为什么引入链表
         *  (2)HashMap为什么引入红黑树
         *  (3)为什么不一开始就使用红黑树
         *  (4)说说你对红黑树的理解
         *  (5) 红黑树为什么要变色、左旋和右旋操作
     *  5.HashMap链表和红黑树转换(面试题)
     *   *  (1) 为什么链表长度大于8，并且表的长度大于64的时候，链表会转换成红黑树？
         *  (2) 为什么转成红黑树是8呢？而重新转为链表阈值是6呢？
         *  (3) 为什么负载因子是0.75？
     *  6.HashMap扩容(面试题)
     *   *  (1)什么时候会发生扩容？
         *  (2)为什么不是满了扩容？
         *  (3)扩容过程

# 一.哈希表(散列) #

## 1.什么是哈希表 ##

> 根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

> 给定表M，存在函数H(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash)表，函数H(key)为哈希(Hash)函数。

## 2.什么是哈希冲突(面试题) ##

> 根据一定的规则放进存放哈希值的数组中，然后下标为1的数组已经有值了，后面根据规则，判定某个数也需要放到下标为1的数组中，这样就导致了只有一个位置两个人都要坐，就引起了冲突。(不同的key值产生的H(key)是一样的)。

## 3.解决哈希冲突的方法(面试题) ##

### (1) 开放地址法 ###

> 插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。

Hi=(H(key)+di)%m  //开放地址法计算下标公式
    Hi：下标(储存的地址)
    H(key)：哈希函数(计算哈希值)
    di：增量
    %：取模
    m：哈希表的长度

探查方法如下

#### ① 线性探查 ####

> di=1,2,3,…m-1；冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

#### ②二次探查 ####

> di=1^2, -1^2, 2^2, -2^2 …k^2, -k^2,(k<=m/2)； 冲突发生时，在表的左右进行跳跃式探测，比较灵活。

#### ③随机探查 ####

> di=伪随机数序列；冲突发生时，建立一个伪随机数发生器（如i=(i+p) % m），p是质数(在m范围取得质数)，生成一个伪随机序列，并给定一个随机数做起点，每次加上伪随机数++就行。

为了更好的理解，我们举一个例子

设哈希表长为14，哈希函数为H(key)=key%11。表中现有数据15、38、61和84，其余位置为空，如果用二次探测再散列处理冲突，则49的位置是？使用线性探测法位置是？
    
    解：因为H(key)=key%11
    所以15的位置 = 15 % 11=4; 38的位置 = 38 % 11=5; 61的位置 = 61 % 11=6; 84的位置 = 84 % 11=7;(证明哈希表4,5,6,7已经有元素)
    
    因为计算下标的公式为：Hi=(H(key)+di)mod%m
    使用二次探测法
    H(1) = (49%11 + 1^1) = 6;冲突      
    H(-1) = (49%11 + (-1^2)) = 4;冲突   注意 -1^2 = -1; (-1)^2 = 1;
    H(2) = (49%11 + 2^2) = 9;不冲突
    二次探测法49的位置就是哈希表的9。
    
    使用线性探测
    H(1) = (49%11 + 1) = 6;冲突
    H(2) = (49%11 + 2) = 7;冲突
    H(3) = (49%11 + 3) = 8;不冲突
    线性探测法49的位置就是哈希表的8。

### (2) 再哈希法 ###

> 再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

### (3) 链地址法 ###

> 每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。  
> 比如 66和88这两个元素哈希值都是1，这就发生了哈希冲突，采用链地址法，可以把 66和88放在同一个链表中。如下图

![在这里插入图片描述][5fa8a3847d2c40089a3600de154c2d31.png]

### (4)建立公共溢出区 ###

> 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

# 二.HashMap #

## 1.HashMap的hash()算法(面试) ##

### (1)为什么不是`h = key.hashCode()`直接返回，而要 `h = key.hashCode() ^ (h >>> 16)`来计算哈希值呢？ ###

**回答：减少哈希冲突**

//源码：计算哈希值的方法 H(key)
    	static final int hash(Object key) {
        
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }   
        //^ (异或运算) 相同的二进制数位上，数字相同，结果为0，不同为1。  举例如下：
        0 ^ 0 = 0
        0 ^ 1 = 1
        1 ^ 1 = 0
        1 ^ 0 = 1
    	// &(与运算)  相同的二进制数位上，都是1的时候，结果为1，否则为零。 举例如下：
    	0 & 0 = 0
    	0 & 1 = 0
    	1 & 0 = 0
    	1 & 1 = 1

`h = key.hashCode() ^ (h >>> 16)`意思是先获得`key`的`哈希值h`，然后 h 和 h右移十六位 做`异或`运算，运算结果再和 `数组长度 - 1` 进行 `与` 运算，计算出储存下标的位置。具体原理如下：

综下所述 储存下标 = 哈希值 & 数组长度 - 1
    
    //jdk1.7中计算数组下标的HashMap源码
    static int indexFor(int h, int length) {
        
    		//计算储存元素的数组下标
            return h & (length-1);
    }
    
    //jdk1.8中去掉了indexFor()函数，改为如下
    i = (n - 1) & hash //i就是元素存储的数组下标

某个key的哈希值为 ：**1111 1111 1110 1111 0101 0101 0111 0101**，数组初始长度也是16，如果没有 `^ h >>> 16`，计算下标如下

1111 1111 1110 1111 0101 0101 0111 0101  //h = hashcode()
    	   &  0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)
    	   ------------------------------------------
    	      0000 0000 0000 0000 0000 0000 0000 0101  //key的储存下标为5
    
           由上面可知，只相当于取了后面几位进行运算，所以哈希冲突的可能大大增加。

以上条件不变，加上 `异或h >>> 16`，之后在进行下标计算

1111 1111 1110 1111 0101 0101 0111 0101  //h = hashcode()
           ^  0000 0000 0000 0000 1111 1111 1110 1111  //h >>> 16
           ------------------------------------------
              1111 1111 1110 1111 1010 1010 1001 1010  //h = key.hashCode() ^ (h >>> 16) 
          &   0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)
           ------------------------------------------
              0000 0000 0000 0000 0000 0000 0000 1010  //key的存储下标为10
              
            重要：由上可知，因为哈希值得高16位和低16位进行异或运算，混合之后的哈希值，低位也可能掺杂了高位的一部分特性(就是变化性增加了)，这样就减少了哈希冲突。

### (2)为什么HashMap的初始容量和扩容都是2的次幂 ###

**回答：也是为了减少哈希冲突。**

> 原理：  
> 因为判断储存位置的下标为 ： `i = (n - 1) & hash`，n就是数组的长度。  
> 2的次幂 - 1，其二进制都是1，比如 2^4 -1= 15(1111)，2^5-1 = 31(11111)。  
> 因为 `n-1` 和 `hash` 进行`与`运算，只有 1 & 1 ，才为1。  
> 因为 `n-1`永远是2的次幂-1，`(n - 1) & hash`的结果就是 hash的低位的值。

1111 1111 1110 1111 0101 0101 0111 0101  //hash值
    	   &  0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)
    	   ------------------------------------------
    	      0000 0000 0000 0000 0000 0000 0000 0101  //高位全部清零，只保留末四位(就相当于保留了hash的低位)

如果容量不是2次幂会怎么样呢？如下图表

*  2次幂的时候，数组长度为16，n-1 = 16 -1 = 15(1111)

*  非2次幂的时候，数组长度为10，n-1 = 10 -1 = 9(1001)

**重要**：由上看出，n为2的次幂，哈希冲突会更少，保证元素的均匀插入。

### (3)如果指定了不是2的次幂的容量会发生什么？ ###

**回答：会获得一个大于指定的初始值的最接近2的次幂的值作为初始容量。**  
比如：输入 9 获得 16，输入 5 获得 8。

原理如下：

static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子
    
    	static final int MAXIMUM_CAPACITY = 1 << 30;//初始容量最大为 2的30次方
    
    	/**
         * @param initialCapacity 初始容量
         */
    	public HashMap(int initialCapacity) {
        
            //此处通过把第二个参数负载因子使用默认值0.75f，然后调用有两个参数的构造方法
            this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用函数一
        }
    
    
    	/**
    	 * 函数一
         * @param initialCapacity 初始容量
         * @param loadFactor  负载因子
         */
        public HashMap(int initialCapacity, float loadFactor) {
        
            if (initialCapacity < 0)   //如果初始容量小于0，抛出异常
                throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)  //如果初始容量超过最大容量（1<<30）
                initialCapacity = MAXIMUM_CAPACITY;  //则使用最大容量作为初始容量
            if (loadFactor <= 0 || Float.isNaN(loadFactor))  //如果负载因子小于等于0或者不是数字，则抛出异常
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
            this.loadFactor = loadFactor;                //把负载因子赋值给成员变量loadFactor
     
            //调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量threshold
            this.threshold = tableSizeFor(initialCapacity); //调用函数二
        }
    
    	/**
    	 * 函数二
         * @param cap 初始容量
         */
        static final int tableSizeFor(int cap) {
         //这里我们假设我们初始容量是 10
            //容量减1，为了防止初始化容量已经是2的幂的情况，在最后有n+1的操作。  n = 10 - 1 = 9
            int n = cap - 1;      
    
    		//n = (n | n >>> 1) 带入得   n = (1001 | 0100) = 1101 
            n |= n >>> 1;        
    		//n = (n | n >>> 2) 带入得   n = (1101 | 0011) = 1111 
            n |= n >>> 2;       
    		//n = (n | n >>> 4) 带入得   n = (1111 | 0000) = 1111 
            n |= n >>> 4; 
    		//n = (n | n >>> 8) 带入得   n = (1111 | 0000) = 1111 
            n |= n >>> 8;       
            //n = (n | n >>> 16) 带入得  n = (1111 | 0000) = 1111 = 15
            n |= n >>> 16;        
            /**
            如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负数,
            所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n+1。
            
            n = 15 + 1 = 16，咱们传进来是初始容量10，会自动转为16容量。
            **/
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
            //return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;相当于下面这段代码
            if(n < 0){
        
            	return 1;
            }else{
        
            	if(n >= MAXIMUM_CAPACITY){
        
            		return MAXIMUM_CAPACITY; 
            	}else{
        
            		return n + 1;
            	}
            }
        }

## 2.HashMap为什么线程不安全(面试题) ##

### (1) 多线程下扩容造成的死循环和数据丢失(jdk1.7) ###

> 在jdk1.7中，链表采用的是`头插法`(每次插入节点都是从头插入)。  
> ![在这里插入图片描述][de36dc853b87423f96b8dc0479a37220.png]

**①** 假设这里有两个线程同时执行了put()操作(扩容)，并进入了transfer()方法。线程A先进行操作  
![在这里插入图片描述][217efaf361e1476ab4568860418e1687.png]

**②** 线程A在执行到 `newTable[i] = e`后被挂起，因为 `newTable[i] = null`,又因为 `e.next = newTable[i]`，所以`e.next = null`

transfer()方法部分源码：
    
    while(null !=e)
    
    {
        
          Entry<K,V> next =e.next; //next = 3.next = 7
    
          e.next = newTable[i]; //3.next = null
          
          newTable[i] = e;//线程A执行到这里被挂起了
    	
    	   e = next;
    
    }

![在这里插入图片描述][843c96d1cc9d46afbda5a9416c8c6774.png]

**③** 开始执行线程B，并完成了扩容。这时候 7.next = 3；3.next = null；

![在这里插入图片描述][acf7563cf0bc4118a8279619bb349062.png]

**④** 继续执行线程A，执行 `newTable[i] = e`，因为当时 e = 3，所以将3放到对应位置，此时执行 `e = next`，因为 `next = 7`(第②步)，所以 `e = 7`

while(null !=e)
    
    {
        
          Entry<K,V> next =e.next; //next = 3.next = 7
    
          e.next = newTable[i]; //3.next = null
          
          newTable[i] = e;//继续从这里执行  newTable[i] = 3
    	
    	   e = next; //e = 7
    
    }

![在这里插入图片描述][94b28bb0c02744218d9f89329aa536eb.png]  
**⑤** 上轮循环之后`e=7`，从主内存中读取`e.next`时发现主内存中`7.next=3`，此时`next=3`，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环。

while(null !=e)
    
    {
        
          Entry<K,V> next =e.next; //next = 7.next = 3
    
          e.next = newTable[i]; //7.next = 3
          
          newTable[i] = e;//newTable[i] = 7
    	
    	   e = next; //e = 3
    
    }

![在这里插入图片描述][2f8163a569e043189d72120abd82990d.png]

**⑥**上轮循环`7.next=3`，而e=3，执行下一次循环可以发现，因为`3.next=null`，所以循环之后 e = null，所以循环会退出。

while(null !=e)
    
    {
        
          Entry<K,V> next =e.next; // next = 3.next = null
    
          e.next = newTable[i];  //3.next = 7 (此处3指向7,同时之前7也指向了3,所以会形成闭环)
          
          newTable[i] = e;       //newTable[i] = 3
          
    	  e = next;              //e = null(退出循环条件)
    
    }

![在这里插入图片描述][3695f1d85cbf42069c67c01952019fa0.png]

### (2)数据覆盖(jdk1.8) ###

> jdk1.8中已经不再采用头插法，改为尾插法，即直接插入链表尾部，因此不会出现死循环和数据丢失，但是在多线程环境下仍然会有数据覆盖的问题。

当你调用put()方法时，putVal()方法里面有两处代码会产生数据覆盖。  
![在这里插入图片描述][80bb7b084f2e49069d35ed05f9b9c11e.png]

> ① 假设两个线程都进行put操作，线程A和线程B通过哈希函数算出的储存下标是一致的，当线程A判断完之后，然后挂起，然后线程B判断完进入，把元素放到储存位置，然后线程A继续执行，把元素放到储存位置，因为线程A和线程B存储位置一样，所以线程A会覆盖线程B的元素。  
> ![请添加图片描述][ce6924ab28694281958927fb2e4cf831.png]

> ② 同样在putVal()方法里。两个线程，假设HashMap的size为15，线程A从主内存获得15，准备进行++的操作的时候，被挂起，然后线程B拿到size并执行++操作，并写回主内存，这时size是16，然后线程A继续执行(这时A线程内存size还是15)++操作，然后写回主内存，即线程A和线程B都进行了put操作，然后size值增加了1，所以数据被覆盖了。  
> ![请添加图片描述][0274ba27ae2b4bffaf7f8fd9c6149dc3.png]

## 3.HashMap解决线程不安全(面试题) ##

### (1) 使用HashTable解决线程不安全问题(弃用) ###

> 因为HashTable解决线程不安全就是在其方法加上同步关键字(synchronized)，会导致效率很低下。

### (2)HashMap和HashTable的区别 ###

**①线程是否安全**  
HashMap线程不安全。  
HashTable线程安全，但是效率较低。

**②是否null**  
HashMap中key只能有一个null，value可以多个为null。  
HashTable不允许键或值为null。

**③容量**  
HashMap底层数组长度必须为2的幂（16，32，128…），默认为16。  
HashTable底层数组长度可以为任意值，导致hash算法散射不均匀，容易造成hash冲突，默认为11。

**④底层区别**  
HashMap是底层由数组+链表形成，在JDK1.8之后链表长度大于8时转化为红黑树。  
HashTable一直都是数组+链表。

**⑤继承关系**  
HashTable继承自Dictionary类。  
HashMap继承自AbstractMap类。

### (3)Collections.synchronizedMap(不常用) ###

Map<String,String> map = Collections.synchronizedMap(new HashMap<>());

> 可以看到SynchronizedMap 是一个实现了Map接口的代理类，该类中对Map接口中的方法使用synchronized同步关键字来保证对Map的操作是线程安全的。

![在这里插入图片描述][8af734bf6e6647c78f4dcc2944d678bb.png]

### (4)ConcurrentHashMap(常用) ###

> ① jdk1.7使用分段锁，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment(锁角色) 和 HashEntry(存放键值对)。

> 分段锁：Segment(继承ReentrantLock来加锁)数组中，一个Segment对象就是一把锁,对应n个HashEntry数组,不同HashEntry数组的读写互不干扰。

![在这里插入图片描述][42ed06c0858743b18cb2a842cb9771ef.png]

> ② JDK 1.8抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消Segment类，直接用数组存储键值对。  
> ![在这里插入图片描述][fd6a8a24fe094e359e87f469ee8dff0e.png]

[CAS理解][CAS]

## 4.为什么使用synchronized替换ReentrantLock锁呢？ ##

① 减少内存开销。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS(队列同步器)来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。  
② 获得JVM的支持。可重入锁毕竟是API这个级别的，后续的性能优化空间很小。 synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。  
③在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。

**AQS**：是一个队列同步器，同步队列是一个双向链表，有一个状态标志位state，如果state为1的时候，表示有线程占用，其他线程会进入同步队列等待，如果有的线程需要等待一个条件，会进入等待队列，当满足这个条件的时候才进入同步队列，ReentrantLock就是基于AQS实现的

> 锁升级方式：就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为CAS(compare and swap 原子操作) 轻量级锁，如果失败就会短暂自旋(不停的判断比较，看能否将值交换)，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。

*  偏向锁：减少无竞争且只有一个线程使用锁的情况下，使用轻量级锁产生的性能消耗。轻量级锁每次申请、释放锁都至少需要一次CAS，但偏向锁只有初始化时需要一次CAS。
 *  轻量级锁：当有两个线程，竞争的时候就会升级为轻量级锁。轻量级锁的目标是，减少无实际竞争情况下，使用重量级锁产生的性能消耗，包括系统调用引起的内核态与用户态切换、线程阻塞造成的线程切换等。
 *  重量级锁：大多数情况下，在同一时间点，常常有多个线程竞争同一把锁，悲观锁的方式，竞争失败的线程会不停的在阻塞及被唤醒态之间切换，代价比较大。

## 4.HashMap底层 数组 + 链表 / 红黑树(面试题) ##

**红黑树**：平衡二叉查找树

### (1)HashMap为什么引入链表 ###

> 因为HashMap在put()操作时，会进行哈希值得计算，算出储存下标要放在数组那个位置时，当多个元素要放在同一位置时就会出现哈希冲突，然后引进链表，把相同位置的元素放进同一个链表(链地址法)。

### (2)HashMap为什么引入红黑树 ###

> 因为当链表长度大于8时，链表遍历查询速度比较慢，所以引入红黑树。

### (3)为什么不一开始就使用红黑树 ###

> 因为树相对链表维护成本更大，红黑树在插入新数据之后，可能会通过左旋、右旋、变色来保持平衡，造成维护成本过高，故链路较短时，不适合用红黑树。

### (4)说说你对红黑树的理解 ###

> 红黑树是一种平衡二叉查找树，是一种数据结构。除了具备二叉查找树特性以外，还具备以下特性

*  1.根节点是黑色
 *  2.节点是黑色或红色
 *  3.每个叶子节点是黑色
 *  4.红色节点的子节点都是黑色
 *  5.从任意节点到其叶子节点的所有路径都包含相同数目的黑色节点

说出以上就很好了

补充：以上性质强制了红黑树的关键性质**从根到叶子的最长的可能路径不多于最短的可能路径的两倍长**。保证了红黑树的高效。

### (5) 红黑树为什么要变色、左旋和右旋操作 ###

> 当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。  
> 过程：先变色如果变色还不满足红黑树的性质，那就进行左旋或者右旋，然后继续变色，以此循环直至符合红黑树的性质。

## 5.HashMap链表和红黑树转换(面试题) ##

*  链表长度大于8，并且表的长度大于64   数组 + 红黑树
 *  链表长度大于8，并且表的长度不大于64  数组 + 链表 会扩容
 *  当数的节点小于6             数组 + 链表

### (1) 为什么链表长度大于8，并且表的长度大于64的时候，链表会转换成红黑树？ ###

> 因为链表长度符合泊松分布，长度越长哈希冲突概率就越小，当链表长度为8时，概率仅为 0.00000006，这时是一个千万分之一的概率，然后我们map也不会存储那么多的数据，所以链表长度不超过8没有必要转换成红黑树。如果出现这种大量数据的话，转为红黑树可以增加查询和插入效率。长度大于64，只是注释写了 最低要在 4\*8，我也没弄懂，请大佬指导。  
> 原理如下：

In usages with well-distributed user hashCodes, tree bins 
    are rarely used.  Ideally, under random hashCodes, the 
    frequency of nodes in bins follows a Poisson distribution 
    (http://en.wikipedia.org/wiki/Poisson_distribution) with a 
    parameter of about 0.5 on average for the default resizing 
    threshold of 0.75, although with a large variance because 
    of resizing granularity. Ignoring variance, the expected 
    occurrences of list size k are (exp(-0.5) * pow(0.5, k) / 
    factorial(k)). The first values are:
     0:    0.60653066
     1:    0.30326533
     2:    0.07581633
     3:    0.01263606
     4:    0.00157952
     5:    0.00015795
     6:    0.00001316
     7:    0.00000094
     8:    0.00000006
     more: less than 1 in ten million  //翻译：更多：少于千万分之一
    
    
    负载因子是0.75和长度为8转为红黑树的原理：由上面我们可以看出 当负载因子为0.75时，哈希冲突出现的频率遵循参数为0.5的泊松分布。
    常数0.5是作为参数代入泊松分布来计算的，而加载因子0.75是作为一个条件。
    
    泊松分布是一种离散概率分布，泊松分布的概率质量函数：
    
    x=(0,1,2,...)。
    λ：单位时间内随机事件的平均发生率。因为我们从上面知道平均发生率是0.5
    e^(-0.5) = 0.60653065971264  //e的负0.5次方
    阶乘：指从1乘以2乘以3乘以4一直乘到所要求的数。比如 3！ = 1 * 2 * 3

![在这里插入图片描述][eab37d8403c344e3b2ef7b205fdb9ce3.png]

*  P(0) = (0.50 \* e\-0.5) / 0! ≈ 0.60653066
 *  P(1) = (0.51 \* e\-0.5) / 1! ≈ 0.30326533
 *  P(2) = (0.52 \* e\-0.5) / 2! ≈ 0.07581633
 *  后面就不给大家计算了，有兴趣可以自己算一下。

### (2) 为什么转成红黑树是8呢？而重新转为链表阈值是6呢？ ###

> 如果转为链表也是8，那如果在8这个位置发生哈希冲突，那红黑树和链表就会频繁切换，就会浪费资源。

### (3) 为什么负载因子是0.75？ ###

> 根据上面的泊松分布来看，表长度达到8个元素的时候，概率为0.00000006，几乎是一个不可能事件，减少了哈希冲突。

> 加载因子 = 填入表中的元素个数 / 散列表的长度

加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大了；

加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。

“冲突的机会”与“空间利用率”之间，寻找一种平衡与折中。

## 6.HashMap扩容(面试题) ##

### (1)什么时候会发生扩容？ ###

> 元素个数 > 数组长度 \* 负载因子 例如 16 \* 0.75 = 12,当元素超过12个时就会扩容。  
> 链表长度大于8并且表长小于64，也会扩容

### (2)为什么不是满了扩容？ ###

> 因为越元素越接近数组长度，哈希冲突概率就越大，所以不是满了扩容。

### (3)扩容过程 ###

*  jdk1.7  
    创建一个新的table，并调用transfer()方法把旧数组中的数据迁移到新数组中，使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致死链和数据丢失现象。
 *  jdk1.8  
    ①在resize()方法中，定义了oldCap参数，记录了原table的长度，定义了newCap参数，记录新table长度，newCap是oldCap长度的2倍，然后循环原table，把原table中的每个链表中的每个元素放入新table。  
    ②计算索引做了优化：hash（原始hash） & oldCap（原始容量） == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap（原始容量）。

**注意**

*  扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
 *  HashMap的容量达到2的30次方，就不会在进行扩容了。

[5fa8a3847d2c40089a3600de154c2d31.png]: https://img-blog.csdnimg.cn/5fa8a3847d2c40089a3600de154c2d31.png
[de36dc853b87423f96b8dc0479a37220.png]: https://img-blog.csdnimg.cn/de36dc853b87423f96b8dc0479a37220.png
[217efaf361e1476ab4568860418e1687.png]: https://img-blog.csdnimg.cn/217efaf361e1476ab4568860418e1687.png
[843c96d1cc9d46afbda5a9416c8c6774.png]: https://img-blog.csdnimg.cn/843c96d1cc9d46afbda5a9416c8c6774.png
[acf7563cf0bc4118a8279619bb349062.png]: https://img-blog.csdnimg.cn/acf7563cf0bc4118a8279619bb349062.png
[94b28bb0c02744218d9f89329aa536eb.png]: https://img-blog.csdnimg.cn/94b28bb0c02744218d9f89329aa536eb.png
[2f8163a569e043189d72120abd82990d.png]: https://img-blog.csdnimg.cn/2f8163a569e043189d72120abd82990d.png
[3695f1d85cbf42069c67c01952019fa0.png]: https://img-blog.csdnimg.cn/3695f1d85cbf42069c67c01952019fa0.png
[80bb7b084f2e49069d35ed05f9b9c11e.png]: https://img-blog.csdnimg.cn/80bb7b084f2e49069d35ed05f9b9c11e.png
[ce6924ab28694281958927fb2e4cf831.png]: https://img-blog.csdnimg.cn/ce6924ab28694281958927fb2e4cf831.png
[0274ba27ae2b4bffaf7f8fd9c6149dc3.png]: https://img-blog.csdnimg.cn/0274ba27ae2b4bffaf7f8fd9c6149dc3.png
[8af734bf6e6647c78f4dcc2944d678bb.png]: https://img-blog.csdnimg.cn/8af734bf6e6647c78f4dcc2944d678bb.png
[42ed06c0858743b18cb2a842cb9771ef.png]: https://img-blog.csdnimg.cn/42ed06c0858743b18cb2a842cb9771ef.png
[fd6a8a24fe094e359e87f469ee8dff0e.png]: https://img-blog.csdnimg.cn/fd6a8a24fe094e359e87f469ee8dff0e.png
[CAS]: https://blog.csdn.net/baidu_41632451/article/details/124754457
[eab37d8403c344e3b2ef7b205fdb9ce3.png]: https://img-blog.csdnimg.cn/eab37d8403c344e3b2ef7b205fdb9ce3.png