HashMap 介绍
这个该怎么写了?其实网上好多博客说了这个,其实我看了之后,甚至看了源码之后我也不知道怎么写,源码中Hashmap的介绍大致如下:
1 | Hashmap 大致是等于hashtable的,除了非同步和允许null值之外; |
首先我们介绍下它的内部数据结构吧。
HashMap的内部结构
Hashmap 是由Node<K,V>[] table
和链表组成的结构,数组被分为一个个的桶(bucket),通过 hash 值在这个桶上进行寻址。hash 值相同的键值对就以链表的形式存储,如果链表的大小超过 TREEIFY_THRESHOLD=8
就会将链表进行树化。
接下来我们看看它的一个初始化方法:
1 |
|
在 new 一个 hashmap 的时候会发现,Node<K,V>[] table;
table 就没有设值。
然后我么来看一个 put 方法:
1 | final V putVal(int hash, K key, V value, boolean onlyIfAbsent, |
总的一个put流程大致就是: 初始化或者 resize() 扩容和树化;
现在我们看看 resize() 方法,
1 | final Node<K,V>[] resize() { |
看完 resize 就会发现发现它做了很多事,初始化,扩容,数据复制;数据复制也会造成一定的开销。
另外resize中的防止rehash并且分散之前的冲突节点的算法也很巧妙:
另外我们看下树化:treeifyBin(tab, hash);
1 | final void treeifyBin(Node<K,V>[] tab, int hash) { |
所以可以看到 HashMap 的 LOAD_FACTOR
加载因子和容量是多么的重要了。我们一般的化可以优化为:负载因子 * 容量 > 元素数量
即初始化容量时候,值要大于“预估元素数量 / 负载因子”
hashmap在高并发场景下会发生什么了?
要记住,hashmap本身就被声明为了非同步安全的类,如果在多线程环境下是会有可能导致无限循环占用cpu,size不准确,具体的原因可以看下这篇博客 a beatiful race condition
那么问一下,为什么要进行树化了?
本质上是个安全问题,如果一个对象hash冲突,都被放到一个桶里面,就会形成一个链表,链表的查询是线性的,就会严重影响存储的性能;
另外有种安全攻击叫做“哈希碰撞拒绝服务攻击”,就是构建哈希冲突的数据,恶意代码用这些数据与服务器进行交互,导致服务端cpu大量占用。来达到攻击的目录。
那么,并发下,我们应该怎么使用HashMap了?
明天讲~