HashMap源码分析

内容简介：HashMap源码分析

本文我们来分析一下HashMap的源码实现，通过本文可以了解到：

1. HashMap中的容量因子是什么？HashMap是通过什么途径解决hash冲突的？
2. get方法是如何实现的？
3. put方法是如何实现的？
4. hash是如何设计的？这样设计的目的是什么？
5. resize方法是如何实现的？

p.s: 建议阅读本文的朋友在阅读的同时在编辑器中打开jdk中HashMap的源码。

基础

在正式进入HashMap的源码分析之前，我们有必要先了解一下几个关键的概念。首先我们先来看一下官方文档对于HashMap的定义：

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

可以看到HashMap是基于Map接口来实现的，并且允许空值和空键，而且HashMap不保正有序性，特别强调的是元素的顺序会随着HashMap的扩展（增删）而变化，这一点在下面我们也会有所强调。

Load factor: The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

LoadFactor(容量因子)的大小默认是 0.75f 。设置LoadFactor的目的就是当 capacity * laodFactor 大于 thredhold (阀值)的时候，HashMap就会就行resize来将HashMap的大小扩大两倍，这一点如果现在不是很理解也没有关系，在下面会提及到。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

另外一个重要的概念就是在jdk1.8中，HashMap做了进一步的优化，当产生hash冲突的时候，以前都是完全通过链表来解决的，现在新增加了一个 static final int TREEIFY_THRESHOLD = 8; ，当链表的长度达到8位的时候，为了提高效率，链表会扩展成红黑树。这样在下面的 get 操作的时候算法效率就可以由 O(n) 提高到 O(logn) 。

get实现原理

public V get(Object key){
 Node<K,V> e;
 return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode的实现比较简单，实现步骤如下：

1. 首先通过 first = tab[(n - 1) & hash] 找到第一个匹配hash值的节点，如果没有匹配成功就返回 null 。
2. 然后判断找到的第一个节点是否等于我们需要查找的 key ，如果是的就直接返回，否则就代表产生了碰撞，转移到红黑树或者链表中去查找。
3. 如果这个节点是红黑树的子节点，转到红黑树中查找，即 ((TreeNode<K,V>)first).getTreeNode(hash, key) 。
4. 否则就在链表中查找，如果没有找到就返回 null 。

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key){
 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 && // always check first node
 ((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);
 }
 }
 return null;
}

put实现原理

public V put(K key, V value){
 return putVal(hash(key), key, value, false, true);
}

put 方法的实现相比较 get 就稍微复杂一些了，主要分为以下几个步骤：

1. 第一个if语句：如果tab为空就创建。
2. 第二个if语句：通过计算hash如果没有发生碰撞就直接创建一个节点。
3. 重点就是分析else语句了。

分析else语句前，建议大家先从整体看一下源码中的的两个条件分支，写的非常清晰，甚至和上面的 get 操作的思路有些相似，分为几个步骤：

1. 首先判断节点是否存在，如果存在直接给 e 赋值。
2. 判断节点是否是红黑树的节点，如果是的从红黑树中查找，并赋值给 e 。
3. 否则从链表中查找，并赋值给 e 注意循环中加了一个检查条件 if (binCount >= TREEIFY_THRESHOLD - 1) ， TREEIFY_THRESHOLD 默认是8，就是如果达到了这个阀值，就将链表扩展为红黑树。
4. 最后通过检查 e 来看是否已经存在相应的 key ，如果存在就更新 value 的值，并且返回。
5. 否则跳出 else 循环之后，通过修改 ++modCount; 记录修改次数，并且判断现在hashmap是否需要resize。

p.s: afterNodeAccess(e); 和 afterNodeInsertion(evict); 是留给HashMap的子类 LinkedHashMap 去实现的。

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 boolean evict) {
 Node<K,V>[] tab; Node<K,V> 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<K,V> 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<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 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;
}

hash的实现

static final int hash(Object key){
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash的实现虽然比较简单，就是高16位不变，低16位和高16位做了一个异或。但是还比较有技巧的，我们先来看一下原作者对这段代码的解释：

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

为什么要做异或呢？而不是直接 (n - 1) & hash ，因为这样很容易发生碰撞，比如假设n等于16，那么散列的其实只有低四位。

resize的实现

resize的实现其实也很巧妙，我们来具体看一看。当超过阀值threshold的时候，就会resize，因为hashmap的长度永远都是2的幂，而resize就是将长度扩展为原来的两倍，所以节点的位置可能会继续保持不变，也有可能会在原来的位置上移动两次幂。

比如我们需要从16位扩展到32位，会发生如下变化：

对于hash1来说因为第5位是0，所以会保持原位置不变，但是对于hash2来说因为第五个位置是1，所以相当于在原位置的基础上加上oldCapacity(16)。

resize的实现思路上面我们已经分析出来了，源代码我就不贴了，代码大家具体到jdk下面去看吧。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

关注我们，获取更多IT资讯^_^

查看所有标签

• 以太坊源码分析(36)ethdb源码分析
• [源码分析] kubelet源码分析（一）之 NewKubeletCommand
• libmodbus源码分析（3）从机（服务端）功能源码分析
• [源码分析] nfs-client-provisioner源码分析
• [源码分析] kubelet源码分析（三）之 Pod的创建
• Spring事务源码分析专题（一）JdbcTemplate使用及源码分析

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。