tsvico的博客

好的代码像粥一样,都是用时间熬出来的

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 进行运算的

坚持原创技术分享,您的支持将鼓励我继续创作!