-
追问6：链表红黑树如何互相转换？阈值多少？
-
面试题2：HashMap是线程安全的吗？
-
- 正经回答：
-
- 追问1：你是如何解决这个线程不安全问题的？
-
追问1：ConcurrentHashMap 底层具体实现知道吗？和Hashtable有哪些区别？
-
追问2：你能给我说说ConcurrentHashMap分段锁的实现原理吗？
-
每日小结
本栏目Java开发岗高频面试题主要出自以下各技术栈：Java基础知识、集合容器、并发编程、JVM、Spring全家桶、MyBatis等ORMapping框架、MySQL数据库、Redis缓存、RabbitMQ消息队列、Linux操作技巧等。
面试题1：说一下 HashMap 的实现原理？
======================================================================================
正经回答：
众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry（包括Key-Value），其中Key 和 Value 允许为null。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。另外，HashMap数组每一个元素的初始值都是Null。
值得注意的是：HashMap不能保证映射的顺序，插入后的数据顺序也不能保证一直不变（如扩容后rehash）。
要说HashMap的原理，首先要先了解他的数据结构，
如上图为JDK1.8版本的数据结构，其实HashMap在JDK1.7及以前是一个“链表散列”的数据结构，即数组 + 链表的结合体。JDK8优化为：数组+链表+红黑树。
我们常把数组中的每一个节点称为一个桶。当向桶中添加一个键值对时，首先计算键值对中key的hash值（hash(key)），以此确定插入数组中的位置（即哪个桶），但是可能存在同一hash值的元素已经被放在数组同一位置了，这种现象称为碰撞，这时按照尾插法(jdk1.7及以前为头插法)的方式添加key-value到同一hash值的元素的最后面，链表就这样形成了。
当链表长度超过8(TREEIFY_THRESHOLD - 阈值)时，链表就自行转为红黑树。
注意：同一hash值的元素指的是key内容一样么？不是。根据hash算法的计算方式，是将key值转为一个32位的int值（近似取值），key值不同但key值相近的很可能hash值相同，如key=“a”和key=“aa”等。
通过上述回答的内容，我们明显给了面试官往深入问的多个诱饵，根据我们的回答，下一步他多可能会追问这些问题：
1、如何实现HashMap的有序？
4、put方法原理是怎么实现的？
6、扩容机制原理 → 初始容量、加载因子 → 扩容后的rehash（元素迁移）
2、插入后的数据顺序会变的原因是什么？
3、HashMap在JDK1.7-JDK1.8都做了哪些优化？
5、链表红黑树如何互相转换？阈值多少？
7、头插法改成尾插法为了解决什么问题？
而我们，当然是提前准备好如何回答好这些问题！当你的回答超过面试同学的认知范围时，主动权就到我们手里了。
深入追问：
追问1：如何实现HashMap的有序？
使用linkedHashMap 或 TreeMap。
linkedHashMap内部维护了一个单链表，有头尾节点，同时linkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。
transient linkedHashMap.Entry
transient linkedHashMap.Entry
//将加入的p节点添加到链表末尾
private void linkNodeLast(linkedHashMap.Entry
linkedHashMap.Entry
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
//linkedHashMap的节点类
static class Entry
Entry
Entry(int hash, K key, V value, Node
super(hash, key, value, next);
}
}
示例代码：
public static void main(String[] args) {
Map
linkedMap.put(“1”, “占便宜”);
linkedMap.put(“2”, “没够儿”);
linkedMap.put(“3”, “吃亏”);
linkedMap.put(“4”, “难受”);
for(linkedMap.Entry
System.out.println(item.getKey() + “:” + item.getValue());
}
}
输出结果:
1:占便宜
2:没够儿
3:吃亏
4:难受
追问2：那TreeMap怎么实现有序的？TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。
-
TreeMap实现了SortedMap接口，它是一个key有序的Map类。
-
要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。
TreeMap
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});
追问3：put方法原理是怎么实现的？
该条问答摘自 安琪拉的博客（https://blog.csdn.net/zhengwangzw/article/details/104889549）
-
判断数组是否为空，为空进行初始化;
-
不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
-
查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
-
存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
-
如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)
-
如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8并且数组长度大于64， 大于的话链表转换为红黑树；
-
插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。
下面我们看看源码中的内容：
public V put(K key, V value) {
//putVal方法的实现就在下面
return putVal(hash(key), key, value, false, true);
}
从源码中可以看到，
《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》
【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享
put(K key, V value)可以分为三个步骤：
-
通过hash(Object key)方法计算key的哈希值。
-
通过putVal(hash(key), key, value, false, true)方法实现功能。
-
返回putVal方法返回的结果。
那么看看putVal方法的源码是如何实现的？
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node
//如果哈希表为空，调用resize()创建一个哈希表，并用变量n记录哈希表长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果指定参数hash在表中没有对应的桶，即为没有碰撞
if ((p = tab[i = (n - 1) & hash]) == null)
//直接将键值对插入到map中即可
tab[i] = newNode(hash, key, value, null);
else {
Node
//如果碰撞了，且桶中的第一个节点就匹配了
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将桶中的第一个节点记录起来
e = p;
//如果桶中的第一个节点没有匹配上，且桶内为红黑树结构，则调用红黑树对应的方法插入键值对
else if (p instanceof TreeNode)
e = ((TreeNode
//不是红黑树结构，那么就肯定是链式结构
else {
//遍历链式结构
for (int binCount = 0; ; ++binCount) {
//如果到了链表尾部
if ((e = p.next) == null) {
//在链表尾部插入键值对
p.next = newNode(hash, key, value, null);
//如果链的长度大于TREEIFY_THRESHOLD这个临界值，则把链变为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//跳出循环
break;
}
//如果找到了重复的key，判断链表中结点的key值与插入的元素的key值是否相等，如果相等，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
//如果key映射的节点不为null
if (e != null) { // existing mapping for key
//记录节点的vlaue
V oldValue = e.value;
//如果onlyIfAbsent为false，或者oldValue为null
if (!onlyIfAbsent || oldValue == null)
//替换value
e.value = value;
//访问后回调
afterNodeAccess(e);
//返回节点的旧值
return oldValue;
}
}
//结构型修改次数+1
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
//插入后回调
afterNodeInsertion(evict);
return null;
}
追问4：HashMap扩容机制原理
- capacity 即容量，默认16。
- loadFactor 加载因子，默认是0.75
- threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。
-
一般情况下，当元素数量超过阈值时便会触发扩容（调用resize()方法）。
-
每次扩容的容量都是之前容量的2倍。
-
扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
这里我们以JDK1.8的扩容为例：
HashMap的容量变化通常存在以下几种情况：
-
空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。
-
有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让 阈值 = 容量 x 加载因子 。（因此并不是我们手动指定了容量就一定不会触发扩容，超过阈值后一样会扩容！！）
-
如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，加载因子0.75不变）
此外还有几个点需要注意：
-
首次put时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容；可见首次扩容可能会调用两次resize()方法。
-
不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；
扩容时，要扩大空间，为了使hash散列均匀分布，原有部分元素的位置会发生移位。
JDK7的元素迁移
JDK7中，HashMap的内部数据保存的都是链表。因此逻辑相对简单：在准备好新的数组后，map会遍历数组的每个“桶”，然后遍历桶中的每个Entity，重新计算其hash值（也有可能不计算），找到新数组中的对应位置，以头插法插入新的链表。
- 这里有几个注意点：
是否要重新计算hash值的条件这里不深入讨论，读者可自行查阅源码。
因为是头插法，因此新旧链表的元素位置会发生转置现象。
元素迁移的过程中在多线程情境下有可能会触发死循环（无限进行链表反转）。
