HashMap 是基于散列表的数据结构。所谓散列表,它通过键值对的方式存储数据,把 key 通过散列算法计算出一个存储地址,将 value 放入这个地址中。散列表是最常用的数据结构之一,在不考虑 hash 冲突的情况下,散列表的查询复杂度是 O(1)。
Java 中,HashMap 是基于数组和链表来实现的,也许有人会奇怪,为什么不是用一个数组,不同的 hash 值对应数组中不同的位置。 其实,链表是用来解决 hash 冲突的。数组的长度有限,不同的 key 值,通过 Hash 算法也有可能算出同样的值,这就是 Hash 冲突的产生的原因,当一个地址,对应了多个值的时候,就把这些值放到链表中去,因此 Hash 冲突会使得查找费时间。
所以,有一种攻击手段,通过精心设计的 key 值,使得所有的 key 计算出的 hash 值都是同一个,即所有的 key 值都是冲突的,这样的话,所有的元素都放在一个链表里,Hash 表就变成了一个单链表,查询元素时必须遍历这个链表,使得性能大大降低。
Java 中,HashMap 默认的数组大小是 16,当满足一定条件的时候,这个数组会自动扩容,并且是按但并不是有了 16 个元素之后才扩容,而是根据加载因子来计算,默认是 0.75,即一旦元素数量大于 16*0.75 时,HashMap 会自动扩容,扩容到原先的 2 倍大小,这一步是很费时间的,因此,尽量合理的设计初始容量和加载因子。
Java
12345 | 注意,HashMap中数组的大小一定是2的整数次幂,默认是16,即使定义入如下 HashMap<String,String> map = new HashMap<String, String>(5); 那么它的默认的容量也是最近的2的整数次幂,即8。 |
---|
在 Java8 之后,HashMap 进一步优化 Hash 冲突,冲突的元素不再是简单的放入链表中,而是根据当链表长度,当长度太长(默认超过 8)时,链表就转换为红黑树,红黑树的查询复杂度比链表低很多。
自行查资料把,网上很多的。反正当时看懂了,几天后就会忘记了。
HashMap 键值对皆可 null。
HashMap 线程不安全。
在 resize 的时候,多线程同时操作 HashMap 中的链表时,有一定的几率形成循环链表,这就导致了获取值的时候陷入循环链表,造成死循环。具体细节,有兴趣的可以看网上的各种分析。
https://tech.meituan.com/java_hashmap.html
http://yikun.github.io/2015/04/01/Java-HashMap 工作原理及实现/