从0开始回顾Java---系列八

HashMap

1、HashMap 有什么特点？

HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在，主要用来存放键值对。

特点：

• HashMap 的实现不是同步的，这意味着它不是线程安全的
• key 是唯一不重复的，底层的哈希表结构，依赖 hashCode 方法和 equals 方法保证键的唯一
• key、value 都可以为null，但是 key 位置只能是一个null
• HashMap 中的映射不是有序的，即存取是无序的
• key 要存储的是自定义对象，需要重写 hashCode 和 equals 方法，防止出现地址不同内容相同的 key
• JDK1.8 之前 HashMap 由 数组+链表 组成

• 数组是 HashMap 的主体
• 链表则是为了解决哈希冲突而存在的（拉链法解决冲突），拉链法就是头插法，两个对象调用的 hashCode 方法计算的哈希码值（键的哈希）一致导致计算的数组索引值相同

• JDK1.8 以后 HashMap 由 数组+链表 +红黑树数据结构组成

• 解决哈希冲突时有了较大的变化
• 当链表长度超过（大于）阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于等于 64 时，此索引位置上的所有数据改为红黑树存储
• 即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，就相当于一个长的单链表，假如单链表有 n 个元素，遍历的时间复杂度是 O(n)，所以 JDK1.8 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题，使得查找效率更高。

2、HashMap的底层数据结构是什么？

在JDK1.7 中，由“数组+链表”组成：数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。

在JDK1.8 中，由“数组+链表+红黑树”组成：当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的  O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：6

• 当链表长度 > 8 && 数组长度 >= 64 才会转红黑树;
• 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。

3、对红黑树了解多少？为什么不用二叉树/平衡树呢？

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

1. 每个节点要么是红色，要么是黑色；
2. 根节点永远是黑色的；
3. 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
4. 每个红色节点的两个子节点一定都是黑色；
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

之所以不用二叉树：

红黑树是一种不严格的平衡二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。

之所以不用二叉平衡树：

二叉平衡树是一种高度平衡的二叉树，查找效率高 ，但是 为了维持这种高度的平衡，就要付出更多代价。每次插入、删除都要做调整，就比较复杂、耗时。因此，红黑树的查询性能略微逊色于二叉平衡树,  但是红黑树在插入和删除上优于二叉平衡树 ；

总体来讲，红黑树的插入、删除、查找各种操作性能都比较稳定，对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

之所以不用B树或B+树：

1. B+树在数据库中被应用的原因就是B+树比B树更加“矮胖”，B+树的非叶子结点不存储数据，所以每个结点能存储的关键字更多。所以B+树更能应对大量数据的情况。如果用B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面。这个时候遍历效率就退化成了链表
2. B和B+树主要用于数据存储在磁盘上的场景，比如数据库索引就是用B+树实现的。这两种数据结构的特点就是树比较矮胖，每个结点存放一个磁盘大小的数据，这样一次可以把一个磁盘的数据读入内存，减少磁盘转动的耗时，提高效率。而红黑树多用于内存中排序，也就是内部排序。

4、红黑树怎么保持平衡的知道吗？

红黑树有两种方式保持平衡：旋转和染色。

• 旋转：旋转分为两种，左旋和右旋

• 染色：

5、解决hash冲突的办法有哪些？HashMap用的哪种？

解决Hash冲突方法有：开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区。HashMap中采用的是链地址法 。

1. 开放定址法：

• 开放定址法也称为再散列法，基本思想就是，如果p = H(key)出现冲突时，则以p为基础，再次hash，p1 = H(p),直到找到一个不冲突的哈希地址。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。

2. 再哈希法:

• 再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当R1 = H1(key1)发生冲突时，再计算R2 =H2(key1)，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。

3. 链地址法(拉链法):

• 在冲突的位置拉一个链表，把冲突的元素放进去。链地址法适用于经常进行插入和删除的情况。

4. 建立公共溢出区:

• 再建一个数组，把冲突的元素放进去。

6、为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?

1. 因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8  个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是  O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
2. 因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

7、HashMap和Hashtable的区别？

1. 线程安全: Hashtable方法sychonized修饰，线程安全
2. 效率方面: 由于Hashtable方法被sychonized修饰，效率比HashMap低
3. 底层数据结构: HashMap jdk8当链表长度>8并且数组长度>=64链表会转红黑树，Hashtable没有这样机制
4. 初始容量: 默认初始量:Hashtable为11，HashMap为16;若指定初始量: Hashtable用指定的值，HashMap会扩充为2的幂次方大小。
5. 扩容:Hashtable容量变为原来2n+1倍，HashMap变为2倍。
6. 对Null key与Null value支持:   HashMap支持一个Null key多个Null value，Hashtable不支持Null key 和 Null value，否则报错空指针异常

8、HashMap jdk8与jdk7区别？

1. 数据结构：

• 7 =   数组 + 链表，8 = 数组 + 链表 + 红黑树
• 发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)

2. 链表插入方式：

• 7 中是头插法，多线程容易造成环，8 中是尾插法

3. 扩容：

• 7 的扩容是全部数据重新定位，8 中是位置不变或者当前位置 + 旧 size 大小来实现
• 8可以提高扩容的效率，更快地扩容

4. 扩容时机：

• 7 是先判断是否要扩容，再插入，8 中是先进行插入，再看是否要扩容

5. 散列函数：

• 1.7 做了四次移位和四次异或，jdk1.8只做一次。
• 做 4 次的话，边际效用也不大，改为一次，提升效率。

9、扩容因子为什么是 0.75，不是 0.6 或者 0.8 ？

为什么需要扩容因子？

HashMap的底层是哈希表，是存储键值对的结构类型，它需要通过一定的计算才可以确定数据在哈希表中的存储位置。一般的数据结构，不是查询快就是插入快，HashMap就是一个插入慢、查询快的数据结构。但这种数据结构容易产生两种问题：

1. 如果空间利用率高，那么经过的哈希算法计算存储位置的时候，会发现很多存储位置已经有数据了（哈希冲突）
2. 如果为了避免发生哈希冲突，增大数组容量，就会导致空间利用率不高。

因此扩容因子，是用来衡量 HashMap 满的程度，表示 HashMap 的疏密程度，影响 hash 操作到同一个数组位置的概率：

1. 太大会导致查找元素效率低，存放的数据拥挤；
2. 太小导致数组的利用率低，存放的数据会很分散。

为什么选择了0.75作为HashMap的加载因子呢？

这与一个统计学里很重要的原理——泊松分布有关：

1. 泊松分布是统计学和概率学常见的离散概率分布，适用于描述单位时间内随机事件发生的次数的概率分布。
2. 在理想情况下，使用随机哈希码，在扩容阈值（加载因子）为0.75的情况下，节点出现在频率在Hash桶（表）中遵循参数平均为0.5的泊松分布。
3. 根据某个公式计算，当一个bin中的链表长度达到8个元素的时候，概率为0.00000006，几乎是一个不可能事件。
4. 因此，默认值为 0.75是官方给出的一个比较好的临界值 ，0.75是对空间和时间效率的一个平衡选择，一般不要修改。

10、Hashmap扩容流程?

扩容条件：

• 当 HashMap 中的元素个数超过 (数组长度)*loadFactor(负载因子) 或者 链表过长时（链表长度 > 8，数组长度 < 64），就会进行数组扩容，创建新的数组，伴随一次重新 hash 分配，并且遍历 hash 表中所有的元素非常耗时，所以要尽量避免 resize，扩容为原来容量的 2 倍。

新节点位置：

1. HashMap 在进行扩容后，节点要么就在原来的位置，要么就被分配到"原位置+旧容量"的位置，具体会将所有节点分成高低位两个链表，
2. 低位链表存放扩容后数组下标没变的节点，高位链表存放变了的节点，最后将高低位链表插入新数组中。

具体流程：

1. 重新建立一个新的数组，长度为原数组的两倍；
2. 遍历旧数组的每个数据，重新计算每个元素在新数组中的存储位置。使用节点的hash值与旧数组长度进行位与运算，如果运算结果为0，表示元素在新数组中的位置不变；否则，则在新数组中的位置下标=原位置+原数组长度。
3. 将旧数组上的每个数据使用尾插法逐个转移到新数组中，并重新设置扩容阈值。

11、HashMap 中  key 的存储索引是怎么计算的？

1. 首先根据key的值计算出hashcode的值；
2. 然后根据hashcode计算出hash值；
3. 最后通过hash &（length-1）计算得到存储的位置。

12、HashMap的长度为什么是2的幂次方？

1. HashMap 中添加元素时，需要根据 key 的 hash 值，确定在数组中的具体位置。为了存取高效，要尽量较少碰撞，把数据尽可能分配均匀，每个链表长度大致相同，实现该方法的算法就是取模，hash%length，计算机中直接求余效率不如位移运算，所以源码中使用 hash & (length-1)，实际上hash % length == hash & (length-1)的前提是 length 是2的n次幂
2. 散列平均分布：2 的 n 次方是 1 后面 n 个 0，2 的 n 次方 -1 是 n 个 1。这样按位“与”时，每一位都能&1，真正参与了运算，可以保证散列的均匀性，减少碰撞。

13、为什么要把key的哈希码右移16位呢？

因为h的int类型正好32位，为了使计算出的hash值更加的分散，所以选择先将h无符号右移16位，然后再与h异或时，就能达到h的高16位和低16位都能参与计算，尽最大努力减少哈希冲突。

14、初始化HashMap，传一个17，它会怎么处理？

简单来说，就是初始化时，传的不是2的n次幂时，HashMap会向上寻找离得最近的2的n次幂，所以传入17，但HashMap的实际容量是32。

以17为例，看一下初始化计算table容量的过程：

15、为什么HashMap链表转红黑树的阈值为8呢？

在 HashMap 中有一段注释说明：空间和时间的权衡

TreeNodes占用空间大约是普通节点的两倍，所以我们只在箱子包含足够的节点时才使用树节点。
当节点变少(由于删除或调整大小)时，就会被转换回普通的桶。在使用分布良好的用户hashcode时，
很少使用树箱。理想情况下，在随机哈希码下，箱子中节点的频率服从"泊松分布"，默认调整阈值为0.75，
平均参数约为0.5，尽管由于调整粒度的差异很大。忽略方差，
列表大小k的预期出现次数是(exp(-0.5)*pow(0.5, k)/factorial(k))
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
当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，
几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，
然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。
不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，
一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，
是根据概率统计决定的。由此可见，发展30年的Java每一项改动和优化都是非常严谨和科学的。

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。

阈值为什么要选8呢？

• 和概率统计有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006，几乎是不可能事件。

红黑树转回链表的阈值为什么是6，而不是8？

• 因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。

其他说法：

• 红黑树的平均查找长度是 log(n)，如果长度为 8，平均查找长度为 log(8)=3，链表的平均查找长度为 n/2，当长度为 8 时，平均查找长度为 8/2=4，这才有转换成树的必要；链表长度如果是小于等于 6，6/2=3，而 log(6)=2.6，虽然速度也很快的，但转化为树结构和生成树的时间并不短。

16、Hashmap的put方法流程？

简要流程如下：

1. 首先判断数组是否为空，为空则调用 resize 进行初始化；
2. 根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；  
3. 如果没有哈希冲突直接放在对应的数组下标里；
4. 如果冲突了，且 key 已经存在，就覆盖掉 value；
5. 如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
6. 如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组长度小于 64，就进行扩容；如果链表节点大于 8 并且数组长度大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。  

17、HashMap怎么查找元素的呢？

简要流程如下：

1. 使用扰动函数，获取新的哈希值
2. 计算数组下标，获取节点
3. 当前节点和key匹配，直接返回
4. 否则，当前节点是否为树节点，查找红黑树
5. 否则，遍历链表查找

18、HashMap为什么线程不安全？

1. 多线程下扩容死循环。JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
2. 多线程的put可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
3. put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。

19、如何解决HashMap线程不安全的问题呢？

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

• HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；
• Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
• ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。

20、HashMap get和put时间复杂度？

1. get() 最好时间复杂度 O(1)

• 若为树，则在树中通过 key.equals(k) 查找，O(logn)
• 若为链表，则在链表中通过 key.equals(k) 查找，O(n)
• 平均为O(1)

2. put() 最好时间复杂度 O(1)

• 若为树，则在树中通过 key.equals(k) 查找，O(logn)
• 若为链表，则在链表中通过 key.equals(k) 查找，O(n)
• 平均为O(1)

21、如何实现一个HashMap吗？

整体的设计：

• 散列函数：hashCode()+ 除留余数法
• 冲突解决：链地址法
• 扩容：节点重新hash获取位置

完整代码地址：https://mp.weixin.qq.com/s/Z9yoRZW5itrtgbS-cj0bUg

22、如何设计线程安全的HashMap?

HashMap线程不安全的体现：

1. 多线程下扩容死循环：JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
2. 多线程的put可能导致元素的丢失：多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
3. put和get并发时，可能导致get为null：线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。

针对问题1，JDK1.8使用尾插法已经解决了，因此我们需要重点解决问题2和问题3。

思路一：使用Synchronized来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放。

优点：实现简单。

缺点：竞争激烈的多线程场景中性能会变的很差。

思路二：使用ConcurrentHashMap1.7的实现思路， 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。

优点：并发访问率比Synchronized更高，效率也更高。

思路三：使用ConcurrentHashMap1.8的实现思路，采用CAS + synchronized实现更加低粒度的锁。

优点：将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。

CAS机制在ConcurrentHashMap的具体体现：

1. 在初始化数组时,它会以CAS的方式修改初始化状态，避免多个线程同时进行初始化；
2. 在执行put方法初始化头节点时，它会以CAS的方式将初始化好的头节点设置到指定槽的首位，避免多个线程同时设置头节点；
3. 在数组扩容时,每个线程会以CAS方式修改任务序列号来争抢扩容任务，避免和其他线程产生冲突；
4. 在执行get方法时，它会以CAS的方式获取头指定槽的头节点,避免其他线程同时对头节点做出修改。