一、HashMap实现原理

HashMap 的实现主要包括两个部分：哈希函数和解决哈希冲突的方法。

1.哈希函数

当使用 put() 方法将键值对存储在 HashMap 中时，首先需要计算键的哈希值。HashMap 使用 hashCode() 方法获取键的哈希值，并将其转换为桶（bucket）的索引位置。具体的哈希函数实现可能会因 JVM 和 Java 版本而异。

2.解决哈希冲突的方法

由于不同的键可能具有相同的哈希值，因此 HashMap 需要一种方法来处理这种情况。HashMap 使用链表或红黑树等数据结构来存储具有相同哈希值的键值对。如果桶中已经存在一个键，则新的键值对将添加到该键所在的链表或红黑树中。如果没有任何键与当前键具有相同的哈希值，则新的键值对将直接添加到桶中。

3.扩容机制

当存储在 HashMap 中的键值对的数量超过负载因子乘以散列表容量时，HashMap 将自动扩容。在扩容时，HashMap 会创建一个新的桶数组，并通过重新哈希化将所有键值对复制到新的桶中。这可以确保哈希函数仍然能够正常工作，并且具有足够的空间来存储新的键值对。

以下是jdk1.7与jdk1.8中hashmap的区别：

	JDK1.7	JDK1.8
存储	数组+链表	数组+链表+红黑树
位置算法	h & (length-1)	h & (length-1)
链表超过8	链表	红黑对(链表超过8且数组长度超64)
节点结构	Entry<K,V> implements Map.Entry<K,V>	Node<K,V> implements Map.Entry<K,V>
插法	头插法(扩容环化造成死循环)	尾插法

1、JDK1.7

使用一个Entry数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode取模后的结果相同，那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表；这样数据遍历时间就过长。1.7中hashmap链表插入的方式是使用头插法。

​

2、JDK1.8

使用一个Node数组来存储数据，但是这个Node可能是链表结构，也可能是红黑树结构；如果插入的元素key的hashcode值相同，那么这些key也会被定位到Node数组的同一个格子里，如果不超过8个使用链表存储，超过8个且Node数组长度超过64，会将链表转换为红黑树。1.8中hashmap链表插入的方式是使用尾插法。

二、相关问题

【问题一】为什么jdk1.8后改为尾插法？

主要是因为头插法在多线程扩容情况下会引起链表环。那什么是链表环呢？

线程1，第一节点为A，第二节点为B后面就没有了，遍历过程为A->B然后B没有后面节点即遍历结束。

这时线程1挂起。线程2引发扩容，扩容后为B->A。这时线程1遍历就会发现A的下一节点是B，会发现遍历B时B还有后续的节点为A，这样就出样链表环了。

【问题二】什么是HashMap，它的工作原理是什么？

HashMap是Java集合框架中的一种实现，可以用来存储键值对。HashMap使用哈希表来实现，它通过将键映射到哈希表中的一个位置来存储和访问值。

【问题三】HashMap如何处理哈希冲突？

当两个键映射到哈希表中的同一个位置时，称为哈希冲突。HashMap使用链地址法来处理哈希冲突，即在哈希表中每个桶都维护一个链表，所有哈希值相同的键值对都被放置在这个链表中。

【问题四】HashMap的初始容量和负载因子是什么意思？它们对HashMap的性能有什么影响？

初始容量表示哈希表在创建时包含的桶数。负载因子是哈希表在自动扩容之前可以达到的平均填充因子的阈值。默认情况下，初始容量为16，负载因子为0.75。如果元素数量超过了容量*负载因子，哈希表将自动扩容，这可能会导致性能下降。

【问题五】如何实现一个线程安全的HashMap？

可以使用ConcurrentHashMap类来实现线程安全的HashMap。ConcurrentHashMap使用锁分段技术来实现线程安全，即将哈希表分成多个段，每个段上都有一个锁，不同的线程可以同时访问不同的段。

【问题六】HashMap与Hashtable有什么区别？

HashMap和Hashtable都是用来存储键值对的集合类，它们的主要区别在于：

• 线程安全性：Hashtable是线程安全的，而HashMap不是。因此，在多线程环境下，如果需要使用Map来存储数据，应该使用ConcurrentHashMap而不是HashMap。

• null值：Hashtable不允许键或值为null，而HashMap允许。

• 性能：Hashtable比HashMap慢，这是因为Hashtable的方法是同步的，而HashMap的方法不是。

本文正在参加「金石计划」