Java集合学习：HashMap的原理

一、HashMap里的Hash是什么？

首先，我们先要搞清楚HashMap里的的Hash是啥意思。

当我们在编程过程中，往往需要对线性表进行查找操作。

在顺序表中查找时，需要从表头开始，依次遍历比较a[i]与key的值是否相等，直到相等才返回索引i；在有序表中查找时，我们经常使用的是二分查找，通过比较key与a[i]的大小来折半查找，直到相等时才返回索引i。最终通过索引找到我们要找的元素。

但是，这两种方法的效率都依赖于查找中比较的次数。

那能不能不经过比较，而是直接通过关键字key一次得到所要的结果呢？这时，就有了散列表查找（哈希表）

散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每一个关键字都对应一个存储位置。这样，在查找的过程中，只需要通过这个对应关系f 找到给定值key的映射f（key）。只要集合中存在关键字和key相等的记录，则必在存储位置f（key）处。我们把这种对应关系f 称为散列函数或哈希函数。按照这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址或散列地址。

相信看到这里大家都懂这个Hash是什么意思了，其实就是散列技术，通过一个对应关系快速找到目标值的位置。

二、HashMap是什么？

HashMap是正是基于哈希表的数据结构，用于存储键值对(key-value)。

HashMap基于键的HashCode值唯一标识一条数据，同时基于键的HashCode值进行数据的存取，因此可以快速地更新和查询数据，但其每次遍历的顺序无法保证相同。

HashMap的key和value允许为null。

HashMap是非线程安全的，即在同一时刻有多个线程同时写HashMap时将可能导致数据的不一致。

如果需要满足线程安全的条件，则可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

三、HashMap的底层原理

HashMap的核心原理是将键的哈希值映射到数组索引位置，通过数组+链表（在Java 8及之后是数组+链表或红黑树）来处理哈希冲突。

HashMap使用键的hashCode()方法计算哈希值，并通过indexFor方法（JDK1.7之后版本移除了这个方法，直接使用(n-1) & hash）确定元素在数组中的存储位置。哈希值是经过一定扰动处理的，防止哈希值分布不均匀，从而减少哈希冲突。

1、HashMap的数据结构

HashMap的数据结构如上图所示，其内部是一个数组，数组中的每个元素都是一个单向链表，链表中的每个元素都是嵌套类Entry的实例，Entry实例包含4个属性：key、value、hash值和用于指向单向链表下一个元素的next。

HashMap在查找数据时，根据HashMap的Hash值可以快速定位到数组的具体下标，但是在找到数组下标后需要对链表进行顺序遍历直到找到需要的数据，时间复杂度为O(n)。为了减少链表遍历的开销，Java 8对HashMap进行了优化，将数据结构修改为数组+链表或红黑树。在链表中的元素超过8个以后，HashMap会将链表结构转换为红黑树结构以提高查询效率，红黑树是一种自平衡二叉搜索树，能够将最坏情况下的查询复杂度从O(n)降低到O(log N)。如果树中元素的数量低于6个，红黑树会转换回链表，以减少不必要的树操作开销。

Java 8 HashMap的数据结构如下图所示：

2、hashCode()和equals()的重要性

HashMap的键必须实现hashCode()和equals()方法。hashCode()用于计算哈希值，以决定键的存储位置，而equals()用于比较两个键是否相同。在put操作时，如果两个键的hashCode()相同，但equals()返回false，则这两个键会被视为不同的键，存储在同一个桶的不同位置。

误用hashCode()和equals()会导致HashMap中的元素无法正常查找或插入

3、默认容量与负载因子的选择

HashMap常用的参数如下：

• capacity：当前数组的容量，默认为16，可以扩容，扩容后数组的大小为当前的两倍，因此该值始终为2n。
• loadFactor：负载因子，默认为0.75。
• threshold：扩容的阈值，其值等于capacity×loadFactor。

默认容量是16，负载因子是0.75，这个组合是在性能和空间之间找到平衡。较高的负载因子会减少空间浪费，但增加了哈希冲突的概率；较低的负载因子会增加空间开销，但减少哈希冲突。

如果已知HashMap的容量需求，建议提前设定合适的初始容量，以减少扩容带来的性能损耗。

4、哈希冲突链表法

当要塞入一个键值对的时候，会根据一个hash算法计算key的hash值，然后通过数组大小n-1 & hash值之后，得到一个数组的下标，然后往那个位置塞入这个键值对

hash算法是可能产生冲突的，且数组的大小是有限的，所以很可能通过不同的key计算得到一样的下标，因此为了解决键值对冲突的问题，采用了链表法：

在JDK1.7及之前链表的插入采用的是头插法，即每当发生哈希冲突时，新的节点总是插入到链表的头部，老节点依次向后移动，形成新的链表结构。

多线程的情况下，头插法可能会导致链表形成环，特别是在并发扩容时。

在JDK1.8的时候，改成了尾插法，即新节点插入到链表的尾部，保持插入的顺序。