HashMap 相关学习

  • HashMap 中的位运算
  • 准备用 HashMap 存 1w 条数据,构造时传 10000 还会触发扩容吗
  • HashMap 源码分析
  • HashMap 为何从头插入改为尾插入
  • HashMap 在 Jdk1.7 和 1.8 中的实现
  • 面试必备:HashMap、Hashtable、ConcurrentHashMap 的原理与区别
  • 由 HashMap 哈希算法引出的求余 % 和与运算 & 转换问题

分析 Hashtable、HashMap、TreeMap 的区别

  • HashMap 是继承自 AbstractMap 类,而 HashTable 是继承自 Dictionary 类。不过它们都同时实现了 map、Cloneable(可复制)、Serializable(可序列化)这三个接口。存储的内容是基于 key-value 的键值对映射,不能有重复的 key,而且一个 key 只能映射一个 value。HashSet 底层就是基于 HashMap 实现的。
  • Hashtable 的 key、value 都不能为 null;HashMap 的 key、value 可以为 null,不过只能有一个 key 为 null,但可以有多个 null 的 value;TreeMap 键、值都不能为 null。
  • Hashtable、HashMap 具有无序特性。TreeMap 是利用红黑树实现的(树中的每个节点的值都会大于或等于它的左子树中的所有节点的值,并且小于或等于它的右子树中的所有节点的值),实现了 SortMap 接口,能够对保存的记录根据键进行排序。所以一般需求排序的情况下首选 TreeMap,默认按键的升序排序(深度优先搜索),也可以自定义实现 Comparator 接口实现排序方式。

一般情况下我们选用 HashMap,因为 HashMap 的键值对在取出时是随机的,其依据键的 hashCode 和键的 equals 方法存取数据,具有很快的访问速度,所以在 Map 中插入、删除及索引元素时其是效率最高的实现。而 TreeMap 的键值对在取出时是排过序的,所以效率会低点。

TreeMap 是基于红黑树的一种提供顺序访问的 Map,与 HashMap 不同的是它的 get、put、remove 之类操作都是 o (log (n)) 的时间复杂度,具体顺序可以由指定的 Comparator 来决定,或者根据键的自然顺序来判断。

对 HashMap 做下总结
HashMap 基于哈希散列表实现 ,可以实现对数据的读写。将键值对传递给 put 方法时,它调用键对象的 hashCode () 方法来计算 hashCode,然后找到相应的 bucket 位置(即数组)来储存值对象。当获取对象时,通过键对象的 equals () 方法找到正确的键值对,然后返回值对象。HashMap 使用链表来解决 hash 冲突问题,当发生冲突了,对象将会储存在链表的头节点中。HashMap 在每个链表节点中储存键值对对象,当两个不同的键对象的 hashCode 相同时,它们会储存在同一个 bucket 位置的链表中,如果链表大小超过阈值(TREEIFY_THRESHOLD,8),链表就会被改造为树形结构。

有个问题要特别声明下

  • HashMap 在 jdk1.7 中采用表头插入法,在扩容时会改变链表中元素原本的顺序,以至于在并发场景下导致链表成环的问题。
  • 在 jdk1.8 中采用的是尾部插入法,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。

我们可以简单列下 HashMap 在 1.7 和 1.8 之间的变化:

  • 1.7 中采用数组 + 链表,1.8 采用的是数组 + 链表 / 红黑树,即在 1.7 中链表长度超过一定长度后就改成红黑树存储,这个改变的阈值为 8,缓冲值为 6。
  • 1.7 扩容时需要重新计算哈希值和索引位置,1.8 并不重新计算哈希值,巧妙地采用和扩容后容量进行 & 操作来计算新的索引位置。
  • 1.7 是采用表头插入法插入链表,1.8 采用的是尾部插入法。
  • 在 1.7 中采用表头插入法,在扩容时会改变链表中元素原本的顺序,以至于在并发场景下导致链表成环的问题;在 1.8 中采用尾部插入法,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。

关于扩容问题

在 HashMap 中,提供了一个指定初始容量的构造方法 HashMap(int initialCapacity),这个方法最终会调用到 HashMap 另一个构造方法,其中的参数 loadFactor 就是默认值 0.75f。

其中的成员变量 threshold 就是用来存储,触发 HashMap 扩容的阈值,也就是说,当 HashMap 存储的数据量达到 threshold 时,就会触发扩容。

从构造方法的逻辑可以看出,HashMap 并不是直接使用外部传递进来的 initialCapacity,而是经过了 tableSizeFor() 方法的处理,再赋值到 threshole 上。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 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;
}

tableSizeFor() 方法中,通过逐步位运算,就可以让返回值,保持在 2 的 N 次幂。以方便在扩容的时候,快速计算数据在扩容后的新表中的位置。

那么当我们从外部传递进来 1w 时,实际上经过 tableSizeFor() 方法处理之后,就会变成 2 的 14 次幂 16384,再算上负载因子 0.75f,实际在不触发扩容的前提下,可存储的数据容量是 12288(16384 * 0.75f)。

这种场景下,用来存放 1w 条数据,绰绰有余了,并不会触发我们猜想的扩容。

当我们把初始容量,调整到 1000 时,再回到 HashMap 的构造方法,threshold 为扩容的阈值,在构造方法中由 tableSizeFor() 方法调整后直接赋值,所以在构造 HashMap 时,如果传递 1000,threshold 调整后的值确实是 1024,但 HashMap 并不直接使用它。详细解释见这里

结论:虽然 HashMap 初始容量指定为 1000,会被 tableSizeFor() 调整为 1024,但是它只是表示 table 数组为 1024,扩容的重要依据扩容阈值会在 resize() 中调整为 768(1024 * 0.75)

通常在初始化 HashMap 时,初始容量都是根据业务来的,而不会是一个固定值,为此我们需要有一个特殊处理的方式,就是将预期的初始容量,再除以 HashMap 的装载因子,默认时就是除以 0.75

例如想要用 HashMap 存放 1k 条数据,应该设置 1000 / 0.75,实际传递进去的值是 1333,然后会被 tableSizeFor() 方法调整到 2048,足够存储数据而不会触发扩容。

当想用 HashMap 存放 1w 条数据时,依然设置 10000 / 0.75,实际传递进去的值是 13333,会被调整到 16384,和我们直接传递 10000 效果是一样的。

tableSizeFor 方法详解

  • 让 cap-1 再赋值给 n 的目的是使得找到的目标值大于或等于原值。例如二进制 0100, 十进制是 4, 若不减 1 而直接操作,答案是 0001 0000 十进制是 16,明显不符合预期。

  • 对 n 右移 1 位:001xx…xxx,再位或:011xx…xxx

  • 对 n 右移 2 位:00011…xxx,再位或:01111…xxx

  • 对 n 右移 4 位…

  • 对 n 右移 8 位…

  • 对 n 右移 16 位,因为 int 最大就 2^32 所以移动 1、2、4、8、16 位并取位或,会将最高位的 1 后面的位全变为 1。

  • 再让结果 n+1,即得到了 2 的整数次幂的值了。

    img

求余 % 和与运算 & 转换

很多哈希算法,为了使元素分布均匀,都是用的取模运算,用一个值去模上总长度,即 n% hash。我们知道在计算机中 & 的效率比 % 高很多,那么如何将 % 转换为 & 运算呢?在 HashMap 中,是用的 (n - 1) & hash 进行运算的