本文是基于 Java 8
的 HashMap
进行分析,主要是分析 HashMap
中的 put()
和 get()
方法。
下面将会分析这部分的源码,如果觉得源码分析内容太啰嗦,可以跳过源码部分,直接看源码下面的总结。
HashMap
的 put()
方法是我们最常用的方法,但是 put()
方法是怎么工作的呢?
/** * HashMap的put()方法支持key/value为null */ public V put(K key, V value) { //实际上是先调用HashMap的hash()方法获取到key的hash值 //然后调用HashMap的putVal()方法 return putVal(hash(key), key, value, false, true); }
put()
方法实际上是
hash()
方法获取到 key
的 hash
值 putVal()
方法存储 key-value
核心方法是 putVal()
方法,下面我会先分析一下 hash()
方法,因为这个方法涉及到 hash
值这个关键属性的计算。
static final int hash(Object key) { int h; // key为null时,hash值为0 // key不为null时,调用key对象的hashCode()方法并通过位运算异或和无符号右移将高位分散到低位 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
hash()
方法指定了 null
的 hash
值为 0
。这样就可以支持 key
为 null
。 (h = key.hashCode()) ^ (h >>> 16)
这段代码通过位运算异或和无符号右移将高位分散到低位,这样做可以减少哈希碰撞的概率(这块不是很清楚原理,是从方法注释上了解到的) /** * Map.put()方法的实际实现 * * @param hash key的hash值 * @param key 键值对中的key * @param value 键值对中的value * @param onlyIfAbsent 如果为true,则键值对中的值已经存在则不修改这个值 * @param evict 如果为false,则是处于创建模式 * @return 上一次的value,如果上一次的value不存在,则为null */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab用于暂存散列表table。p为散列表中对应索引的链表的头节点的指针。n存储tab的长度。i则为命中的散列表的索引 Node<K,V>[] tab; Node<K,V> p; int n, i; //给tab和n赋值 //当tab为null或者tab的长度n为0时,触发resize()来初始化tab if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //使用(n - 1) & hash(等价于hash%n)计算命中的散列表索引,同时判断散列表对应索引的链表是否存在 if ((p = tab[i = (n - 1) & hash]) == null) //散列表对应索引的链表不存在则创建一个新的链表 tab[i] = newNode(hash, key, value, null); else {//散列表对应索引的链表已存在 Node<K,V> e; K k; // 判断头节点的hash值和key是否与入参的hash值和key一致。需要注意,null的hash值为0 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 对应的键值对已经存在,记录下来 e = p; else if (p instanceof TreeNode)//判断对应的链表是否转化为红黑树 //若是,则直接调用红黑树的putTreeVal()方法 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开始,所以为阈值-1 // 将链表转化为红黑树 treeifyBin(tab, hash); // 中断循环 break; } // 判断当前遍历的节点的hash值和key是否与入参的hash值和key一致,即key是否已经存在 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // key已经存在,中断循环 break; // 记录当前遍历的节点 p = e; } } if (e != null) { // Map中存在重复的key V oldValue = e.value;//记录下旧值 if (!onlyIfAbsent || oldValue == null)//判断值存在是否可以进行修改以及旧值是否为null e.value = value;//修改该节点的值 afterNodeAccess(e);// 链表节点的回调方法,此处为空方法 return oldValue;//返回旧值 } } // HashMap发生结构变化,变化次数累加 ++modCount; // 键值对个数自增,同时判断是否达到扩容的阈值 if (++size > threshold) resize(); // 链表节点的回调方法,此处为空方法 afterNodeInsertion(evict); // 此处返回null是因为链表新增了节点,所以上一次的值必然为null return null; }
putVal()
方法的关键点:
table
没有初始化则调用 reszie()
方法初始化。 (n - 1) & hash
(等价于 hash%n
)。其中 n
为散列表长度, hash
为插入的键值对的 key
的哈希值。 null
,若为 null
,则创建链表,否则进入下一步。 key
和 hash
一致,若一致则替换该节点的值为 value
,否则进入下一步 putTreeVal()
方法遍历红黑树,否则遍历链表。 key
和 hash
相同的节点就替换对应节点的值 value
,若不存在则插入新的树节点。 key
和 hash
相同的节点就替换对应节点的值为 value
。若找不到 key
和 hash
相同的节点,则链表尾部插入节点,同时进入下一步。 TREEIFY_THRESHOLD(8)
时,则将链表转化为红黑树。 除了 HashMap
的 put()
方法外, get()
方法也是一个我们常用的方法,下面开始分析其关键的源码。
/** * 返回key对应的value,如果不存在则返回null */ public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
get()
方法实际上是
hash()
方法获取到 key
的 hash
值 getNode()
方法通过 key
和 hash
获取对应的 value
,不存在则返回 null
。 核心方法是 getNode()
方法,下面我会先分析一下 getNode()
方法。
/** * Map.get()方法的实际实现 * @param hash key的哈希值 * @param key 查询用的key * @return 节点或者是节点不存在是返回null */ final Node<K,V> getNode(int hash, Object key) { //tab用于暂存散列表table。first为散列表中对应索引的链表的头节点的指针。n存储tab的长度。i则为命中的散列表的索引 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //初始化方法内的变量,同时尝试命中散列表 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))// 总是先检查链表的头节点 return first;//头节点符合直接返回头节点 if ((e = first.next) != null) {//是否只有一个节点 if (first instanceof TreeNode)//判断头节点是否为红黑树节点 return ((TreeNode<K,V>)first).getTreeNode(hash, key);//改为遍历红黑树 do {//遍历链表是否有符合的节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //不存在对应的key,返回null return null; }
getNode()
方法的关键点:
table
不为 null
且 长度
大于 0
且其索引为 (n - 1) & hash
(等价于 hash%n
)的节点不为 null
。其中 n
为散列表长度, hash
为插入的键值对的 key
的哈希值。则进入下一步,否则直接返回 null
key
和 hash
是否与入参一致,若相同则返回首节点,否则进入下一步。 1
个,若是则返回 null
,否则进入下一步 key
和 hash
与入参相同的节点,若找到则返回该节点,否则返回 null
put()
和 get()
方法是 HashMap
的常用方法,通过学习其源码了解到 HashMap
是如何使用 拉链法 解决哈希冲突。而下面将会通过两幅图展示 put()
和 get()
的执行过程:
put()
方法图解 get()
方法图解