存储键值对我们首先想到 HashMap, 它的底层基于哈希表, 采用数组存储数据, 使用链表来解决哈希碰撞, 它是线程不安全的, 并且存储的 key 只能有一个为 null, 在安卓中如果数据量比较小(小于一千), 建议使用 SparseArray 和 ArrayMap, 内存, 查找性能方面会有提升, 如果数据量比较大, 几万, 甚至几十万以上还是使用 HashMap 吧. 本篇只详细分析 HashMap 的源码, SparseArray 和 ArrayMap 不在本篇讨论范围内, 后续会单独分析.
HashMap 的理解, 最最核心就是扩容那二十几行代码, 可以说是 HashMap 的核心所在了, 然而网上绝大部分博客只是一带而过, 大体说了一下结论, 让人十分失望, 本篇将会彻底分析扩容机制, 源码分析基于 android-23.
好了, 直入主题吧.
一, HashMap 中成员变量
private static final int MINIMUM_CAPACITY = 4;// 约定 hashmap 中最小容量, 也可以是 0, 如果不为 0, 那么最小容量限制为 4
private static final int MAXIMUM_CAPACITY = 1 <<30; 约定 hashmap 中最大容量, 为 2 的 30 次方
- static final float DEFAULT_LOAD_FACTOR = .75F;// 扩容因子: 主要用于扩容时机, 后续会细讲
- transient HashMapEntry<K, V>[] table;// 盛放数据的 table, 数据每一项 key 不为 null, 每一项都是一个 HashMapEntry 对象
transient HashMapEntry<K, V> entryForNullKey; 盛放 key 为 null 的数据项
- transient int size;//hashmap 中已经盛放数据的大小
- private transient int threshold;// 用来判断是否需要扩容, 其值为 DEFAULT_LOAD_FACTOR * hashmap 的容量, 当盛放数据达到 hashmap 的四分之三时, 急需要考虑扩容了
主要成员变量已经有所标注, 后续分析的时候会再次提及, 此处不做过多解释.
二, HashMap 中数据项 HashMapEntry
HashMap 中每个数据项都是 HashMapEntry 对象, HashMapEntry 是 HashMap 的内部类, 我们先来看看其结构:
- static class HashMapEntry<K, V> implements Entry<K, V> {
- final K key;
- V value;
- final int hash;
- HashMapEntry<K, V> next;
- HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
- this.key = key;
- this.value = value;
- this.hash = hash;
- this.next = next;
- }
- public final K getKey() {
- return key;
- }
- public final V getValue() {
- return value;
- }
- public final V setValue(V value) {
- V oldValue = this.value;
- this.value = value;
- return oldValue;
- }
- @Override public final boolean equals(Object o) {
- if (!(o instanceof Entry)) {
- return false;
- }
- Entry<?, ?> e = (Entry<?, ?>) o;
- return Objects.equal(e.getKey(), key)
- && Objects.equal(e.getValue(), value);
- }
- @Override public final int hashCode() {
- return (key == null ? 0 : key.hashCode()) ^
- (value == null ? 0 : value.hashCode());
- }
- @Override public final String toString() {
- return key + "=" + value;
- }
- }
主要信息就是每一个数据项都包含了我们存储的 key,value 以及根据 key 算出来的 hash 值, next 用于发生哈希碰撞的时候指向其下一个数据项.
三, HashMap 构造方法
HashMap 构造方法有如下:
- public HashMap()
- public HashMap(int capacity)
- public HashMap(int capacity, float loadFactor)
- public HashMap(Map<? extends K, ? extends V> map)
构造方法有如上 4 种方式, 我们平时最常用的就是第一种方式, 直接初始化然后不停往里面仍数据就可以了, 第二种初始化的时候可以指定容量大小, 第三, 四中估计大部分人没用过, 第三种除了指定容量大小我们还可以指定扩容因子, 不过我们还是不要动扩容因子为好, 指定为 0.75 是时间和空间的权衡, 平时我们使用就用默认的 0.75 就可以了.
我们看一下 HashMap()这种构造方式:
- public HashMap() {
- table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
- threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
- }
太简单了, 就是初始化 table 为空的数组 EMPTY_TABLE, 这个 EMPTY_TABLE 的初始化容量可不为 0, 源码如下:
- private static final Entry[] EMPTY_TABLE
- = new HashMapEntry[MINIMUM_CAPACITY>>> 1];
看到了吧, 初始化容量为 MINIMUM_CAPACITY 的一半, 也就是 2.
此外 threshold 初始化的时候置为 - 1.
接下来我们在看下 HashMap(intcapacity) 这种构造方式:
- public HashMap(int capacity) {
- if (capacity <0) {
- throw new IllegalArgumentException("Capacity:" + capacity);
- }
- if (capacity == 0) {
- @SuppressWarnings("unchecked")
- HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
- table = tab;
- threshold = -1; // Forces first put() to replace EMPTY_TABLE
- return;
- }
- if (capacity <MINIMUM_CAPACITY) {
- capacity = MINIMUM_CAPACITY;
- } else if (capacity> MAXIMUM_CAPACITY) {
- capacity = MAXIMUM_CAPACITY;
- } else {
- capacity = Collections.roundUpToPowerOfTwo(capacity);
- }
- makeTable(capacity);
- }
- private HashMapEntry<K, V>[] makeTable(int newCapacity) {
- @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
- = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
- table = newTable;
- threshold = (newCapacity>> 1) + (newCapacity>> 2); // 3/4 capacity
- return newTable;
- }
6-12 行逻辑大体就是我们调用 hashmap()空参数的构造函数初始化一样.
14-17 行, 就是对我们设置的容量 capacity 进行检查了, 如果小于 MINIMUM_CAPACITY 那么就重置为 MINIMUM_CAPACITY, 如果大于 MAXIMUM_CAPACITY 则重置为 MAXIMUM_CAPACITY.
19 行, Collections.roundUpToPowerOfTwo 这个方法就是找出一个 2^n 的数, 使其不小于给出的数字, 并且最近接给出的数字.
比如:
Collections.roundUpToPowerOfTwo(3)返回 4,22.
Collections.roundUpToPowerOfTwo(4)返回 4,22.
Collections.roundUpToPowerOfTwo(100)返回 128,27.
明白了吧? 也就是说返回的数肯定是 2 的几次方, 也就是说 hashmap 的容量肯定是 2 的几次方形式, 这里很重要, 一定要记住, 后续分析的时候还会用到.
接下来就是调用 makeTable 了.
26,27 就是根据给定的容量创建 newTable 数组.
28 行, 成员变量 table 指向新创建的 newTable 数组.
29 行, 计算 threshold 的值, 也就是我们指定的容量的四分之三了.
好了, 以上就是构造方法逻辑, 其余两种方法可自行查看一下, 比较核心的就是 19 行代码, 对 capacity 数据的转换, 约束 hashmap 容量大小肯定为 2 的 n 次方.
四, HashMap 中 put 方法分析
接下来就是 HashMap 核心所在了, 我们一点点分析, 先看下 put 方法源码:
- @Override
- public V put(K key, V value) {
- if (key == null) {
- return putValueForNullKey(value);
- }
- int hash = Collections.secondaryHash(key);
- HashMapEntry<K, V>[] tab = table;
- int index = hash & (tab.length - 1);
- for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
- if (e.hash == hash && key.equals(e.key)) {
- preModify(e);
- V oldValue = e.value;
- e.value = value;
- return oldValue;
- }
- }
- // No entry for (non-null) key is present; create one
- modCount++;
- if (size++> threshold) {
- tab = doubleCapacity();
- index = hash & (tab.length - 1);
- }
- addNewEntry(key, value, hash, index);
- return null;
- }
3-5 行, 如果我们放入的数据 key 为 null, 那么执行 4 行代码逻辑并且直接返回, putValueForNullKey 源码如下:
- private V putValueForNullKey(V value) {
- HashMapEntry<K, V> entry = entryForNullKey;
- if (entry == null) {
- addNewEntryForNullKey(value);
- size++;
- modCount++;
- return null;
- } else {
- preModify(entry);
- V oldValue = entry.value;
- entry.value = value;
- return oldValue;
- }
- }
大体逻辑很简单, 就是对成员变量 entryForNullKey 操作, 其就是 HashMapEntry 对象实例, 3-8 行如果 entry 为 null, 则代表之前没有放入过 key 为 null 的数据, 则只需要创建即可. 8-12 行表示之前放入锅 key 为 null 的数据, 那么只需要将 value 替换为新的 value 即可, 这里说明 HashMap 只会有一个数据的 key 为 null, 重复放入只会将 value 替换为最新 value. 好了, 这里就只是简单分析一下.
回到 put 方法, 如果我们放入的 key 不为 null, 则继续向下执行:
6 行, 根据 key 计算二次哈希值, 源码如下:
- public static int secondaryHash(Object key) {
- return secondaryHash(key.hashCode());
- }
- private static int secondaryHash(int h) {
- // Spread bits to regularize both segment and index locations,
- // using variant of single-word Wang/Jenkins hash.
- h += (h <<15) ^ 0xffffcd7d;
- h ^= (h>>> 10);
- h += (h <<3);
- h ^= (h>>> 6);
- h += (h <<2) + (h << 14);
- return h ^ (h>>> 16);
- }
就是将 key 的 hashCode 方法返回的值传入 secondaryHash(inth)再次计算一次返回一个值, 这里最重要的一点就是我们传入的 key 必须有 hashCode()方法并且每次返回的值一样, 如果 HashMap Key 的哈希值在存储键值对后发生改变, Map 可能再也查找不到这个 Entry 了, 所以 HashMap 中 key 我们需要使用不可变对象, 比如经常使用的 String,Integer 对象, 其 HashCode()方法分别如下:
- @Override
- public int hashCode() {//String 中 HashCode()方法
- int hash = hashCode;
- if (hash == 0) {
- if (count == 0) {
- return 0;
- }
- for (int i = 0; i <count; ++i) {
- hash = 31 * hash + charAt(i);
- }
- hashCode = hash;
- }
- return hash;
- }
- @Override
- public int hashCode() {//Integer 中 HashCode()方法
- return value;
- }
回到 put 方法, 则继续向下执行:
7 行定义局部变量 tab 指向全局变量 table 数组.
8 行, 计算放入的数据在 tab 中的位置, 计算方式为 key 的 hash 值按位与 tab 的长度减 1, 这样确保了计算出的 index 不会超出数组角标, 比如:
key 的 hash 值为 11111111111111111111111111111111,tab 容量为 8, 则 tab.length-1 为 7, 其数组角标范围为 0~7.
hash & (tab.length - 1)按位与计算如下:
也就是经过上述计算最大值为 7, 不会超过数组角标.
为什么要进行二次哈希值得计算呢?
比如我们放入三个数据, key 的 HashCode 值分别为: 31,63,95.tab 容量为 8
如果不进行二次哈希值计算索引 index, 也就是 key.hashcode() & (tab.length - 1), 计算如下:
- 31=00011111 & 00000111 = 0111 = 7
- 63=00111111 & 00000111 = 0111 = 7
- 95=01011111 & 00000111 = 0111 = 7
进行二次哈希值后再计算索引 index, 也就是源码中 secondaryHash(key.hashCode())& (tab.length - 1), 计算如下:
- 31=00011111 =>secondaryHash=> 00011110 & 00000111= 0110 = 6
- 63=00111111 ==secondaryHash=> 00111100 & 00000111= 0100 = 4
- 95=01011111 ==secondaryHash=> 01011010 & 00000111= 0010 = 2
如上不经过二次哈希值计算最终计算出的 index 值均为 7, 也就是我们放入数组中都处于同一位置. 而经过二次哈希值计算之后再计算 index 值分别为 6,4,2 也就是在数组中处于了三个不同的位置, 这样就达到了更加散列的效果. 但是即使经过二次哈希值计算也不能保证计算出的 index 值都不相同, 这里只是尽可能的散列化, 不能保证避免哈希碰撞.
回到 put 方法, 继续向下分析:
我们知道 HashMap 存储数据结构如下:
简单说就是我们放入一个数据的时候会先根据数据项的 key 计算出其在 table 数组中的索引, 如果索引位置已经有元素了, 那么则与已经放入的数据形成链表的关系, 相信稍有经验的都明白, 这里只是稍微提一下.
9-16 行的 for 循环逻辑就是挨个遍历所在数组行链表中每一个数据项, 然后将每个数据项的 hash 值和 key 与将要放入的 key 及其 hash 值比较, 如果二者均相等则表明 HashMap 中已经存在此数据.
12-14 行就是将对应数据项的 value 值替换为新的 value 值, 并将之前 value 返回.
如果整个 for 循环都没有找到则表明 HashMap 中没有将要存储的数据项, 继续向下执行.
19 行, 判断是否需要扩容, threshold 上面说过值为 table 容量的四分之三, size 记录我们 HashMap 中存入数据的大小, 我们放入数据时如果超过容量的四分之三那么就需要扩容了.
20 行, 如果需要扩容那么调用 doubleCapacity()方法进行扩容(后续会仔细分析扩容机制), 扩容完此方法会返回扩容后的数组.
21 行, 由于数组已经扩容, 容量发生了变化, 所以这里需要重新计算一下将要放入数据的 index 索引.
23 行调用 addNewEntry 方法将数据放入数组中. addNewEntry 源码如下:
- void addNewEntry(K key, V value, int hash, int index) {
- table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
- }
这里就是根据我们传入的 key,value,hash 值新建 HashMapEntry 数据节点, 此数据节点的 next 指向原 table[index], 最后将新数据节点赋值给 table[index], 这里说的有点蒙圈, 用图来解释一下, 又要展示我强大的画图能力了:
这里通过阅读源码可以发现新添加的数据项是放在链表头部的, 而不是直接放在尾部.
好了, 以上就是 put 方法主要逻辑了, 不再做其余分析, 下面我们着重看一下 HashMap 的扩容机制.
五, HashMap 中扩容机制分析
好了, 如果你看到这里那么清理一下大脑吧, 下面的有点烧脑了.
废话少说, 直接看扩容方法源码;
- private HashMapEntry<K, V>[] doubleCapacity() {
- HashMapEntry<K, V>[] oldTable = table;
- int oldCapacity = oldTable.length;
- if (oldCapacity == MAXIMUM_CAPACITY) {
- return oldTable;
- }
- int newCapacity = oldCapacity * 2;
- HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
- if (size == 0) {
- return newTable;
- }
- for (int j = 0; j <oldCapacity; j++) {
- /*
- * Rehash the bucket using the minimum number of field writes.
- * This is the most subtle and delicate code in the class.
- */
- HashMapEntry<K, V> e = oldTable[j];
- if (e == null) {
- continue;
- }
- int highBit = e.hash & oldCapacity;
- HashMapEntry<K, V> broken = null;
- newTable[j | highBit] = e;
- for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
- int nextHighBit = n.hash & oldCapacity;
- if (nextHighBit != highBit) {
- if (broken == null)
- newTable[j | nextHighBit] = n;
- else
- broken.next = n;
- broken = e;
- highBit = nextHighBit;
- }
- }
- if (broken != null)
- broken.next = null;
- }
- return newTable;
- }
2-6 行 oldTable,oldCapacity 记录原来数组, 数组长度以及检查原数组长度是否已经达到 MAXIMUM_CAPACITY, 如果已经达到最大长度, 那么不好意思了, 直接返回原数组了, 老子无法给你扩容了, 都那么长了, 还扩什么容, 自己继续在原数组玩吧, 管你哈希碰撞导致链表多长我都不管了.
7 行, 定义 newCapacity 也就是新数组长度为原数组长度的 2 倍.
8 行, 就是执行 makeTable()逻辑, 创建新的数组 newTable 了, 至于 makeTable 方法上面说过, 就不再分析了.
9-11 行, 检查 size 是否为 0, 如果为 0 那么表明 HashMap 中没有存储过数据, 不用执行下面的数据拷贝逻辑了, 直接返回 newTable 就可以了.
12-37 行, 这可就是 HashMap 整个类的精华所在了, 这几行代码看不懂这个类你就没有真正理解, 看懂了其余扫一下就明白了.
假设原 HashMap 如图:
12 行很简单就是遍历原数组中每个位置的数据, 也可以说每个链表的头数据.
13-16 行, 风骚的注释: 直白翻译就是下面这几行代码是这个类中最风骚的几行代码.
17-20 行代码, 就是检查取出的数组中每个数据项是否为 null, 为 null 则表明此行没有数据, 继续循环就可以了.
在继续向下讲请大家思考一个问题: HashMap 中同一个链表中每一个数据项的哈希值有什么相同点? 比如原数组大小是 8, 那么同一链表中每一个数据项的哈希值有什么相同点?
思考.....
这里直接说了: 能在同一链表说明计算出来的 index 值相同, 在看计算公式为 int index = hash & (tab.length - 1), 这里在扩容之前 tab.length-1 的值是相同的, 比如数组长度为 8, 那么 tab.length - 1 的二进制表示为 00000111, 不同 hash 值计算出的 index 又相同, 那么这里同一链表中每一个数据项的 hash 值得最后三位一定相同, 只有这样计算出的 index 值才相同, 如下:
如上图 两个 hash 值不同的数据项, 经过运算后得出 index 均为 2, 原因就是虽然整体的 hash 值不同, 但是最后三位均为 010, 所以计算出 index 值是相同的(此处假设数组长度为 8).
进而得出结论: 如果 HashMap 中数组长度为 2 的 n 次方, 那么同一链表中不同数据项的 hash 值的最后 n 位一定相同.
好了, 到这里第一个难点通过, 我们继续分析 doubleCapacity()方法.
21 行, int highBit = e.hash &oldCapacity 计算出 highBit 位, 翻译过来就是高位, 这他妈又是什么玩意? 仔细看计算方式与的 oldCapacity, 而不是 oldCapacity-1, 所以这里取得是数据项 hash 值得第 n+1 位 (hashmap 数组长度为 2 的 n 次方) 是 0 还是 1, 这里一定要知道 HashMap 数组长度一定为 2 的 n 次方, 二进制形式就是第 n+1 位为 1 其余为均为 0. 这里先记住这个 highBit 是哪一位, 后面会用到.
22 行, 定义一个 broken, 知道有这么个玩意, 后面也会用到.
23 行, newTable[j | highBit] = e, 将我们从原数组取出的数据项放入新数组中, 也就是数据的拷贝了, 注意这里 e 是每一个链表的头部, 也就是处于数组中的数据. 链表其余数据是通过 24 行 for 循环挨个遍历再放入新数组中的. 但是这里有个疑问原数组放入数据是按照 hash & (tab.length - 1)计算其在数组中位置的, 这里怎么成了 j | highBit 这样计算了呢? 这里真是卡住我了, 一开始我是怎么想怎么想不通, 但是我觉得二者之间一定有什么关系, 不可能用两个完全不相关的算法来计算同一数据项在数组中的位置, 绝不可能, 一定有内在联系, 我查啊查, 算啊算, 在经过如下计算我终于想明白了: hash & (tab.length - 1)与 j | highBit 这二者逻辑是完全相同的, TMD, 逻辑竟然是相同的.
接下来咱们推导分析一下:
j | highBit
= j | (e.hash &oldCapacity) 第一步
= (e.hash &(oldCapacity-1)) | (e.hash &oldCapacity) 第二步
= e.hash & ((oldCapacity-1) | oldCapacity) 第三步
= e.hash & (newCapacity- 1) 第四步
从开始到第一步很简单了, highBit 的计算方式就是 e.hash &oldCapacity 这里只是替换回来.
第一步到第二步, j 怎么就成了 e.hash &(oldCapacity-1)呢? 还记得 index 的计算方式吗? 就是 e.hash &(oldCapacity-1), 那就是说 j 就是 index 了, 在看看 j 是什么? j 就是从 0 开始到 oldCapacity 的值, 这里我们想一下啊, e 就是通过 oldTable[j]获取的, 我们想想 put 方法怎么放入的呢, 不就是 oldTable[e.hash &(oldCapacity-1)] = e 吗, 想到了什么? 想到了什么? 对, 通过 j 获取的元素 e, 这个 j 就是 e.hash &(oldCapacity-1), 所以这里可以替换的.
第二步到第三步就是数学方面的, 记住就可以了.
第三步到第四步怎么来的呢? 也就是(oldCapacity-1) | oldCapacity 与 newCapacity- 1 相等, 还记得上面说的 HashMap 数组容量一定是 2 的 n 次方吗? 并且 newCapacity = oldCapacity * 2 .
oldCapacity 为 2 的 n 次方, 也就是 n+1 位为 1, 其余都为 0,oldCapacity-1 也就是 0 到 n 位为 1 其余都为 0, 二者或运算后 0 到 n+1 为 1 其余位 0.
newCapacity= oldCapacity * 2 也就是 n+2 位为 1 其余位 0,newCapacity- 1 也就是 0 到 n+1 位为 1 其余为 0.
所以(oldCapacity-1) | oldCapacity 与 newCapacity- 1 相等.
到此, 我们就证明了 j | highBit = e.hash & (newCapacity- 1) 其计算数据项在新数组中位置与原数组的计算逻辑是一样的, 只不过十分巧妙的运用了位运算, 好了, 想明白这里恭喜你通过了第二个难点, 我们继续向下分析.
24-34 行就是遍历链表中数据项了, 把他们挨个放入新数组中, 这里思考一个问题? 在原数组中同一链表的数据项在新数组中还处于同一链表吗? 如果不是那么是什么决定它们不在同一链表了?
在上面分析的时候我们得出一个结论: 如果 HashMap 中数组长度为 2 的 n 次方, 那么同一链表中不同数据项的 hash 值的最后 n 位一定相同.
扩容后数组容量为原来的 2 倍了, 根据 index 的计算方式 e.hash & (newCapacity- 1)每个数据项的 hash 值是不变的, 但是长度变了, 所以同一链表中不同数据项在新数组中不一定还处于同一链表, 那么具体是什么决定在新数组中二者在不在同一链表呢?
原数组长度为 2 的 n 次方, 新数组长度扩容后为原数组 2 倍也就是 2 的 n+1 次方, 原数组中同一链表中不同数据项的 hash 值的最后 n 位一定相同, 所以新数组同一链表中不同数据项的 hash 值的最后 n=1 位一定相同. 如果上面讲的你真的理解了, 这里就不难理解, 不过多解释.
在原数组中同一链表的数据项已经确保了 hash 值最后 n 位相同, 按照计算方式新数组中处于同一链表的数据项需要确保 hash 值最后 n+1 位相同即可, 既然原链表中的数据项最后 n 位已经相同了, 在新数组中是否处于同一链表那么只需要比较同链表数据项 hash 值的第 n+1 位即可, 如果相同则表明在新数组中依然处于同一链表, 如果不同那么就处于不同链表了, 上面的高位 highBit 就是取的是每一数据项的第 n+1 位, 后面比较也只是比较每个数据项的 highBit 是否相同.
好了, 这里我认为解释的已经很清楚了, 这里你要是明白了, 恭喜你, HashMap 中最难理解的部分你已经完全掌握了.
至于 24-34 行具体逻辑我就不一一分析了, 静下心来, 自己试着分析, 难度不大.
六, 总结
好了, 到这里本篇就要结束了, 咦? 这不就分析了一个 put 方法外加扩容机制吗? 这就完了? 是的, 我想说的就这些, 这部分是最难理解的, 至于其余自己看看都能理解的差不多了.
最关键是一定要理解扩容机制, 那几行最难理解的代码设计的真是巧妙, 大神的思想真是无法企及啊!!!
本篇到此结束, 希望对你有用.
来源: https://www.cnblogs.com/leipDao/p/9482764.html