hashmap 的相关问题在校招面试中十分常见, 作为新人, hashmap 的各个问题应该要理解的十分透彻才行. 此外, concurrenthashmap, hashtable 也是经常与 hashmap 一同被问, 下文中都有介绍.
hashmap 在 jdk1.8 之前底层使用的是数组+链表的拉链式结构; 在 jdk1.8 之后引入了红黑树, 当链表长度大于阈值的时候就会将这个链表转化为红黑树.
如上面所说, jdk1.8 中对 hashmap 做了一些改动, 在 jdk1.8 之前链表的插入使用的是头插法, 作者认为刚刚插入的数据被查询的可能性比较大, 头插法在多线程 resize 的时候可能会产生循环链表. jdk1.8 之后改为了尾插法, 在扩容的时候会保持链表元素原本的顺序, 避免了链表成环的问题, 但是改完以后 hashmap 依然不能支持并发场景. (不过 hashmap 本来也不是为多线程而生的呀)
当链表长度大于阈值的时候就会将这个链表转化为红黑树, 链表转化为红黑树的默认阈值为 8, 如果红黑树的节点个数减少到一定程度也会转化为链表, 这是出于时间和空间的折中方案, 默认会在节点个数减少到 6 的时候进行转化.
上面所讲的阈值为什么选择 8 和 6 呢? 根据泊松分布, 在负载因子为 0.75 (hashmap 的默认值) 的时候, 单个 hash 槽内元素个数为 8 的概率小于百万分之一, 所以将 7 作为一个分水岭, 等于 7 的时候不进行转化, 大于等于 8 时转化为红黑树, 小于等于 6 的时候再转化为链表.
通过阅读源码, 我们可以发现它是通过 (h = key.hashcode()) ^ (h >>> 16) 来计算 hash 值, 混合了 key 哈希值的高 16 位和低 16 位.
hashmap 的默认容量 (其实就是拉链式中数组的长度) 为 16, 每次扩容都会变为原来的 2 倍, 并保证容量为 2 的幂次, 如果在构造函数或者扩容的时候给定一个不是 2 的幂次的数, 它会自动向上扩展到一个 2 的幂次.
我要评论hash % len 等价于 hash & (len - 1), 与运算相对取模运算更快.(len - 1) 的所有二进制位都为 1, 这种情况下, 只需要保证 hash 算法的结果是均匀分布的, 那么 hashmap 中各元素一定是均匀分布的.threshold, 源码注解中写着 the next size value at which to resize (capacity * load factor), 表示它用来判断下次什么时候扩容的字段. 当数组发生扩容时, 只需要再比较 1 bit 即可确定这个节点是否需要移动, 要么不动, 要么移动原来的数组长度.这应该是一个经验值, 要保证容量为 2 的幂次, 并且需要在效率和空间上做一个权衡, 太大浪费空间, 太小需要频繁扩容.
| 集合 | 线程安全性 | 效率 | 默认容量 | 扩容方式 | 底层结构 | 实现方式 | 是否支持null值 | 迭代器 |
|---|---|---|---|---|---|---|---|---|
| hashmap | 不安全 | 高 | 16 | 2n (保证是2的幂次) | 数组+链表+红黑树 | 继承abstractmap类 | key允许存在一个null, value可以为null | fail-fast 机制 |
| hashtable | 安全 | 低 | 11 | 2n+1 | 数组+链表 | 继承dictionary类 | key和value都不能为null | enumerator |
首先 hashmap 本来就不是针对多线程情况而设计的, hashtable 是遗留类, 它内部使用 synchronzied 来修饰方式, 使得它能够成为一个同步集合, 但这种方式效率比较低.
我们可以通过两种方式来获得同步的 hashmap.
collentions.synchronizedmap(map<k,v> m) 来将一个非同步 map 变为同步 map. 这种方式的原理比较简单, 与 hashtable 类似, 它会把传入的 map 对象作为 mutex 互斥锁对象, 然后在方法里都加上 synchronized(mutex) 的同步.java.util.concurrent 包下的同步集合 concurrenthashmap, 这个集合将在下面详细介绍./* hashmap 中计算 hash 值的过程 */
static final int hash(object key) {
int h;
return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}
/* hashtable 中 put 的部分源码 */
public synchronized v put(k key, v value) {
// make sure the value is not null
if (value == null) {
throw new nullpointerexception();
}
// makes sure the key is not already in the hashtable.
entry<?,?> tab[] = table;
int hash = key.hashcode();
int index = (hash & 0x7fffffff) % tab.length;
...
}
首先从源码上看, hashtable 在 put 值为 null 的 key 或者 value 时候会抛出 nullpointerexception, 但是 hashmap 对值为 null 的 key 做了特殊处理. 看似很简单的处理, 那这么处理的内在原因是什么呢?
hashtable 的迭代器使用了安全失败机制 (fail-safe), 这种机制在遍历元素的时候, 先复制原有集合内容, 在拷贝的集合上进行遍历, 这会使得每次读取到的数据并不一定是最新数据. 如果可以使用 null 值, 将会无法判断对应的 key 是不存在还是为空. conrrenthashmap 也是同样的道理.
hashmap 则是使用安全失败机制 (fail-fast), 这种机制是指在用迭代器遍历一个集合对象的时候, 如果遍历过程中对集合对象的内容进行了修改, 则会抛出 concurrent modification exception. 通过阅读源码, 我们可以发现这种机制使用了 modcount 变量, 每次遍历下个元素的时候, 都会检查 modcount 变量的值是否发生改变, 如果发生改变就会抛出异常. 我们不能依赖这个异常是否抛出来进行并发控制, 这个异常只建议用于检测并发修改的 bug.
java.util 包下的集合 (除了同步容器: hashtable, vector 等) 都是 fail-fast, 而 java.util.concurrent 包下的集合和 java.util 包下的同步集合都是 fail-safe.
它们的底层结构不一样: concurrenthashmap 的底层结构与 hashmap 类似, 使用了数组+链表+红黑树, 而 hashtable 使用了数组+链表.
它们都是线程安全的, 但它们实现线程安全的方式不一样.
linkedhashmap 继承自 hashmap, 底层结构与 hashmap 一致, 主要区别是 linkedhashmap 维护了一个双向链表, 记录了插入数据的顺序. linkedhashmap 十分适合用来实现 lru 算法, lru 算法主要利用了双向链表和 hashmap, 这简直就是量身打造, 要是手撕代码题用 linkedhashmap 简直是作弊, 一般面试官不会让你这么干的
如对本文有疑问， 点击进行留言回复！！
SpringBoot引用阿里easyexcel，Excel导出返回浏览器下载
HashMap、Hashtable、ConcurrentHashMap三者间的异同
解决RecycleView 中Item包含Edittext时，滑动view复用导致数据错乱的问题
多线程、同步工作原理、死锁案例、Lock接口、线程的生命周期的讲解及实现
网友评论