alighters

程序、写作、人生

HashMap 实现细节点整理

| Comments

提及 HashMap,大家都耳熟能详了,本文不会再讲它的实现原理,只对其中的一些小的实现细节进行罗列。

hashmap

首先先要明白的两点:

  • 图中的 table 是一个大小为 2n的一维数组,其中存放的是一个个的 HashMapEntry,而 HashMapEntry 是包含了 hash、key 与 value 值及一个指向 HashMapEntry 的 next 指针。

  • HashMapEntry 在 object 数组中的获取及存放是根据 HashMapEntry 结构的中的 hash 与当前的 table 数组大小一减去已进行与操作的结果来作为相应的索引值( index = (table.length -1 ) & hash)。若在存放的过程中,index 值相同,则会链接当前 entry 的 next 指针上。

只允许放置一个 key 为 null 的元素

知道 HashMap 中允许存放 key 为 null 的元素,纠其原理是因为其中有一个 entryForNullKey 的属性,专门来存放 null 相应的 value 值,再进行 putremove方法的时候,都会对 key 进行判断,若为 null,则会只进行 entryForNullKey相应的更新操作。

1
2
3
4
/**
 * The entry representing the null key, or null if there's no such mapping.
 */
transient HashMapEntry<K, V> entryForNullKey;

容量获取算法 roundUpToPowerOfTwo

我们在初始化 HashMap 的时候,可以通过 new HashMap(int capacity)来构造新的 HashMap,而这个参数的值是可以任意填写的,没做任何规范及限制的。(PS:最好根据要存放元素的数量来填写) 但是在 HashMap 的实现当中,而是以大于等于 capacity 并且是 2 的幂数的整数来作为一个新的容量值。修正的算法是通过调用 Collections 类中的 roundUpToPowerOfTwo 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Returns the smallest power of two >= its argument, with several caveats:
* If the argument is negative but not Integer.MIN_VALUE, the method returns
* zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method
* returns Integer.MIN_VALUE. If the argument is zero, the method returns
* zero.
* @hide
*/
public static int roundUpToPowerOfTwo(int i) {
  i--; // If input is a power of two, shift its high-order bit right.

  // "Smear" the high-order bit all the way to the right.
  i |= i >>>  1;
  i |= i >>>  2;
  i |= i >>>  4;
  i |= i >>>  8;
  i |= i >>> 16;

  return i + 1;
}

可以看到这个算法进行了 5 次移位操作,乍一看,一脸懵逼,这是在干嘛?

细细一想啊,我现在要获取一个是 2 的幂数的整数,那其二进制的表现形式就是其最高位为1 ,低位全部为 0;或者其低位全部为 1,只需再对其加 1,即可变成 2 的倍数。

举个栗子:

1
2
3
4
5
6
7
8
9
10
11
1000 0000
0100 0000  // 无符号右移一位
1100 0000  // 上面两个执行或操作的结果

1100 0000
0011 0000 // 无符号右移二位
1111 0000 // 上面两个执行或操作的结果

1111 0000
0000 1111 // 无符号右移三位
1111 1111 // 上面两个执行或操作的结果

其实我们只需将我们的关注点放置其元素为1的最高位上,执行右移操作,紧接着是或操作,最后的结果就是将高位的1,向后涂抹 (smear),全部变为1。

移位5次的原因在于 Java 中的整数是32位的,正好是2的 5次方。

算法刚开始的减一操作,则是为了防止刚开始传入的数字便是 2 的幂数。用来保证最终的结果是大于等于传入的参数的值。

扩容的临界值

HashMap 能够放置元素的最小容量为 4,最大容量为 1 << 30,并且每次扩容之后的容量大小都是 2 的幂数。 什么会扩容呢?在每次调用 HashMap 的 put 方法时,在进行 size++ 时,会与 threshold 进行比较,当超过 threshold时,就会自动扩容。而这个 threshold 的取值为容量的 ¾ ,其值的更新之时,是在一维数组 table 根据乘以2的容量,申请空间之时,即 makeTable 方法:

1
2
3
4
5
6
7
8
9
10
11
/**
* Allocate a table of the given capacity and set the threshold accordingly.
* @param newCapacity must be a power of two
*/
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;
}

这里主要研究一下这个获取容量为 ¾ 的算法,将 newCapacity 右移1位,即获取的是 1/2;右移2位,即获取 1/4;另外再加上 newCapacity 为2的倍数,所以这里的 ¾ 毫无破绽。

扩容 * 2实现中的元素转移

假如我当前 HashMap 中的容量(capacity)为8,在执行元素的获取及存放是,都是先拿元素的 hash 值,跟 capacity – 1 即 7,对应的二进制为 111,执行与操作,获取的结果即为对应所存放数组中的索引。

而当 HashMap 在进行扩容 * 2 之后,元素的获取也要满足上面的方法,那在扩容的时候,就要先前数组到新数组的赋值,那它这个重新索引的算法是怎么进行的呢?

在执行 doubleCapacity方法时候,会进行这个操作:

1
2
3
4
5
6
7
8
9
10
11
for (int j = 0; j < oldCapacity; j++) {
   // 获取不为空的元素
   HashMapEntry<K, V> e = oldTable[j];
   if (e == null) {
       continue;
   }
   int highBit = e.hash & oldCapacity;
   newTable[j | highBit] = e;

    /**省略 **/
}

oldCapacity 为2的幂数,获取到的 highBit 也是 2 的幂数。若是 e.hash 对应在 oldCapacity 的高位也是相同的 1,则 newTable的索引 j | highBit则是相当于 j 加上了 2 的幂数,即 j | highBit 相对于 newCapacity 来说,从前半段移动到后半段;若是 e.hash 对应在 oldCapacity 的高位不为1,则获取到 highBit 为零,则相应旧数组迁移至新数组的索引位置还是维持原样。

简化上面的公式:

公式一: oldIndex = ( 2n -1) | hash
公式二: hash & 2n | oldIndex = newIndex

可知新的 newIndex 同时也满足:

公式三: newIndex = (2n+1 – 1) | hash

若是我们将公式一和公式三都代入公式二中,消除 oldIndex 和 newIndex 可得到:

公式四: hash & (2n -1) | (hash & 2n) = hash & ( 2n+1 – 1)

这里发现这个公式,很是符合结合律,即:

( a & x ) | ( a & y ) = a & ( x | y )

不要问我怎么证明这个公式是对的。(我是问了个妹子,妹子直接告诉不要纠结公式,直接读字面量,即与或操作,就可发现这个公式是正确的。)

这样的话,将上面的公式执行结合律的话,可得公式四的左边:

hash & ((2n -1) | 2n ) = hash & ( 2n+1 – 1)

确定是跟公式四的右半部分相等。至此,可证明这个扩容移位的操作是毫无破绽的,不过一时半会理解起来还是颇为费劲的,也不得不感叹作者的强大。

Hash 值的生成

在进行元素的存放及获取时,都会获取元素的 hash 值,(即是 key 的 hash值),而一个好的 HashMap,应该是元素均匀地放置在数组中,而不应该大量地出现簇拥现象,(即对应的 HashMapEntry 的 next 指针不为空)。所以仅仅依靠原始的 key 的 hash 值,则是不靠谱的。所以 HashMap 的算法都会进行二次 hash,但我发现 java 中的版本 跟 android 版本实现完全不一致:

  • Android的实现(以 Android API 23 为例) 这里真正的实现是在 Collections 类中:
1
2
3
4
5
6
7
8
9
10
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);
}

这个算法看的是一脸懵逼,若是有哪位大神看懂了,希望能够指点一下小弟。这里可去参看注释中提到的 Wang/Jenkins hash,这里是借鉴这位大神的实现。算法最终达到的效果就是一个网友提到的“崩坏性”,即微小的改动,也会触发结果的大变样。

  • Java的实现 (以 JDK 1.8 为例)
1
2
3
4
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

明显地看出它这里处理就相当简单了,只将高位进行后移16位,然后进行异或就结束了。不过官方文档给出的说法是,因为其 table 大小是 2n ,其实发生碰撞的概率很小,另外在 1.8 中碰撞的链表已经修改为了树结构,所以这里是针对速度、实用及位扩展操作复杂度的一个权衡。

线程同步

另外需要谨记的是,HashMap 不是线程安全的,若出现多线程访问的问题,需要实用 Collections.synchronizedMap(Map<K, V> map) 方法来对 map 再进行一次包装。不过其返回的数据结构 SynchronizedMap 也是很简单的,采用组合的方式持有 map,然后针对 map 的每个操作,都加上了同步块。

至此,HashMap 应该了然于胸了,若是小伙伴还有什么疑问的话,欢迎一起交流。

版权归作者所有,转载请注明原文链接:/blog/2016/08/26/hashmap-knowledge-elements/

给 Ta 个打赏吧...

Comments