HashMap 相关学习

发表于 更新于 Valine：
  • 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 进行运算的