HashMap 总结 | Yao's Blog

HashMap 工作原理

HashMap 基于哈希原理，通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hash()方法来计算 hashcode，然后找到 bucket 位置来储存 Entry 对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap 使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中，当链表的节点数超过了阈值，将会转换为红黑树以提高效率。

工作原理的关键在于 HashMap 是在 bucket 中储存键对象和值对象，作为 Map.Entry。这一点有助于理解获取对象的逻辑。

HashMap 的底层数据结构

在 JDK1.7 中，底层数据结构为“数组+链表”，数组是 HashMap 的主体，链表主要是用来解决哈希冲突。JDK1.8 之后的版本将“链表”进一步修改为“链表+红黑树”。链表和红黑树会在到达一定的条件时自动转换：

链表的长度超过 8 且数组长度超过 64 时才会转换为红黑树；
数组的长度小于 64 时会先进行数组扩容，以减少搜索时间；

链表的搜索时间复杂度为$O(n)$，红黑树的搜索时间复杂度为$O(logn)$，所以当链表过长时会严重影响 HashMap 的效率，但是也不可以直接使用红黑树。红黑树的构造需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。如果一开始就用红黑树结构，元素太少，新增效率又比较慢，非常浪费性能。

HashMap 的 put 流程

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

HashMap 的扩容过程

首先新建一个 HashMap 的底层数组，然后调用transfer()方法，将旧的 HashMap 的全部元素添加到新的 HashMap 中（要重新计算元素在新的数组中的索引位置）。扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用 HashMap 时，最好能提前预估下 HashMap 中元素的个数，这样有助于提高 HashMap 的性能。

两个对象的 hashcode 相同时如何获取对象？

hashcode 相同意味着两个对象的 bucket 位置相同，会发生碰撞。因为 HashMap 使用链表存储包含有键值对的 Map.Entry 对象，所以 hashcode 相同时会先找到对应的 bucket 位置，然后调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

什么是负载因子？负载因子默认值是多少？

负载因子是指当一个 map 填满了一定比例的 bucket 时候，将会创建原来 HashMap 大小的两倍的 bucket 数组，来重新调整 map 的大小，并将原来的对象放入新的 bucket 数组中。

默认的负载因子大小为 0.75，这个数字是对空间和时间的一个平衡选择。较高的负载因子会降低空间开销，但是提高查找成本；同样，较低的负载因子会降低查找成本而提高空间开销。

修改负载因子时应该注意：

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

重新调整 HashMap 大小存在什么问题？

当重新调整 HashMap 大小的时候存在条件竞争，在调用get()方法时会出现死循环。因为如果两个线程都发现 HashMap 需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的 bucket 位置的时候，HashMap 并不会将元素放在链表的尾部，而是放在头部。如果条件竞争发生了，那么就死循环了。但是在 jdk1.8 中，调整大小后节点的相对顺序是不会发生改变的，因此也就不会出现死循环的问题，但是这仍然改变不了 HashMap 仍是非并发安全，在并发下，还是要使用 ConcurrentHashMap 来代替。

为什么 String, Interger 这样的 wrapper 类适合作为键？

String, Interger 这样的 wrapper 类作为 HashMap 的键是再适合不过了，而且 String 最为常用。因为 String 是不可变的，也是 final 的，而且已经重写了equals()和hashCode()方法了。其他的 wrapper 类也有这个特点。不可变性是必要的，因为要计算 hashCode，就要防止键值改变，如果键值在放入时和获取时返回不同的 hashcode 的话，那么就不能从 HashMap 中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个 field 声明成 final 就能保证 hashCode 是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的 hashcode 的话，那么碰撞的几率就会小些，这样就能提高 HashMap 的性能。

“我们可以使用自定义的对象作为键吗？ ”这是前一个问题的延伸。当然你可能使用任何对象作为键，只要它遵守了equals()和hashCode()方法的定义规则，并且当对象插入到 Map 中之后将不会再改变了。如果这个自定义对象时不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。

HashMap 线程不安全的原因

多线程下扩容会出现死循环。JDK1.7 中使用头插法插入元素，会导致环形链表。而在 JDK1.8 中使用尾插法，在扩容时可以保持链表元素原本的顺序，所以不会出现环形链表。
多个线程同时调用put方法时，如果计算出来的索引位置相同，那就会导致前一个 key 被后一个 key 覆盖的情况，从而发生元素丢失。
put和get同时被调用时，可能导致get得到null的结果。例如线程 1 执行put时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行get，就有可能发生这个问题。

HashMap 如何同步？

HashMap 可以通过Map m = Collections.synchronizeMap(hashMap);实现同步。synchronizedMap() 方法返回一个 SynchronizedMap 类的对象，而在 SynchronizedMap 类中使用了 synchronized 来保证对 Map 的操作是线程安全的，故效率其实也不高。

可以直接使用 JDK5 之后的 ConcurrentHashMap。

HashMap 和 Hashtable 的区别？

Hashtable 是基于陈旧的 Dictionary 类的，HashMap 是 Java + 1.2 引进的 Map 接口的一个实现。
Hashtable 是线程安全的，也就是说是同步的，而 HashMap 是线程序不安全的，不是同步。
只有 HashMap 可以让你将空值作为一个表的条目的 key 或 value。

HashMap 和 HashSet 的区别？

HashMap 实现的 Map 接口，HashSet 实现的是 Set 接口。
HashMap 存储键值对，HashSet 存储对象。
添加元素 HashMap 使用put()方法，HashSet 使用add()方法。
HashMap 使用键对象计算哈希值，HashSet 使用成员对象计算哈希值，如果哈希值相等再使用equasl()判等。
HashMap 相对 HashSet 较快，因为是使用唯一的键获取对象。

可以使用 CocurrentHashMap 来代替 Hashtable 吗？

Hashtable 是 synchronized 的，但是 ConcurrentHashMap 同步性能更好，因为它仅仅根据同步级别对 map 的一部分进行上锁。ConcurrentHashMap 当然可以代替 HashTable，但是 HashTable 提供更强的线程安全性。