一、数据结构介绍
HashMap是Java中常用的一种集合,是基于一定的hash算法实现的Key-value数据结构。HashMap类继承于AbstractMap类,实现了Map接口。HashMap的底层实现是数组加链表或红黑树,通过key的hash值来找到其在数组中的位置,然后将其存储在该位置的链表或红黑树中。
public class HashMapextends AbstractMap implements Map , Cloneable, Serializable { ... }
二、put方法
put方法是HashMap中最关键的方法之一,它负责将一个键值对存储到Map中。put方法有两个参数,第一个是key,第二个是value,该方法的返回值是被替换的value,如果之前没有关联的value则返回null。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
可以看到,put方法的核心是putVal方法,该方法对外部不可见,它将key-value对插入到HashMap中,并且可以进行扩容和重新哈希处理。
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 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; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
三、put实现原理
put方法主要通过以下几个步骤实现:
- 如果table为null,或者table数组长度为0,执行resize方法进行初始化,否则直接用当前table数组存储值。
- 通过(key.hash) & (n-1)计算key的哈希值,并找到它在table中需要存储的位置 i。
- 检查table[i]的这个位置是否已经有了值(e),如果没有,就把新的键值对放到table[i]的位置上。
- 如果已经存在节点e,即table[i]位置已被占用,则需要进一步判断e和新插入元素的key是否相同,如果相同,则覆盖原本的值,否则,需要判断e所在节点的类型,如果是红黑树节点,则插入红黑树,否则在链表末尾追加节点。
- 如果链表长度超过TREEIFY_THRESHOLD(默认值为8)时,则将链表转化成红黑树。TREEIFY_THRESHOLD是为了避免链表过长导致查询时间复杂度增加。
- 在插入节点后,判断是否超过容量阈值(threshold),如果超过,进行扩容操作,将table数组长度翻倍。
四、实战应用
下面是一个简单的HashMap使用示例,通过put方法向map中存储数据。
HashMapmap = new HashMap<>(); map.put(1, "one"); map.put(2, "two"); map.put(3, "three"); System.out.println(map.get(1)); //"one" System.out.println(map.get(2)); //"two" System.out.println(map.get(3)); //"three"
五、总结
本篇文章介绍了Java中HashMap的put方法实现原理,分别通过数据结构介绍、put方法、put实现原理和实战应用等方面进行了详细阐述。
为了保证HashMap的效率,需要在设计key的时候尽量避免哈希冲突,这样可以减少链表的长度,提高HashMap的查询效率。同时需要注意TREEIFY_THRESHOLD的值,这个值设置过小会导致链表膨胀成红黑树的过快,大大降低查询性能。