创意电子

标题: 看完这篇，终于搞懂HashMap的源码了 [打印本页]

作者: Java码农之路 时间: 2020-8-27 13:48
标题: 看完这篇，终于搞懂HashMap的源码了
配景

HashMap是我们在平时开发最常用的容器之一，但是我们有真正了解过它吗？他是线程安全的吗？它是以何种方式来存储的呢？为什么初始化的容器大小是2的n次幂呢？他是怎样进行扩容的呢？他是怎样实现并发安全呢？等等一系列问题。正是知己知彼才能百战百胜，以是我打算深入理解一下hashMap
hashMap脑图

为了理清思路和能快速记着hashMap的“面貌”就大概列了一下

看完脑图，其中很多还是不够详细的。只是概述了内容。

HashMap

hashMap的概述

hashMap，继承Map集合，以key-value情势存储，其中key可以为null ，value是可以重复，其数据是无序的，且会在扩容的时候发生改变。
hashMap在进行存储的时候的步骤

链表转红黑树

在1.8的时候，hashMap加用了红黑树的数据结构，当某一数组的某一个位置hash冲突到达8个的时候，就会将链表转为红黑树，其原因就是提高插入和查找的效率，利用链表的插入尾节点的效率是o（n），而利用了红黑树的话插入和查找都是O（logn）我们来看一下详细的插入流程：

JDK1.7和1.8的扩容

触发条件：数组长度X负载因子（默认0.75）到达这个数值时在1.8会直接触发扩容，而在1.7会出现再判断一个这个节点是否有占用，如果没有就插入，有的话就扩容
1.7和1.8 的时候在扩容的时候会将新建一个为原数组两倍的数组，
1.7将原数组中的hash进行重新计算hash参加到新数组，然后将hash碰撞的链表数据，以头插法进行插入到新的数组上，然后移动。这个过程在并发环境下会有可能出现循环依赖的环境，导致无限循环耗尽CPU。
而1.8 如果这个计算出来的hash值在原有数组位置+旧数组长度则放在新的数组上的这个原有数组位置+旧数组长度上面，新数组没有则放在原来的位置上，新的插入的数据

hash计算的方式

如果key为null的话就放在第一个数组的下标为0的位置。
如果不为先计算出hashCode，再将hashCode 无符号右移，忽略符号位，空位都以0补齐。然后再进行异或运算。

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }1234

1.7 的计算方式

将计算出来的hash值和数组的长度减1进行与运算，计算出来

static int indexfor(int h,int length) {// 其中的legth-1 也是为什么 hashMap的容量为2的n次幂的原因return h & (length-1);}1234从上面的两种通过hash值计算数组下表位置index的方式都可以将计算出来的值在数组length的长度内。至于那种性能更高速率更快，散列的空间更加匀称，那毋庸置疑，肯定1.8内里的。
上面说到可负载因子是0.75，为什么默认的负载因子是0.75呢？

个人理解：首先0.75 会用作扩容，这个值越大直到1，那扩容的次数是不是概率越低，hash冲突是不是越小？因为他这个值决定了到达多大值就会扩容。如果设置一个0.1,那么在第一次存储完成后就扩容了，那肯定第二次进行计算hash的时候由于数组很大，那也就降低了hash碰撞。我的理解就是在扩容次数和hash冲突之间起到一个平衡的作用
jdk1.7 中的注教学明：作为一般规则，默认负载因子（0.75）在时间和空间资本上提供了很好的折衷。较高的值会降低空间开销，但提高查找资本（表现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该思量预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
jdk 1.8中：抱负状态下，在随机哈希值的环境，对于loadfactor = 0.75 ，虽然由于粒度调整会产生较大的方差，桶中的Node的分布频率服从参数为0.5的泊松分布。

hash冲突的几种解决方式

开放定址法

从发生冲突的那个单元起，按照肯定的序次，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。

链地点法（拉链法）hashMa也就是用的这种方式

链接地点法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除重要在同义词链表中进行。链表法适用于常常进行插入和删除的环境。

再哈希法

就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。
既然已经看了hashMap的源码我们再联系一下线程安全的hashMap都有哪些呢

ConcurrentHashMap

不消说我们都知道concurrentHahMap是线程安全版的hashmap ，其底层源码与hashMap雷同，但是在数据结构上改变了一下，加了一个sagment[] ,这个sagement对象数组内里有多个小的hashMap，在进行操作的时候会对sagment进行加锁，让其同步执行。由于当sagment内里hashMap越多的时候那么这个并发安全系数就越低，以是在ConcurrentHashMap内里有一个并发安全系数。来控制sagment内里的hashMap的数量。其上面的说法是jdk1.7版本，这个锁采用的是rentrantLock。但是在JDK1.8中利用的是更细粒度的锁利用Sychronized和CAS来进行枷锁。
1.8中的一个列子

1.7中的sagement[]
//get方法是不加锁的，所有共享变量都是通过volatile修饰的，确保或许最新值

public V get(Object key) { Segment s; HashEntry[] tab; int h = hash(key); long u = (((h >>> segmentShift) & segmentMask)

作者: 大毛怪咔咔 时间: 2020-8-28 07:37
转发了

欢迎光临创意电子 (https://wxcydz.cc/)