JAVA中hashMap原理解析
原创
JAVA中hashMap原理解析
原创
在文章开始之前，推荐一些很值得阅读的好文章！感兴趣的也可以去看一下哦！
今日推荐：TCP/IP协议：网络访问层相关知识梳理
文章链接：https://cloud.tencent.com/developer/article/2472596
这篇文章详细梳理了TCP/IP网络访问层，包括其与物理硬件和介质的交互、主要功能（如数据转换、错误检查）、与OSI模型的关系，以及涉及的关键设备（如网卡、集线器、中继器、网桥和交换机）。
核心原理
hashMap底层最核心的是： 数组 + 链表 + 红黑树 结构 ，链表中存储的结构是 Node 节点.
- 入口核心是：数组。
- 每个数组元素是一个链表或红黑树。
- 每个链表元素是一个Node节点封装数据。
注意：当链表长度超过阈值（默认为8）时，链表会转换为红黑树，以减少搜索时间
为什么使用数组+链表？
使用数组+链表来存储hashMap最主要的原因是解决哈希冲突问题。通过数组的时效及链表的空间完成hashmap在时间和空间上的平衡。
处理哈希冲突
我们知道，一个键增加到hashmap中时，会先使用hash算法进行计算应该会存在数组的哪个索引上，当两个或多个键计算出来的索引是一致时，这时候就会存在数据冲突的问题了。为了解决这一问题，所以采用链表来完成冲突时候的存储。即当出现冲突时，将两个或多个值全都存在一个链表中，而数据索引存链表的指针。
动态扩容
数组的大小是固定的，但HashMap需要动态调整大小以保持效率。当HashMap中的元素数量达到一定阈值时，HashMap会进行扩容，创建一个新的更大的数组，并将旧数组中的元素重新哈希到新数组中。链表结构使得重新哈希过程变得相对简单。
空间效率
数组+链表结构相比于纯链表结构，可以更有效地利用空间。数组可以紧凑地存储元素，而链表只在需要时才分配额外的空间。
讲一讲hashmap的原理
着重以put为例讲一下原理。
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("a","v");当我们实例化一个hashmap后，调用put方法时，底层是怎么实现的呢？
put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}put实际调用了putVal，其中有一个hash(key) 也就是实际的存在哪个索引的hash值的计算。
hash(Object key)
我们看看hash(key)这个方法。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}首先调用键的
key.hashCode()方法来获取键的hashCode值。这个值是一个int类型的数值，表示键的哈希码。其次将这个hashCode值与其无符号右移16位的值进行异或运算（
^）。这样做的目的是将hashCode的高位和低位混合起来，以减少由于哈希碰撞导致的链表长度增加。最后处理null值，如果键为null，那么直接返回0。在HashMap中，null键总是存储在数组的第一个位置。
V putVal(int hash,K key,V value, boolean onlyIfAbsent, boolean evict)
先看看putVal的参数分别是：(键对应的hash值结果，键,值，键已经存在时的行为，是否在插入后执行清除操作）
对于键已经存在时的行为主要包括2种行为 ：
如果这个参数为true，那么只有在键不存在时，才会插入新的键值对。
如果为false，那么无论键是否存在，都会插入新的键值对，并且更新旧的值。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 检查哈希表是否为空或长度为0，如果是，则进行初始化或扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据哈希值计算键值对在数组中的索引
if ((p = tab[i = (n - 1) & hash]) == 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) // -1 for 1st
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
V oldValue = e.value;
// 根据onlyIfAbsent参数决定是否更新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 返回旧的值
return oldValue;
}
}
// 更新修改次数
++modCount;
// 如果元素数量超过阈值，进行扩容
if (++size > threshold)
resize();
// 插入后的操作，对于LinkedHashMap等子类可能会用到
afterNodeInsertion(evict);
// 如果没有更新现有节点，返回null
return null;
}
总结一下关于putVal核心的操作
1、如果未初始化数组，则 直接初始化扩容
2、通过 hash 算法，计算出对应key 所在的数组
如果所在数组为null, 则 newNode()
如果不为null,说明是链表：
2.1 获取索引上的链表，判断 当前添加值 在链表中是否存在
如果不存在，则将 新值 插入在链表最前面
如果存在，则覆盖
3 判断size 是否大于 容积 * 加载因子，如果大于，扩容
扩容机制
HashMap的扩容机制是其核心特性之一，它确保了HashMap在元素数量增加时仍能保持高效的性能。
- 当HashMap中的元素数量达到当前容量*负载因子（load factor）时，就会触发扩容。(负载因子是一个介于0和1之间的数值，默认值为0.75)这意味着当HashMap填满了75%时，就会进行扩容。
- 扩容时，会创建一个新的数组，其容量是原数组容量的两倍。目的是为了保持哈希表的扩展性，同时减少哈希冲突的概率。
- 所有现有的键值对都需要重新计算在新数组中的位置，并重新插入到新数组中。这是因为数组的容量变了，哈希值的计算方式也会相应改变（通常是通过取模运算）。
- 在重新哈希的过程中，链表中的元素可能会被重新分布到不同的索引中。如果索引中的元素类型是红黑树，那么红黑树也需要被拆分和重新组织。
注意：扩容是一个影响效率的操作，因为需要对所有的元素进行重新的hash计算，并重新放到新的数组中。所以最好的我们使用new HashMap(16) 时，增加这个入参来指定我们预知的长度。来减少扩容。
线程不安全
HashMap在Java中是非线程安全的。
邀请人：文家齐
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
