[HashMap]模拟put/get操作流程助你理解高频考点HashMap

前言在 Java 中Map 是一种非常重要的数据结构用于存储 键值对key-value它提供了根据 key 快速查找对应 value 的能力。常见的 Map 实现类有 HashMap、Hashtable、TreeMap 等。与 List、Set 等集合不同Map 不关注元素的顺序而是关注 通过 key 高效访问数据。在日常开发和面试中HashMap 几乎是不可回避的核心考点。本篇文章将从模拟一次HashMap中put和get操作来引入HashMap1.7和1.8版本不同的底层数据结构扩容机制线程安全HashMap基础与原理HashMap内部结构在JDK1.7之前HashMap的底层是数组链表。HashMap通过哈希算法将元素的键key映射到数组中的槽位Bucket。如果多个键映射到同一个槽位会以链表的形式存储的同一给槽位上这就是1.7版本的映射流程这带来的后果是当一个索引上的链表很长时效率就特别低了。因为链表的查询效率时On于是1.8版本时候就进行了改进。当某个桶的链表长度8且哈希表数组长度64时自动转换为红黑树结果就是时间复杂度降低成了O(log n);put/get流程get作用传入我们需要获取的节点key返回valuepublicVget(Objectkey){NodeK,Ve;return(egetNode(hash(key),key))null?null:e.value;}put用于向HashMap中添加键值对具体调用流程如下根据要添加的键的哈希码计算在数组中的位置检查给位置是否为空若为空在该位置创建一个新的Node对象来存储键值对。将要添加的键值对作为该Node的键和值如果改位置已经存了其他键值对检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同若相同直接替换掉旧值完成更新如果不同则需遍历链表或红黑树来查找是否有相同的键如果是链表从表头逐个比较键的哈希码和equal()方法直到找到或达到链表末尾如果是红黑树在红黑树中使用哈希码和equal()方法进行查找。添加方法如上检查链表长度是否达到阈值8如果链表长度超过阈值且数组长度超过64自动将链表转化为红黑树检查负载因子是否超过阈值0.75如果键值对的数量与数组的长度的比值阈值则触发扩容扩容操作创建一个新的两倍大小的数组遍历就数组中的每一个键值对将遍历到的结果重新分配到新数组的位置要么原位置要么 原位置 oldCap无需重新计算hash这一点在下面会具体讲解完成添加操作总结put流程需要注意的点一共有两种链表切换成红黑树以及扩容的触发时机两者时机要进行区分一个是链表长度一个是数组长度。以及扩容逻辑与具体操作上面我们了解了put/get的具体流程接下来讲述的是上述流程的一些具体细节key的要求我们在上面了解了get操作流程通过key值定位找到value。那么有哪些类型适合作为key呢一般用string作为key因为String对象是不可变的一旦创建旧不能被修改这确保了key的稳定性key可以为null当使用hash方法时且key为null。直接令key的哈希值为0不走key.hashCode()方法hashmap虽然支持key和value为null但null作为key只能有一个null作为value可以有多个。总结key可以为null但是只能由一个一般用String类型作为key因为String是不可变类型扩容逻辑回到put流程扩容操作的问题在这里我们具体聊聊触发扩容有哪些因素hashMap默认的负载因子是0.75即如果hashmap中的元素个数超过了总容量75%负载因子太低会导致大量的空桶浪费空间负载因子太高会导致大量的碰撞降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。则会触发扩容扩容分为两个步骤对哈希表长度的扩展2倍将旧哈希表中的数据放到新的哈希表中因为扩容是2倍扩容所以元素的位置不是在原位就是在原位再次移动2次幂的位置例如将16位扩容至32位时因此我们在扩充HashMap的时候不需要重新计算hash只需要看看原来的hash值新增的那个bit是1还是0就好了是0的话索引没变是1的话索引变成“原索引oldCap”HashMap在多线程下的问题1.7中的HashMap使用头插法插入元素在多线程环境下扩容的时候可能导致环形链表形成死循环。所以1.8使用尾插法插入元素在扩容时会保持链表元素原本的顺序不会出现环形链表问题。但是多线程同时put操作如果计算出来的索引位置相同又叫哈希冲突会造成前一个key被后一个key覆盖从而导致元素丢失解决方式多线程环境可以使用Collections.synchronizedMap同步加锁的方式还可以使用Hashtable但是同步的方式显然性能不达标而ConurrentHashMap更适合高并发场景使用。ConcurrentHashmap在JDK1.7和1.8的版本改动比较大1.7使用SegmentHashEntry分段锁的方式实现1.8则抛弃了Segment改为使用CASsynchronizedNode实现同样也加入了红黑树避免链表过长导致性能的问题。HashMap的优缺点优点快速查找 平均时间复杂度为O(1)。灵活 可以存储不同类型的对象允许null键和值。缺点非线程安全 多线程情况下需要手动同步。不保证顺序 插入顺序和遍历顺序可能不同。