HashMap面试题-------深入理解HashMap集合（负载因子、哈希冲突、与HashTable的区别）

“有一天清晨，我扔掉了所有的昨天，从此我的脚步便轻盈了。”🌹

.

HashMap的类结构图

JDK1.7和JDK1.8中的HashMap有什么区别？

JDK1.7中，hashmap的底层数据结构是数组和链表；JDK1.8中，hashmap的底层数据结构是数组、链表以及红黑树。

JDK1.8中，为什么引入了红黑树？

即使哈希函数取得再好，也很难达到元素百分百均匀分布。在JDK1.7中，哈希冲突的解决办法是链表，即在索引处引入一个单链表，这样的话，如果发生哈希冲突的元素比较多，那么链表就会很长，并且遍历的时间复杂度是O(n)，hashmap就失去了优势；但是引入红黑树之后，红黑树遍历的时间复杂度是O(logn)，这样效率比较高

HashMap如何解决哈希冲突？

哈希冲突：不同的值元素，由哈希函数计算出的哈希值（hashcode）相同

解决方案：

• JDK1.7中，在发生哈希冲突的索引处使用链表存放数据
• JDK1.8中，当链表长度大于阈值（默认为8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储

只有当链表长度大于阈值且数组的长度大于64时才会变为红黑树是因为，红黑树中有一些操作比如左旋，右旋，变色等来保持平衡，当数组很小并且阈值也很小的时候，基于这些平衡操作，红黑树的效率并不高；但是当数组长度大于64时，引入红黑树之后，效率就变高了。

什么是负载因子？为什么负载因子设置为0.75？

loadFactor：即我们常说的负载因子，它表示HashMap的疏密程度。

负载因子主要与HashMap的扩容有关，先来说说扩容。

当我们初始化一个HashMap时，数组的大小默认是16，HashMap中还有一个临界值值，临界值 = 数组大小 * 负载因子，当数组大小为16的时候，临界值 = 16 * 0.75 = 12，临界值的作用就是告诉HashMap何时扩容。也就是说，当加入HashMap的元素个数等于12的时候，HashMap会进行扩容，变成原来的两倍，即32。下一次发生扩容的时候，临界值等于32*0.75=24。

所以，你应该明白了吧，0.75的含义就是当加入的元素超过数组大小的75%时，HashMap就应该扩容了。
那么，为什么要当加入的元素超过数组大小的75%时才进行扩容呢？为什么不早点或者不晚点扩容呢？

这是因为，0.75实际上是一个"临界值"，这个值大小适中。如果设置的太小，那么就会过早发生扩容；如果设置的太大，就会过晚发生扩容。而过早发生扩容，数组的利用率就会很低，因为这时候数组中加入的元素还不多；而过晚发生扩容，此时数组中的元素已经变得比较拥挤了，查找的时候效率已经比较低了。

HashMap为什么线程不安全？

首先，HashMap的线程不安全体现在三个方面：多线程下扩容造成的死循环、多线程下扩容造成的数据丢失、数据覆盖。其中，前两个问题在JDK1.8中已经得到解决。

扩容引发的死循环及数据丢失

原因主要存在于transfer函数中。
在JDK1.7中：

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}}

原因就是HashMap在扩容时，采用的是头插法，头插法会将链表的顺序翻转，这是形成死循环关键的地方。

依旧假设此时有两个线程，线程A和线程B。
当线程A执行到newTable[i] = e;时，时间片用完，轮到线程B执行。
此时，线程A中的数据是这样的：

next = 7，e = 3，e.next = null
当线程B执行之后，数据已经成了扩容之后的样子。（见上图）
然后A得到时间片开始执行newTable[i] = e，执行完之后是这样

然后再继续执行，采用头插法：

按照源码继续走，结果如下：

很明显当线程A执行完后，HashMap中出现了环形结构，并且数据5莫名其妙的丢失了。

数据覆盖

死循环以及数据丢失只发生在JDK1.7中，在JDK1.8中已经得到解决。但是在JDK1.8中，多线程情境下会发生数据覆盖的问题。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)//用来判断是否存在hash冲突，如果没有则直接插入tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

假设此时有两个线程，线程A和线程B，它们两个在经过哈希函数计算之后得到的插入下标是相同的，线程A先进行判断（此时线程B还没有插入），但是恰好当线程A在插入数据的前一刻时间片用完，那么线程A就停止运行了；然后线程B得到时间片，在此处插入数据。当线程B插入完成之后，线程A继续运行，由于之前已经判断过了，所以就不会再进行判断了，所以线程A会直接插入。由此所造成的结果就是，线程A后插入的数据覆盖了线程B之前插入的数据。

HashMap、HashTable和ConcurrentHashMap三者的区别？

经过以上分析，我们已经知道HashMap是线程不安全的。
而HashTable是线程安全的，如果看过源码的小伙伴，就知道HashTable中的方法基本上都加了锁。由此所引发的问题就是，HashTable虽然保证了线程安全，但是HashTable在多线程下效率比较低。

concurrenthashmap使用了锁分段技术，容器里有多把锁，每一把锁只锁一部分数据，那么当多线程访问容器里不同数据时，线程间就不存在竞争，可以提高并发访问的效率

整理面经不易，觉得有帮助的小伙伴点个赞吧~感谢收看！