内容简介:[TOC]hashmap 作为 java 和 Android 开发中面试的必问问题,很有必要对其有一个详细的了解。这篇文章将会从源码角度,对其存储结构,功能实现,扩容优化等进行分析。
[TOC]
hashmap 作为 java 和 Android 开发中面试的必问问题,很有必要对其有一个详细的了解。
这篇文章将会从源码角度,对其存储结构,功能实现,扩容优化等进行分析。
分析版本 java 1.8.0
基本使用
在 hashmap 源文件前的注释中,可以了解的信息如下:
- 实现了 map 接口,提供了 map 相关的操作,并支持 key, value 都为 null 值。
- 如果元素均匀分布于桶内,可于O(1) 进行存取;
- 由两个因素影响性能:初始容量和扩容因子。
- 非同步方法:多个线程进行操作时,可能会出 ConcurrentModificationException 异常
首先从一个例子开始:
val map = HashMap<Int, Int>() map.put(1, 1) map.get(1) 复制代码
这是基本的存取操作,下面分别看一下每一行具体做了什么。
首先是 hashmap 的构造方法,创建了一个对象。
/** * 以指定的容量和扩容因子创建空的 hashmap */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // 初始化容量大小 this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } // 以 指定的 map 创建 对象 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } 复制代码
源码中有四个构造方法,其对应的注释如上,上面提到几个值,比如容量,扩容因子等,在源码中有几个常量定义如下:
/** * The default initial capacity - MUST be a power of two. * 初始化的默认 容量 大小, 2的4次幂, 16 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. * 最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. * 扩容因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 链表 树化 阈值 */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. * 树 链表化 阈值 */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. * 树化 的 最小容量 */ static final int MIN_TREEIFY_CAPACITY = 64; 复制代码
将在稍后作出解释。
存储结构
从结构上来讲,使用 数组+链表(红黑树)实现,也即遇到 hash 冲突时使用链表法解决, 如下。
可以解释一些基本的概念:
/** * map 的数组 */ transient Node<K,V>[] table; /** * 保存的节点 */ transient Set<Map.Entry<K,V>> entrySet; /** * 已存入 map 的元素的大小 */ transient int size; // hashmap 操作的 的次数记录 transient int modCount; // 扩容阈值 int threshold; // 扩容因子 final float loadFactor; 复制代码
容量表示 table 的大小,最大为 MAXIMUM_CAPACITY。
在容量不够时需要进行扩容,什么时候能确定容量不够,即 size > 容量 * 扩容因子 = 扩容阈值
时进行扩容;
默认为 0.75f。
当链表的个数大于8, 由于存取变慢,将链表转为 红黑树,优化性能;随着链表个数减少,小于 6 时, 又转为链表。
MIN_TREEIFY_CAPACITY = 64, 这个值表示当 链表的个数大于8, 但如果容量小于64,还是进行扩容,而不是转换树。
接下来首先看一下 Node<K, V> 的结构,即上图中的黑点,map 中保存的元素。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } 复制代码
不难理解,最基本的 hash 节点,在大部分数据结构中都有用到。
实现原理
接着看一下 put 操作:
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 复制代码
/** * Implements Map.put and related methods * * @param hash : key 的 hash 值 * @param key : key * @param value :value * @param onlyIfAbsent:为true 时表示,当节点存在时不覆盖 * @param evict : false 表示有 构造函数调用的方法 * @return value : 返回之前的值,空时返回 null。 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 当 table 为空时惊醒扩容,n表示容量 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 定位 table数组中节点的位置,后面分析。 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; // 如果是树节点,此时链表长度大于8, 转为红黑树 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; } 复制代码
主要内容在 putVal() 函数里面。
###桶节点索引定位
这里有几个特别重要的地方,同时也显示出设计的巧妙之处。
if ((p = tab[i = (n - 1) & hash]) == null)) { tab[i] = newNode(hash, key, value, null); } 复制代码
上面代码表示在 table 中根据下标 i = (n - 1) & hash
定位节点的位置,如果该位置为存入节点,则创建节点并存入。
首先来看为什么要这样确定 hash 桶中的索引位置。在 n 大小的数组中,使用 hash % n 来确定位置。这里有个特例, 由于 hash 桶中的数组大小始终为 2 的 n次方,所以 可以使用 上述方法来计算,效率更高;
此时,冲突就由 hash 来决定:当 hash 不容易重复时,就越不容易冲突,看一下 hash 的计算方法:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 复制代码
这里刚开始我也不明白为甚么为进行 高位和低位进行异或运算求 hash。
n 表示 table 的大小,当 hash & (n - 1)
时,假设 hash 任意,n 为 16.
key.hash 1110 1110 1101 1010 0001 0001 0010 0110 n - 1. 0000 0000 0000 0000 0000 0000 0000 1111 (只有低位参与运算) 复制代码
上图例子中显示,如果只是 key.hash 参与运算,那么只会是低位参与, 为了防止冲突,加入高位。所以将高16 位 与 低16位进行异或运算,防止冲突。 设计极为巧妙
扩容
上面提到,桶的大小始终为为 2 的n次方,主要在于取模(上有介绍)和扩容时做优化。
那么构造方法里传入的自定义大小时怎么处理的呢, 回看代码如下:
this.threshold = tableSizeFor(initialCapacity); /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } 复制代码
对于给定的 cap,将转化为大于等于cap 中最小的2的n次方数。这里稍微说明一下,也是设计极为巧妙。
n = cap - 1
: 为了处理 cap 刚好是 2的n次方数, n 为 高位为0, 低位为1 的数:00000111111;
n |= n >>> 1
: 无符号右移 1位。不失一般性(包含上面的结果), 假设一个数位 0000001xxxxx,
任何数从左边第一个 1 开始,右移动 1 位进行或运算;
0000 001x xxxx 0000 0001 xxxx 0000 0011 xxxx(得到的结果左边两高位为1) 0000 0000 11xx 0000 0011 11xx(得到的结果左边4高位为1) 复制代码
其余的计算不用进行了,这个时候可以保证低位全部位1, 加上最后的 n + 1; 即可得到结果。
那么继续往下, resize() 函数的代码如下:
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * 初始化或者扩容为 2 倍大小。由于其始终为2 的 n 次方,所以计算的下标或者相等, 或者偏移 2的 n 次方。 * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // 旧数组 int oldCap = (oldTab == null) ? 0 : oldTab.length; //旧 table 的容量 int oldThr = threshold; //旧 table 的阈值 int newCap, newThr = 0; // 新容量,新大小 if (oldCap > 0) { // 达到最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 新容量,新阈值都扩为两倍大小 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 还未初始化,为0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 这里解释了构造函数为什么将 tablesizefor 赋值 threshold。 else { // zero initial threshold signifies using defaults // 默认值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 新建 新容量大小的 节点数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 非初始化,旧 table 有数据 if (oldTab != null) { // 移动到新 table 里面 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; // 该下标有节点存在 if ((e = oldTab[j]) != null) { // 旧链表该位置为置空 oldTab[j] = null; if (e.next == null) // 只有一个节点,找到下标赋值 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 树的操作 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; //低位头尾节点 Node<K,V> hiHead = null, hiTail = null; //高位头尾节点 Node<K,V> next; do { next = e.next; // 不用计算 hash, 确定新 table 中下标的位置 // 后续介绍 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } 复制代码
在上面的过程中,对 if ((e.hash & oldCap) == 0)
作下解释:
在上面确定桶下标索引的位置时,使用 hash & (n - 1)
计算得到,扩容后,这里的 n 相当于 oldCap。
举个例子:
0000 0000 0000 0000 0000 0000 0000 1111 (n - 1) 0000 0000 0000 0000 0000 0000 0000 0101 (hash1) -> 0101 0000 0000 0000 0000 0000 0000 0001 0101 (hash2) -> 0101 复制代码
如上,计算时下标相同, 在同一索引位置。
0000 0000 0000 0000 0000 0000 0001 0000 (oldCap) 0000 0000 0000 0000 0000 0000 0000 0101 (hash1) -> 0101 0000 0000 0000 0000 0000 0000 0001 0101 (hash2) -> 10101 复制代码
可以看到,当冲突的节点确定索引位置时,有两种可能,在原位置或者 原位置 + oldCap。(因为结果最高位1)
因为根据 (e.hash & oldCap) 的 结果 为1 即可判断索引在高位, 为 0 即可判断索引在低位。
后续就是利用头尾节点移动冲突的值,最后返回新 table。
这就是为什么容量大小始终为 2 的 n 次方的优化点,极为巧妙。
这个时候回过来看 get 操作:
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } 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; } 复制代码
不做过多解释,有了上面的过程,相信很简单就能看懂。
关于树化后的操作
在设计良好的 hash 算法中,加上有 MIN_TREEIFY_CAPACITY 的存在,转成树的情况很少遇到,这里就不对红黑树的操作作过多分析,有需要的可以查看源码或者相关参考资料了解。
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 即使链表长度大于8,还要满足容量大于MIN_TREEIFY_CAPACITY if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } } 复制代码
map 的遍历
public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; } 复制代码
可以获取 key 的 entry 的集合进行遍历。
总结
以上就是对 hashmap 存取过程的一个分析,主要有以下几点
- 初始容量及其扩容的大小
- 索引下标位置的确定
- 扩容的方案
在使用 hashmap 的过程中,扩容是一个特别耗费时间空间的操作,所以在初始化的时候给一个合适的大小。
另外需要处理并发可以使用 ConcurrentHashMap。
了解了 hashmap 的扩容,那么对其他简单数据类型的扩容也再是问题,继续看源码。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Once Upon an Algorithm
Martin Erwig / MIT Press / 2017-9-8 / GBP 22.95
How Hansel and Gretel, Sherlock Holmes, the movie Groundhog Day, Harry Potter, and other familiar stories illustrate the concepts of computing. Picture a computer scientist, staring at a screen and......一起来看看 《Once Upon an Algorithm》 这本书的介绍吧!