- 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 | /** |
在 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的整数次幂的值了。
求余%和与运算&转换
很多哈希算法,为了使元素分布均匀,都是用的取模运算,用一个值去模上总长度,即 n%hash。我们知道在计算机中 & 的效率比 % 高很多,那么如何将 % 转换为 & 运算呢?在HashMap 中,是用的 (n - 1) & hash 进行运算的