对比JDK8与JDK7中HashMap的差异
无论是在开发过程中还是在面试准备阶段，HashMap都是一个常见的数据结构工具。本文将深入解析其存取机制以及数据结构实现原理，并从源代码层面探讨其工作原理。
一. HashMap的实现原理
- HashMap遵循hashing原理，在put(key,value)和get(key)方法之间实现存储与检索功能。
- 当进行存储操作时, 键值对会被传递给put(key,value)方法,该方法会利用键对象key的hashCode()计算哈希值,进而定位到对应的桶位置,随后将value存入该桶。
- 在获取数据的过程中, 首先调用key.hashCode()得到哈希码,接着定位到数组对应位置上的桶,随后通过key.equals()验证是否匹配正确的键值对,最终返回相应的value。
- HashMap采用链表解决冲突问题,每当发生碰撞事件时,相关数据会被存放在当前桶中的下一个节点上。具体来说,在每个链表节点中都会保存一个键值对(key-value)。特别地,JDK8及以上版本中如果冲突次数超过8次则会采用红黑树结构来优化查找性能;为了实现数据检索的有效性,必须确保相同的键经hashCode计算后指向同一桶中的节点序列
二.HashMap底层数据结构
上图展示了JDK8之前版本中HashMap作为底层数据结构。该数据结构由数组与链表构成，并且其快速查询性能主要源于通过key计算hashCode值来确定一维数组中的存储位置。在增删操作方面，则依赖于链表实现以确保高效操作。
在JDK1.8版本中，HashMap基于数组、链表及红黑树的组合结构进行优化。具体而言，在HashMap元素数量超过64时（即元素个数>64），若对应的链表长度超过8（即length>8），则采用红黑树数据结构；而当 HashMap 元素数量未超过该阈值时（即元素个数≤64），若对应的链表长度低于或等于6（即length≤6），则重新采用链表结构。
三. 什么是哈希表
在上文中简要介绍了HashMap的数据结构；实际上它们都是基于哈希表实现的。
散列表(Hash Table, 也称为哈希表) 是一种基于键值对（Key-Value）直接存取的数据结构。具体而言，在这种数据结构中，键值通过哈希函数被映射到表中的某个位置以便快速定位对应的值。这种直接存取的方式显著提高了数据查找的速度。其中被用来执行该映射操作的函数即为哈希函数（或称散列函数），而存储这些键值的容器则被称为桶（Bucket）。而像HashMap这样的具体实现正是基于哈希表这一基础数据结构来实现的。
四.哈希冲突解决方案
一般情况下使用哈希表来存储数据时必须面对如何解决哈希冲突的问题那么什么是哈希冲突呢？
当我们通过key计算其hashCode值时，存在两个不同的key被同一个哈希函数映射到同一个hashCode值的情况。这会导致同一时间点将多个不同的键（keys）映射到同一个桶（bucket）中。我们将其称为哈希冲突
解决哈希冲突的方法通常有以下几种：
开放地址法。
探测序列中，在计算得到哈希码发生冲突的情况下类似于后续的桶位置遍历过程来寻找可用空间以存储数据。在现有的探查策略中采用的方法包括线性探查法、平方再散列法以及伪随机探查法。
链地址法
当遇到相同的元素时，通过链表实现元素之间的连接。将每个链表存储到一个数组中，在HashMap数据结构中采用该方法以解决哈希冲突问题。
公共溢出区法
创建一个专用存储区域...用于专门存储存在冲突的数据项。该方案适用于处理数据量及冲突水平较低的情形。
再散列法
设置一组多数量的哈希函数，在当第一个哈希函数发生碰撞时，则会依次采用后续的其他哈希函数进行处理。
五. HashMap源码核心成员变量
在了解HashMap源码之前我们需要明确HashMap中的一些关键成员变量所代表的意义及其功能
JDK7中HashMap核心成员变量 ：
- Entry[] table记录了HashMap核心数据的集合。
- size大小代表映射中键值对的数量。
- capacity容量需要注意的是，在HashMap内部并没有一个成员字段名为capacity。
- threshold阈值与loadFactory装载因子之间存在关系：threshold通常由capacity乘以loadFactory计算得出（虽然在某些实现中可能有所不同）。当实际存储的关键-值对数目(size)达到或超过threshold时（只有当size严格大于threshold时才会触发扩容），HashMap会重新计算每个元素的哈希位置以提高负载效率。
- entrySet、keySet以及values三个集合都是基于table数组生成的视图功能。
JDK8中HashMap核心成员变量 ：
- 该Map使用Node类型的数组存储键值对。
- 键值对的数量。
- 其内部采用数组实现，在默认情况下容量为16。
- threshold阈值与loadFactory装载因子相关联，默认为0.75时计算得到。当达到该阈值时启动红黑树优化。
- entrySet、keySet和values分别提供不同类型的访问视图。
- 当达到该阈值时启动红黑树优化，默认8.
- 当数值低于该阈值时切换回链表结构，默认6.
- 当容量达到或超过该最小阈值时开始进行优化以维持性能，默认最小树化阈值为64.
六.HashMap源码分析
1. JDK7中的HashMap
1) put(key,value)操作
当我们调用put(key, value)方法时观察到，在处理一个空的表时会启动表初始化流程InflateTable(threshold);
如果 key 等于 null，则将 putForNullKey(value) 执行；随后依次检查 table[0] 中是否包含该 key；进而选择将 value 插入或覆盖已存在的记录。
当key不为null时会计算其hash值以确定bucket的位置。随后会遍历所有键并更新对应的值如果没有找到对应的键则会添加新的数据。
在添加数据前会对key进行hash()运算：
通过查看图表可以看出，在jdk7版本中使用hashMap时会经历9次扰动事件。这些扰动事件具体包括5次异或运算和4次位移操作过程较为复杂
计算完hashcode还要判断是否需要扩容：
当size达到或超过threshold值时（其中capacity*loadFactory表示容量乘以负载因子），系统会触发扩容操作。按照原来规模的两倍进行扩展后（即容量翻一番），系统将所有数据元素重新计算其在新表中的位置，并将其存入新表newTable中。同时，在此过程中也会重新计算每个数据元素对应的哈希位置。
最后真正插入数据：
插入Entry的时候采用的是头插法。
最后归纳一下整个put操作的流程图：
2) get(key)操作
获取操作先进行判断key是否为null；若key为null，则调用getForNullKey()方法并在table[0]中进行查找。
key不为null的时候就执行getEntry(key);
先哈希找到bucket，再遍历链表找到对应的entry返回。
整各get(key)流程可以归纳为下图：
2. JDK8中的HashMap
1）put(key,value)操作
调用put(key,value)方法，
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}首先会进行key的hash运算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}jdk1.8中的hash运算进行了两次扰动，分别是一次异或，一次位运算；
接着就是调用putVal()方法：
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)//头结点是null
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) // 变红黑树
treeifyBin(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 key key已经存在进行替换
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//大于阈值则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}该方法大概步骤为：
- 首先判断table成员是否初始化，如果没有，则调用reszie。
- 通过传入键值对的key的hashCode和容量，马上得到了该映射所在的table数组下标。并通过数组的取下标操作，得到该哈希桶的头结点。
- 如果没有发生哈希碰撞(头结点为null)，那么直接执行新增操作。
- 如果发生了哈希碰撞(头结点不为null)那么分为两种情况：
1. 如果与桶内某个元素==返回true，或者equals判断相同，执行替换操作。
2. 如果与桶内所有元素判断都不相等，执行新增操作，可能是链表也可能是红黑树的插入。
在链表新增操作完成后会进行两个判断：首先，在哈希桶为单链表结构的前提下，并且其内部结点数量达到了TREEIFY_THRESHOLD（8），并且当前size达到了或超过MIN_TREEIFY_CAPACITY（64）时，则将其转换为红黑树结构；其次，在新增操作后的size超过threshold时，则会触发resize函数。
下面为put操作的整体流程流程图：
2） get(key)操作
public V get(Object key) {//计算hash
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判断头结点是否为null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//判断是否是红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {//hash相同key相同 就判断equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}首先对key执行hash计算操作后确定在map数组中对应位置的索引
接着检查该索引处的节点是否为空若为空则返回null
如果该节点不为空则进一步验证其键值是否匹配
若所有节点均未满足条件则最终返回null
七. JDK7与JDK8中HashMap区别
总结一下JDK7和JDK8中HashMap的区别:
底层结构
JDK7采用了数组加链表来存放节点数据Entry这一设计特点，在版本更新后JDK8则增添了红黑树结构这一优化措施以提升性能表现。在HashMap元素数量超过64且链表长度超过8时会自动切换为红黑树以避免线性探测问题。
当哈希表处于空状态时，在JDK 7版本中会先启动一个动态数组结构；而在JDK 1.8版本中则直接通过resize()方法进行扩容。
Hash冲突时插入数据
JDK7中采用头插法，JDK8中会将结点插入到链表尾部。
hash函数
在JDK7版本中，默认实现的哈希值计算主要基于key对象的hashCode属性值，并且其计算过程存在一定的复杂性；而在JDK8版本中，则采用了key对象的hashCode值与自身hashCode值经过异或运算后并进行无符号右移16位的操作来确定最终哈希值的方式；这种改进方法不仅提升了哈希算法的整体分散性（即消减碰撞概率），而且简化了计算步骤，在实际应用中表现出较高的稳定性。
扩容方案：在JDK7中实现时需要对哈希值进行重新计算，在JDK8版本时，则无需像J JDK7那样对哈希值进行重新计算。具体来说，只需要查看原哈希值新增的那个比特位是否为1或0即可。如果该比特位为0，则表示索引未发生变化；如果该比特位为1，则表示新的索引应为原索引加上oldCap的值。