HashMap

面试官再问你 HashMap 底层原理，就把这篇文章甩给他看
长文多图——HashMap源码解析
红黑树简介及左旋、右旋、变色

1、HashMap 的实现原理/底层数据结构？ JDK1.7 和 JDK1.8

JDK1.7： Entry数组 + 链表
JDK1.8： Node 数组 + 链表/红黑树，当链表上的元素个数超过 8 个并且数组长度 >= 64 时自动转化成红黑树，节点变成树节点，以提高搜索效率和插入效率到 O(logN)。
Entry 和 Node 都包含 key、 value、 hash、 next 属性。

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

  2、当new一个HashMap的时候，会发生什么吗？

  HashMap有几个构造方法，但最主要的就是指定初始值大小和负载因子的大小。如果我们不指定，默认HashMap的大小为16，负载因子的大小为0.75
  HashMap的大小只能是2次幂的，假设你传一个10进去，实际上最终HashMap的大小是16，你传一个7进去，HashMap最终的大小是8，具体的实现在tableSizeFor可以看到。
  我们把元素放进HashMap的时候，需要算出这个元素所在的位置（hash），在HashMap里用的是位运算来代替取模，能够更加高效地算出该元素所在的位置。为什么HashMap的大小只能是2次幂，因为只有大小为2次幂时，才能合理用位运算替代取模。
  而负载因子的大小决定着哈希表的扩容和哈希冲突。
  比如现在我默认的HashMap大小为16，负载因子为0.75，这意味着数组最多只能放12个元素，一旦超过12个元素，则哈希表需要扩容。么算出是12呢？很简单，就是16*0.75。每次put元素进去的时候，都会检查HashMap的大小有没有超过这个阈值，如果有，则需要扩容。
  鉴于上面的说法（HashMap的大小只能是2次幂），所以扩容的时候时候默认是扩原来的2倍
  扩容这个操作肯定是耗时的，那能不能把负载因子调高一点，比如我要调至为1，那我的HashMap就等到16个元素的时候才扩容呢。是可以的，但是不推荐。负载因子调高了，这意味着哈希冲突的概率会增高，哈希冲突概率增高，同样会耗时（因为查找的速度变慢了）

  3、在put元素的时候，传递的Key是怎么算哈希值的？

  实现就在hash方法上，可以发现的是，它是先算出正常的哈希值，然后与高16位做异或运算，产生最终的哈希值。这样做的好处可以增加了随机性，减少了碰撞冲突的可能性。
  

  4、HashMap 的 put 方法的执行过程？

  在put的时候，首先要判断数组是否为空，如果数组为空则会进行第一次的扩容。然年对key做hash运算，计算出该key所在的index。

如果没碰撞，直接放到数组中，如果碰撞了，需要判断目前数据结构是链表还是红黑树，根据不同的情况来进行插入。假设key是相同的，则替换到原来的值。
最后判断哈希表是否满了(当前哈希表大小*负载因子），如果满了，则扩容。

在get的时候，还是对key做hash运算，计算出该key所在的index，然后判断是否有hash冲突。
假设没有冲突直接返回，假设有冲突则判断当前数据结构是链表还是红黑树，分别从不同的数据结构中取出。

5、HashMap中是怎么判断一个元素是否相同的呢？

首先会比较hash值，随后会用==运算符和equals()来判断该元素是否相同。
说白了就是：如果只有hash值相同，那说明该元素哈希冲突了，如果hash值和equals() || == 都相同，那说明该元素是同一个。

1. HashMap判断Key是否相同；

2. 对比hash值，对比equals。

   6、HashMap的数据结构是数组+链表/红黑树，那什么情况拿下才会用到红黑树呢？

   当数组的大小大于64且链表的大小大于8的时候才会将链表改为红黑树，当红黑树大小为6时，会退化为链表。这里转红黑树退化为链表的操作主要出于查询和插入时对性能的考量。链表查询时间复杂度O(N)，插入时间复杂度O(1)，红黑树查询和插入时间复杂度O(logN)。

   7、HashMap是线程安全的吗？

   HashMap不是线程安全的，在多线程环境下，HashMap有可能会有数据丢失和获取不了最新数据的问题，比如说：线程Aput进去了，线程Bget不出来。

   8、hash碰撞是什么以及如何解决

   大白话解释hash碰撞是什么以及如何解决

   9、HashMap线程不安全解释

   如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会对该位置进行插入。
   假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。

   10、CopyOnWriteArrayList 的底层原理是怎样的

3. 首先 CopyOnWriteArrayList 内部也是用过数组来实现的，在向 CopyOnWriteArrayList 添加元素时，会复制一个新的数组，写操作在新数组上进行，读操作在原数组上进行；

4. 并且，写操作会加锁，防止出现并发写入丢失数据的问题；
5. 写操作结束之后会把原数组指向新数组；
6. CopyOnWriteArrayList 允许在写操作时来读取数据，大大提高了读的性能，因此适合读多写少的应用场景，但是 CopyOnWriteArrayList 会比较占内存，同时可能读到的数据不是实时最新的数据，所以不适合实时性要求很高的场景。

但是 CopyOnWriteArrayList 有其缺陷：
内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景 。

11、一般用什么作为HashMap的key?

一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。
因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。这就是
HashMap 中的键往往都使用字符串的原因。因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的，这些类已经很规范的重写了 hashCode() 以及 equals() 方法。

12、HashMap默认加载因子是多少？为什么是 0.75，不是0.6 或者 0.8 ？

默认的 loadFactor 是0.75，0.75是对空间和时间效率的一个平衡选择，一般不要修改，除非在时间和空
间比较特殊的情况下 ：

• 如果内存空间很多而又对时间效率要求很高，可以降低负载因子 Load factor 的值 。
• 相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

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

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

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

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

1. 开放定址法也称为再散列法 ，基本思想就是，如果 p=H(key) 出现冲突时，则以 p 为基础，再次
   hash， p1=H(p)，如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地
   址 pi 。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次
   hash，所以 只能在删除的节点上做标记，而不能真正删除节点。
2. 再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当 R1=H1(key1) 发生冲突时，再计
   算 R2=H2(key1) ，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。

3. 链地址法(拉链法)，将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希
   表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除
   的情况。建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

   15、HashMap 的 get 方法能否判断某个元素是否在 map 中？

   HashMap 的 get 函数的返回值不能判断⼀一个 key 是否包含在 map 中，因为 get 返回 null 有可能是不包含该key，也有可能该 key 对应的 value 为 null。因为 HashMap 中允许 key 为 null，也允许 value 为null。

   16、HashMap 与 HashTable 的区别是什么？

4. 线程是否安全： HashMap 是非线程安全的， HashTable 是线程安全的，因为 HashTable 内
   部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用
   ConcurrentHashMap 吧！）；

5. 效率： 因为线程安全的问题， HashMap 要比 HashTable 效率高一点。另外， HashTable
   基本被淘汰，不要在代码中使用；
6. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为
   键只能有⼀个， null 作为值可以有多个； HashTable 不允许有 null 键和 null 值，否则会抛出
   NullPointerException 。
7. 初始容量大小和每次扩充容量大小的不同 ：
   1. 创建时如果不指定容量初始值， Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。 HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
   2. 创建时如果给定了容量初始值，那么Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。
8. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。 Hashtable 没有这样的机制。

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

   为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。
   我们上面也讲到过了， Hash 值的范围值 -2147483648 到 2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射得比较均匀松散，⼀般应用是很难出现碰撞的。但问题是⼀个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是
   “ (n - 1) & hash ”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。、

这个算法应该如何设计呢？
我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了： “取余(%)操作中如果除数是2的幂次则等价于与其除数减⼀的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。 ” 并且采用⼆进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

2的n次方的主要核心原因是hash函数的源码中右移了16位让低位保留高位信息，原本的低位信息不要，那么进行&操作另一个数低位必须全是1，否则没有意义，所以len必须是2^n，这样能实现分布均匀，有效减少hash碰撞！

为了提高HashMap的效率，减少数据的碰撞，使数据分布平均，用之前需要用hash值对数组进行求余运算，算出在数组中的位置，这个计算方法是（length-1）& hash，与hash对数组长度求余结果是一样的，这样效率更高，因为2的n次方是1后边n个0，2的n次方-1，就是n个1，所以为了减少数据碰撞，使分布均匀，需要使得hashmap的长度是2的n次方。

18、HashMap的死循环（jdk 1.8 以下）

Java面试题：高并发环境下，HashMap可能出现的致命问题。注意：是在jdk8以下版本

19、HashMap 的 7 种遍历方式与性能分析

HashMap 的 7 种遍历方式与性能分析

ConcurrentHashMap

万字图文——Concurr entHashMap源码深度解析

1、介绍一下ConcurrentHashMap是怎么实现的？

JDK 1.7中的实现：
在 jdk 1.7 中，ConcurrentHashMap 是由 Segment 数据结构和 HashEntry 数组结构构成，采取分段锁来保证安全性。Segment 是 ReentrantLock 重入锁，在 ConcurrentHashMap 中扮演锁的角色，HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，Segment 的结构和 HashMap 类似，是一个数组和链表结构。

JDK 1.8中的实现：
JDK1.8 的实现已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作，整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。

2、ConcurrentHashMap 的 put 方法执行逻辑是什么？

JDK1.7

• 首先，会尝试获取锁，如果获取失败，利用自旋获取锁；如果自旋重试的次数超过 64 次，则改为阻塞
  获取锁。获取到锁后：
  • 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
  • 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的value。
• 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
• 释放 Segment 的锁。

JDK1.8

• 根据 key 计算出 hash值；
• 判断是否需要进行初始化；
• 定位到 Node，拿到首节点 f，判断首节点 f：
  • 如果为 null ，则通过CAS的方式尝试添加；
  • 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容。
  • 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。

• 当在链表长度达到8的时候，数组扩容或者将链表转换为红黑树。
  

  3、ConcurrentHashMap 和 Hashtable 的区别

  ConcurrentHashMap 和 Hashtable 的区别主要体现在实现「 线程安全 」的方式上不同。

• 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

• 实现线程安全的方式（重要）：
  • 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
  • Hashtable(同一把锁) ：使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：


JDK1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

4、ConcurrentHashMap 线程安全的具体实现方式/底层具体实现？

JDK1.7（上面有示意图）
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 实现了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。
HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

JDK1.8 （上面有示意图）
ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）
synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

5、ConcurrentHashMap 的 get 方法是否要加锁，为什么？

get 方法不需要加锁。因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程A
修改结点的val或者新增节点的时候是对线程B可见的。
这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 安全效
率高的原因之一。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
}

6、get方法不需要加锁与volatile修饰的哈希桶有关吗？

没有关系。哈希桶 table 用volatile修饰主要是保证在数组扩容的时候保证可见性。

7、ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？

我们先来说 value 为什么不能为 null ，因为 ConcurrentHashMap 是用于多线程的 ，如果map.get(key) 得到了 null ，无法判断，是映射的value是 null ，还是没有找到对应的key而为 null 。
而用于单线程状态的 HashMap 却可以用 containsKey(key) 去判断到底是否包含了这个 null 。
我们用反证法来推理：
假设ConcurrentHashMap 允许存放值为 null 的value，这时有A、B两个线程，线程A调用ConcurrentHashMap .get(key)方法，返回为 null ，我们不知道这个 null 是没有映射的 null ，还是存
的值就是 null 。
假设此时，返回为 null 的真实情况是没有找到对应的key。那么，我们可以用ConcurrentHashMap
.containsKey(key)来验证我们的假设是否成立，我们期望的结果是返回false。
但是在我们调用ConcurrentHashMap .get(key)方法之后，containsKey方法之前，线程B执行了
ConcurrentHashMap .put(key, null)的操作。那么我们调用containsKey方法返回的就是true了，这就
与我们的假设的真实情况不符合了，这就有了二义性。
如果面试官不满意，就回答因为作者Doug不喜欢 null ，所以在设计之初就不允许了 null 的key存在。

8、ConcurrentHashMap 的并发度是多少？

在JDK1.7中，并发度默认是16，这个值可以在构造函数中设置。如果自己设置了并发度，
ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度，也就是比如你设置的值
是17，那么实际并发度是32 。

9、ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？

ConcurrentHashMap 的效率要高于Hashtable，因为Hashtable给整个哈希表加了一把大锁从而实现线
程安全。而ConcurrentHashMap 的锁粒度更低，在JDK1.7中采用分段锁实现线程安全，在JDK1.8 中采
用 CAS+Synchronized 实现线程安全。