文章目录
- Java中的HashMap
- 什么是HashMap?
- 对比其他Map中put()方法
- HashMap中put()方法使用示例
- HashMap中put()源码解析
- 手绘流程图
- 实现原理
- 源码探究(JDK 1.8)
- 设计put()的意义
- 总结
Java中的HashMap
什么是HashMap?
HashMap是Java中常用的数据结构之一,它基于哈希表实现,提供了快速的键值对存取能力。在HashMap中,put方法是最常用的方法之一,用于将键值对存储到HashMap中。本文将深入探究HashMap的put方法的实现原理,解析其内部数据结构和算法,并探讨设计put方法的意义。
对比其他Map中put()方法
可以看一下博主的博客了解HashMap、TreeMap和LinkedHashMap三者的使用:Java-数据结构(二)-Map:HashMap、TreeMap、LinkedHashMap
HashMap、TreeMap和LinkedHashMap都是Java中常用的Map实现类,它们在put方法的实现上有一些区别。
-
HashMap的put方法:
- HashMap使用哈希表来存储键值对,通过键的哈希码和哈希函数来确定键值对在哈希表中的存储位置。
- 当发生哈希冲突时,HashMap使用链表或红黑树来解决冲突。
- HashMap的put方法具有O(1)的平均时间复杂度。
-
TreeMap的put方法:
- TreeMap使用红黑树来存储键值对,根据键的自然顺序或自定义比较器来进行排序。
- 在插入键值对时,TreeMap会根据键的顺序将键值对插入到相应的位置,以保持有序性。
- TreeMap的put方法具有O(log n)的时间复杂度。
-
LinkedHashMap的put方法:
- LinkedHashMap继承自HashMap,底层仍然使用哈希表来存储键值对。
- LinkedHashMap在HashMap的基础上,使用双向链表来维护键值对的插入顺序或访问顺序。
- 在插入键值对时,LinkedHashMap会将键值对插入到链表的尾部,以保持插入顺序或访问顺序。
- LinkedHashMap的put方法具有O(1)的平均时间复杂度。
- HashMap的put方法使用哈希表来存储键值对,适用于需要高效存储和查找键值对的场景。
- TreeMap的put方法使用红黑树来存储键值对,适用于需要有序存储和查找键值对的场景。
- LinkedHashMap的put方法在HashMap的基础上,使用双向链表来维护插入顺序或访问顺序,适用于需要保持插入顺序或访问顺序的场景。
HashMap中put()方法使用示例
以下是一个简单的Java代码示例,展示了如何使用HashMap的put方法:
import java.util.HashMap; public class HashMapExample { public static void main(String[] args) { // 创建一个HashMap对象 HashMap
hashMap = new HashMap<>(); // 使用put方法添加键值对 hashMap.put("apple", 1); hashMap.put("banana", 2); hashMap.put("cherry", 3); // 使用get方法获取键对应的值 int value = hashMap.get("banana"); System.out.println("The value of 'banana' is: " + value); } } HashMap中put()源码解析
手绘流程图
(源文件删掉了,备注:有一条线画错了<在比较完key是否与插入的key一样,若相同就直接使用插入的值p替换掉旧的值e,会直接return出去,不会再进行++modCount操作>)
实现原理
在Java中,HashMap的put方法的实现原理可以分为以下几个步骤:
1.首先,根据键的哈希值计算出键的哈希码。HashMap使用键的哈希码来确定键值对在哈希表中的存储位置。
2.接下来,通过哈希码计算出键值对在哈希表中的索引位置。HashMap使用一个称为“哈希函数”的算法来计算索引位置。常用的哈希函数是将哈希码与哈希表的容量进行取模运算,得到索引位置。
3.如果该索引位置上没有其他键值对,则直接将键值对存储在该位置上。如果该索引位置上已经存在其他键值对,则发生了“哈希冲突”。
4.当发生哈希冲突时,HashMap使用链表或红黑树来解决冲突。在JDK1.8之前,HashMap使用链表来解决冲突,即在冲突的索引位置上,将新的键值对插入到链表的尾部。而在JDK1.8及以后的版本中,当链表长度超过一定阈值时,HashMap会将链表转换为红黑树,以提高查找效率。
5.最后,将键值对成功存储在哈希表中,并返回先前关联的值(如果存在)。如果该索引位置上已经存在其他键值对,则需要遍历链表或红黑树,找到对应的键值对,并更新其值。
通过以上步骤,HashMap的put方法成功将键值对存储在哈希表中。需要注意的是,当哈希表的负载因子(即存储的键值对数量与容量的比值)超过一定阈值时,HashMap会进行扩容操作,以保持哈希表的性能。
源码探究(JDK 1.8)
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node
[] tab; Node p; int n, i; // table未初始化或者长度为0,进行扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash 确定元素存放在哪个桶中,桶为空,新生成结点放入桶中(此时,这个结点是放在数组中) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 桶中已经存在元素(处理hash冲突) else { Node e; K k; //快速判断第一个节点table[i]的key是否与插入的key一样,若相同就直接使用插入的值p替换掉旧的值e。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 判断插入的是否是红黑树节点 else if (p instanceof TreeNode) // 放入树中 e = ((TreeNode )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); // 结点数量达到阈值(默认为 8 ),执行 treeifyBin 方法 // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。 // 只有当数组长度大于或者等于 64 的情况下,才会执行转换红黑树操作,以减少搜索时间。否则,就是只是对数组扩容。 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); // 跳出循环 break; } // 判断链表中结点的key值与插入的元素的key值是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 相等,跳出循环 break; // 用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表 p = e; } } // 表示在桶中找到key值、hash值与插入元素相等的结点 if (e != null) { // 记录e的value V oldValue = e.value; // onlyIfAbsent为false或者旧值为null if (!onlyIfAbsent || oldValue == null) //用新值替换旧值 e.value = value; // 访问后回调 afterNodeAccess(e); // 返回旧值 return oldValue; } } // 结构性修改 ++modCount; // 实际大小大于阈值则扩容 if (++size > threshold) resize(); // 插入后回调 afterNodeInsertion(evict); return null; } 设计put()的意义
设计put方法的意义在于提供了一种简单而高效的方式来存储和查找键值对。HashMap的put方法具有O(1)的平均时间复杂度,即使在发生哈希冲突的情况下,通过链表或红黑树的处理,也能保持较快的查找性能。这使得HashMap成为了处理大量数据的理想选择,尤其在需要频繁进行键值对操作的场景下。
总结
本文深入探究了Java中HashMap的put方法的实现原理。通过了解其内部数据结构和算法,我们可以更好地理解和使用HashMap,在实际开发中更加高效地进行键值对的存储和查找操作。同时,我们也探讨了设计put方法的意义,以及提供了相关的Java代码示例。希望本文对读者有所帮助,让大家对HashMap的put方法有更深入的理解。
-