HashMap作为Java中最常用的集合之一,具有快速的查找和插入性能,其put方法在HashMap中扮演着至关重要的角色。本文将从多个方面详细介绍HashMap put方法的内部实现,帮助读者深入理解其工作原理。
一、概述
HashMap是基于哈希表实现的,它通过将元素的键hash为一个整型值来实现快速查找。put方法是HashMap中用于插入元素的核心方法之一,在使用HashMap时,了解put方法的工作原理非常必要。
二、实现原理
在了解HashMap put方法的具体实现之前,需要先掌握一些HashMap的基础知识:
HashMap是由一个数组和链表组成的,数组中的每个元素又是一个链表。
当我们向HashMap中插入一个元素时,会先通过hash函数对元素的键进行哈希处理,将得到的哈希值作为数组下标,将元素存储在对应的数组位置。如果相同哈希值的元素不止一个,那么这些元素就会被插入到同一个链表中。
下面是HashMap put方法的核心源代码:
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; // 判断是否需要初始化哈希表 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 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 )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) 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; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize();//扩容 afterNodeInsertion(evict); return null; }
整个方法的主体流程如下:
- 通过hash函数计算出元素键对应的哈希值;
- 判断哈希表是否初始化,若未初始化则进行初始化;
- 计算数组下标,将元素插入数组对应位置的链表中:
- 如果该位置没有元素,则直接插入;
- 如果该位置已有元素,则从链表头开始遍历链表,查找是否存在相同键的元素:
- 如果查找到相同键的元素,直接替换其值;
- 如果未查找到相同键的元素,则将该元素插入链表尾部。
- 检查链表长度,若链表长度超过阈值,则将链表转化为树;
- 检查是否需要扩容哈希表,若需要则进行扩容;
- 执行插入后后续操作,如回调用户函数、更新size等操作。
三、参数
在使用HashMap put方法时,有几个参数需要注意:
1、key
HashMap中的键必须是不可变对象,例如String或Integer等类的实例。如果使用可变对象作为键,可能会导致无法查找和访问键对应的值,甚至会导致内存泄漏。
2、value
value参数是我们要插入的元素值。与key一样,value也应该是不可变对象。如果value是可变对象,则在插入后修改该对象可能会导致HashMap中元素的值混乱。
3、onlyIfAbsent
该参数用于控制是否只在当前HashMap中不存在指定键的情况下才插入指定键值对,若值为true则只在键不存在时插入,否则直接替换原有值。
4、evict
该参数指定当前HashMap是否可以移除元素,若值为true则可以移除,否则不可移除。若需要保证元素不被移除,则可以将该参数设为false。
四、总结
本文介绍了HashMap put方法的原理、源代码和相关参数,希望通过阅读本文,读者能够深入理解HashMap的内部机制,并在实际开发中灵活使用该数据结构。