HashMap与ConcurrentHashMap 的数据结构

ziruoxiangyi 2017-12-24

HashMap:

数组与链表,每个数据对应一个链表

插入时进行与运算

http://blog.csdn.net/tingting256/article/details/52475422

数组默认长度16,当超过16*0.75=12时,组数长度变为16*2->叫resize,毁

HashMap的基础构造器HashMap(intinitialCapacity,floatloadFactor)带有两个参数,它们是初始容量initialCapacity和加载因子loadFactor。

https://www.cnblogs.com/ITtangtang/p/3948406.html

相同含义的两个对象,插入同一个key:

http://blog.csdn.net/zbuger/article/details/51029898

为什么数据是2的n次幂

为了更均匀打到槽点。与运算

http://www.cnblogs.com/ysocean/p/9054804.html

当lenth=2n时,X%length=X&(length-1),模运算%可以变换为按位与&运算

早期版本是直接取模%,后期改为位运算

一个十进制数对一个2n的数取余,我们可以将这个十进制转换为二进制数,将这个二进制数右移n位,移掉的这n位数即是余数。

为什么是数组长度是16

计算卡槽点时,具体落到哪个数组时,做与运算时

hash(hashCode(key))&(length-1)->会落到位置范围内

二进制:Interger.toBinaryString(15);

容量到了12会扩容:在扩容的时候更多的节点不需要重新计算到新槽点,hash之后的桶的角标是不变的。

为什么0.75

过低,小一点:扩容频繁。

过高,大一点:扩容不容易发生,数组重复概率增加,导致get和put时间增多,冲突需要遍历大量链表空间。

finalinthash(Objectkey)里有>>>,>>>

降低重复冲突概率

深入理解:https://www.zhihu.com/question/20733617

“扰动函数”混合原始哈希码的高位和低位,加大低位随机性,为了减少数组碰撞概率,减少10%。

Java8觉得扰动做一次就够了,做4次的话,多了可能边际效用也不大,所谓为了效率考虑就改成一次了。

当获取对象时get,hash找到数组槽位,循环链表,通过键对象key的equals()方法找到正确的键值对,然后返回值对象。

HashTable:

数组默认长度11

http://blog.csdn.net/xuefeng0707/article/details/40834595

继承的父类不同

线程安全性不同

key和value是否允许null值

hash值不同,插入算法也不同,hashtable取取模运算,hashmap与运算。

是否提供contains方法

http://blog.csdn.net/fujiakai/article/details/51585767

ConcurrentHashMap:

http://blog.csdn.net/yan_wenliang/article/details/51029372

segment数组,每个数组是一个hashtable,里面有分段锁

多线程put时,当同一数组存储时线程加锁,不同数组时,没有锁,效率的提升。

相关推荐