4.1 Hash表与HashMap

4.1.1 HashMap内部实现的Hash表结构图

4.1.2 概述

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

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

HashMap：是Java中用对象数组加链表实现的一种数据类型（结构类型），它通过代码实现了Hash表 这种数据结构，并在此结构上定义了一系列操作。

• 桶的初始数量为16个(对应0~15的下标)。
• 在存值时利用hashCode( )得到的一个int类型的key，然后将key与桶个数进行取余运算得到key在数组中的下标位置，然后就可将key对应的value存入该下标对应的桶(链表)中。

4.1.3 重点知识

1. 在jdk8之后，为了提高HashMap的性能，在哈希桶(链表)中数据量大于8时，会将链表转换为红黑树(目的在于数据量大时将查询的时间复杂度从n降为log(n)),而当数据量从大于8降为小于6时又会转为链表(数据量小时查询效率差不太多，反而会增加空间复杂度)。

   i. 为什么不一开始就用红黑树的？

   ​ 答：因为二叉树(红黑树其实是一种二叉树)虽然查询效率高，但是空间开销非常大，单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，而在数据量很小时，红黑树与链表的查询效率不会差太多，所以一开始用链表结构的桶是比较划算的。

   ii. 为什么转换阀值是8？

   ​ 答：①从分布规律解释：根据理想状态下的泊松分布规律桶长度超过8的概率非常小，约为6乘以10的负8次方，这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。

   ​ ②从数学计算来解释：红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，查询长度已经多出1个了，这样就有了转换成树的必要。

   iii.在转换回来的时候，为什么不是小于8(即7)时就立即将红黑树转为链表？

   答：中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

2. HashMap默认的散列因子(负载因子)是0.75。

   i. 什么是散列因子？

   ​ 答：负载因子是哈希表容量自动增加之前允许哈希表获得的满度的度量。当哈希表中的桶的数量超过负载因子和当前容量的乘积时，哈希表将被重新哈希。

   ii. 为什么散列因子是0.75？

   ​ 答：当负载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么桶中的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是，这时候空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。一句话总结就是负载因子太小，虽然时间效率提升了，但是空间利用率降低了。而当负载因子为1的时候，此时空间利用率确实高，但是，链表或红黑树的高度也剧增了，此时的查询效率就大打折扣了。为了达到时间和空间上的权衡，最终选择了0.75作为负载因子