图文并茂java源码解析-HashMap

HashMap结构

java7用的数组+链表
java8用的数组+链表+红黑树
因为数组有定位快，增加元素快，但是remove费劲的特点，链表有删除元素快，头尾增加快，但是定位元素慢的特点，因此HashMap结合两者优点应运而生.在实际中应用很多！

HashMap的Entry

Entry存储了K，V，Hash，以及下一个Entry的引用。

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键(Key)映射到数组中的槽位(Bucket)。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以hash冲突很严重，一个索引上的链表非常长，效率就很低了。
所以在 JDK 1.8 版本的时候做了优化，当一个链表（不算桶）的$L\ge 8$的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度$O(logn)$，可以提高查询性能，但是在数量较少时，即数量（不算桶）$L\le 6$时，会将红黑树转换回链表。

了解的哈希冲突解决方法有哪些?

• 链接法:使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
• 开放寻址法:在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括
  线性探测、二次探测和双重散列。
• 再哈希法(Rehashing):当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
• 哈希桶扩容:当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap是线程安全的吗?

hashmap不是线程安全的，hashmap在多线程会存在下面的问题:

• JDK 1.7 HashMap 采用数组 +链表的数据结构，多线程背景下在数组扩容的时候，存在 Entry 链死循环和数据丢失问题。
• JDK 1.8 HashMap 采用数组 +链表+红黑二又树的数据结构，优化了 1.7 中数组扩容的方案，解决了 Entry 链死循环和数据丢失问题。但是多线程背景下，put 方法存在数据覆盖的问题。
  如果要保证线程安全，可以通过这些方法来保证:
• 多线程环境可以使用Collections.synchronizedMap同步加锁的方式，还可以使用HashTable，但是同步的方式显然性能不达标，而ConurrentHashMap更适合高并发场景使用。
• ConcurrentHashmap在JDK1.7和1.8的版本改动比较大，1.7使用Segment+HashEntry分段锁的方式实现，1.8则抛弃了Segment改为使用CAS+synchronized+Node实现，同样也加入了红黑树避免链表过长导致性能的问题。

hashmap的put过程介绍一下

jdk8的获取hash的方法

把原来key的HashCode方法得到的值存到h里面，然后h ^ (h>>>16),意思是把h无符号右移16位，把原来h的16位高位挪到16低位里面，然后高位16用0填充这个数我们用h2存储，h2 = h>>>16,然后h ^ h2，这样h ^ h2得到的才是hash结果。这样操作充分利用到了key的高位，可以更加的随机位置插入元素了

jdk8的获取索引的方法

先保证数组长度n始终为$2^k,k\in 自然数N\ge 4$，一般来说默认无参构造函数创建数组长度16，负载因子0.75.
当数组长度始终为2的k次幂的时候，$(n-1)\&hash$等于 $hash\%n$，计算机里面%运算比减法和&运算的复合复杂度要高，因此采用$(n-1)\&hash$的方式获取索引！此乃结论！直接硬背！

hashmap的put过程介绍一下

第一步:根据要添加的键的哈希码计算在数组中的位置(索引)。
$(n-1)\&hash$

第二步:检查该位置是否为空(即没有键值对存在
如果为空，则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的K和V，并保存在数组的对应位置。将HashMap的修改次数(modCount)加1，以便在进行迭代时发现并发修改。

第三步:如果该位置已经存在其他KV对，检查该位置的第一个KV对的哈希码和K是否与要添加的KV对的K相同?
如果相同，则表示找到了相同的键，直接将新的V替换旧的V完成更新操作。

第四步:如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键

1. 如果KV对集合是链表List结构，从链表的头部开始逐个比较K的哈希码和equals()方法，直到找到相同的键或达到链表末尾。

• 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
• 如果没有找到相同的键，则将新的Entry添加到链表的头部。

2. 如果键值对集合是红黑树R结构，在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。

• 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
• 如果没有找到相同的键，则将新的Entry添加到红黑树中。

上图第二个大红框里面判断e.hash == hash的理由是：为了快速过滤掉那些明显不可能匹配的节点

1. 性能优化:
   快速排除不匹配的节点: 通过比较哈希值，可以快速排除那些哈希值不同的节点，避免不必要的 equals 方法调用。equals 方法通常涉及更多的计算和内存访问，因此比较哈希值可以显著提高性能。
   减少 equals 调用次数: 如果哈希值不同，那么键肯定不同，不需要进一步调用 equals 方法。只有当哈希值相同时，才需要进一步检查键是否相等。
2. 正确性:
   确保键的唯一性: 即使两个不同的对象可能具有相同的哈希值（哈希碰撞），但它们的键必须完全相同才能被认为是同一个键。因此，先比较哈希值可以确保在调用 equals 方法之前，已经排除了大部分不匹配的情况。

其实我感觉hash值不一样也会导致$(n-1)\&hash$映射到同一位置
$has{h}_1\ne has{h}_2,id{x}_1=id{x}_2$
举个例子，
$has{h}_1\&(n-1)\to id{x}_1$
$has{h}_2\&(n-1)\to id{x}_2$

第五步:检查链表长度是否达到阈值(默认为8)
如果链表长度超过阈值，且HashMap的数组长度大于等于64，则会将链表转换为红黑树，以提高查询效率。如果链表长度L＞=8且HashMap长度小于64，则执行扩容resize（注意这里ConcurrentHashMap的也是一样的，put元素时数组长度＞=64才转List为RB-Tree，否则扩容）

第六步:检查负载因子是否超过阈值(默认为0.75):
如果键值对的数量(size)与数组的长度的比值大于阈值，则需要进行扩容操作。

第七步:扩容操作:(可选，非必要，仅当超过负载因此时才扩容)
创建一个新的两倍大小的数组。
将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。
更新HashMap的数组引用和阈值参数。

此外，HashMap是非线程安全的，如果在多线程环境下使用，需要采取额外的同步措施或使用线程安全的ConcurrentHashMap。

hashmap 调用get方法一定安全吗?

不是，调用 get 方法有几点需要注意的地方
空指针异常(NullPointerException):如果你尝试用 null 作为键调用 get方法，而Hashmap 没有被初始化(即为null),那么会抛出空指针异常。不过，如果Hashmap 已经初始化，使用 null 作为键是允许的，因为Hashmap支持 null 键。
线程安全HashMap 本身不是线程安全的。如果在多线程环境中，没有适当的同步措施，同时对Hashmap 进行读写操作可能会导致不可预测的行为。例如，在一个线程中调用get 方法读取数据，而另一个线程同时修改了结构(如增加或删除元素)，可能会导致读取操作得到错误的结果或抛出ConcurrentModificationException。如果需要在多线程环境中使用类似 HashMap的数据结构，可以考虑使用
ConcurrentHashMap

HashMap一般用什么做Key?为啥String适合做Key呢?

用 string 做 key，因为 String对象是不可变的，一旦创建就不能被修改，这确保了Key的稳定性。如果Key是可变的，可能会导致hashCode和equals方法的不一致，进而影响HashMap的正确性。

为什么HashMap要用红黑树而不是平衡二叉树?

• 平衡二叉树追求的是一种“完全平衡”状态:任何结点的左右子树的高度差不会超过1，优势是树的结点是很平均分配的。这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
• 红黑树不追求这种完全平衡状态，而是追求一种“弱平衡”状态:整个树最长路径不会超过最短路径的2倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整这也是我们为什么大多数情况下使用红黑树的原因。

hashmap key可以为null吗?

可以为 null。

• hashMap中使用hash()方法来计算key的哈希值，当key为空时，直接另key的哈希值为0，不走key.hashCode()方法
• hashMap虽然支持key和value为nul，但是nul作为key只能有一个，null作为value可以有多个;
• 因为hashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。

hashmap用头插法还是尾插法？

jdk1.7 头插法，多线程会环形链表
jdk1.8 尾插法

列举HashMap在多线程下可能会出现的问题?

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

重写HashMap的equal和hashcode方法需要注意什么?

HashMap使用Key对象的hashCode()和equals方法去决定key-value对的索引。当我们试着从HashMap中获取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，在这种情况下，两个不同Key也许会产生相同的hashCode()和equals()输出，HashMap将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方
同样的，所有不允许存储重复数据的集合类都使用hashCode0和equals()去查找重复，所以正确实现它们非常重要。equals()和hashCode()的实现应该遵循以下规则:
·如果o1.equals(o2)，那么o1.hashCode()== o2.hashcode()总是为true的。
如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。

重写HashMap的equal方法不当会出现什么问题?

HashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。
所以 equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等(比如散列冲突的情况)
重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回false，这样的一个后果会导致在hashmap等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与hashmap只能有唯一的key的规范不符合。

HashMap的扩容机制介绍一下

hashMap默认的负载因子是0.75，即如果hashmap中的元素个数超过了总容量75%，则会触发扩容，扩容分为两个步骤:

• 第1步 是对哈希表长度的扩展(2倍)
• 第2步 是将旧哈希表中的数据放到新的哈希表中。
  因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
  如我们从16扩展为32时，具体的变化如下所示:
  注意我这里
  $has{h}_1和has{h}_2$只是任意举的例子，随便拿俩key出来举例，有一个例子是“原来索引的例子”，有一个是“原来索引位置+oldCap”的例子，你仔细看一眼n = 16 和n = 32的情况，
  

在扩容过程中，树化要满足两个条件：

1. 链表长度大于等于 TREEIFY_THRESHOLD（8）
2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY （64）第一个条件比较好理解，这里就不说了。这里来说说加入第二个条件的原因，个人觉得原因如下：
   当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。

往hashmap存20个元素，会扩容几次?

当插入 20 个元素时，HashMap 的扩容过程如下
初始容量: 16
插入第 1到第 12 个元素时，不需要扩容。插入第 13 个元素时，达到负载因子限制，需要扩容。此时，HashMap 的容量从 16 扩容到 32。
扩容后的容量： 32
插入第 14 到第 24 个元素时，不需要扩容。
因此，总共会进行一次扩容。

说说hashmap的负载因子

HashMap 负载因子 loadFactor 的默认值是 0.75，当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。
默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。
负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

Hashmap和Hashtable有什么不一样的?

Hashmap一般怎么用?

• HashMap线程不安全，效率高一点，可以存储nul的key和value:null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值(默认为8)，先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
• HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
• 怎么用:HashMap主要用来存储键值对，可以调用put方法向其中加入元素，调用get方法获取某个键对应的值，也可以通过containsKey方法查看某个键是否存在等v