【java】HashMap底层实现原理

目录

• 一.哈希表(散列)
• • 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放在同一个链表中。如下图

(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)

hash	(n-1) & hash	储存下标
0	1111 & 0000	0
1	1111 & 0001	1
2	1111 & 0010	2
3	1111 & 0011	3
4	1111 & 0100	4
5	1111 & 0101	5

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

hash	(n-1) & hash	储存下标
0	1001 & 0000	0
1	1001 & 0001	1
2	1001 & 0010	0
3	1001 & 0011	1
4	1001 & 0100	0
5	1001 & 0101	1

重要：由上看出，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中，链表采用的是头插法(每次插入节点都是从头插入)。

① 假设这里有两个线程同时执行了put()操作(扩容)，并进入了transfer()方法。线程A先进行操作

② 线程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;  } 

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

④ 继续执行线程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  } 

⑤ 上轮循环之后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  } 

⑥上轮循环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(退出循环条件)  } 

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

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

当你调用put()方法时，putVal()方法里面有两处代码会产生数据覆盖。

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

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

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的操作是线程安全的。

(4)ConcurrentHashMap(常用)

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

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

② JDK 1.8抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消Segment类，直接用数组存储键值对。

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 

• P(0) = (0.5⁰ * e^-0.5) / 0! ≈ 0.60653066
• P(1) = (0.5¹ * e^-0.5) / 1! ≈ 0.30326533
• P(2) = (0.5² * 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次方，就不会在进行扩容了。