HashMap是不可重复key的 Map集合。

数组 链表对比

数组长度不可增加、读取速度块,在内存时一块连续的区域

链表在内存不是一块连续的区域

HashMap底层原理是: 数组 + 链表 当链表长度大于8时 即链表长度等于9,链表结构就会转换为红黑树

map是无序的但是LinkedHashMap 是有序的

JDK 1.7 HashMap 源码分析

安装JDK 1.7 太烦了,我直接参考于:https://blog.csdn.net/qq_19431333/article/details/61614414

文章不错!!!!

核心属性 (规定一些默认的值)

threshould 必须是2的 次方 由 tableSizeFor(int cap) 进行二进制位运算得出

locaFactory 一般等于 0.75f ,这是经过 科学计算的

size

modCount 容量变化次数

构造方法 (4个)

进行一些参数的校验,

put(K key, V value)方法

  1. 如果哈希表还未创建,那么创建哈希表
  2. 如果键为null,那么调用putForNullKey插入键为null的值
  3. 如果键不为null,计算hash值并得到桶中的索引数,然后遍历桶中链表,一旦找到匹配的,那么替换旧值
  4. 如果桶中链表为null或链表不为null但是没有找到匹配的,那么调用addEntry方法插入新节点

1.7的addEntry方法

将键值对,以新节点作为链表的头节点,在JDK 1.8 之后,采用尾插法!

resize方法

将原有数组容量,扩容原来的2倍(实际数组的扩容,就是创建一个新的数组),扩容后,需要 转移原来的元素 到 新结构上的元素(相当于 进行原来的put),由于是头插法,如果 原来属性是 1,2,3 那么新的结构就是 3,2,1

get方法

remove方法

replace方法

JDK7 HashMap的桶初始容量是16(只有第一次put的时候,才会初始化,put源码有说明)
HashCode的范围-2的31次方到2的31次方-1
长度2的n次方原因: hash & 数组的长度-1 只有是2的n次方的时候 -1 才能拿到2的n次方的值 进行按位与 才能快速拿到下标,并且均匀分布
如果遇见相同的key value,就直接覆盖(key存在,不会被替换,实际是替换value)。
扩容机制 :如果新put值。一旦超过当时的容量乘以负载因子,容量就会翻倍,但不会缩容。
首先先扩容,按照原来的顺序,然后再rehash,再添值
put方法:先进行hash()运算,获取hashcode值,(目的是尽量减少Hash碰撞)然后indexFor获得length-1&h 得出再数组中的位置,判断这个位置有没有key,有的话,替换value;如果没有key,调用addEntry()方法,这个方法先把键值对new出来,接下来判断是否超过阈值,接下来进行。一旦超过阈值,就把表的尺寸扩大,然后进行复制老数组。JDK7是反转链表的位置,多线程get时会出现链路回环,JDK8时顺序读取,就不会出现get链路回环,然后性能最消耗的就是:一旦resize(扩容)就按照原来的顺序,重新进行rehashu运算,重新插入。
get方法:先进进行hash(),然后去数组上找,然后判断链表。
HashMap线程不安全的原因:假如两个线程,同时操作HashMap,如果两个线程同时扩容,存储在链表的顺序会翻过来,将元素放在头部,避免尾部遍历,如果发生了,就死循环了。
JDK7 HashMap的死锁问题。

JDK7put流程(存储的结构Hash、Key、Value、Next 。hash存储的时哈希值,key是键值,value是值,next指向下一个的索引下标)
将元素进行hash运算获得索引下标,然后插入数组中,一旦发生Hash碰撞,将新的键值对的next指向原在数组位置上的元素 .
为什么不是将老值的next指向新值呢? 如果要将老值的next指向新值,就需要重新遍历修改,浪费性能。

创建HashMap ==>初始容量initialCapacity(必须是2的指数次幂)、加载因子loadFactor(默认是0.75)、扩容阈值threshHold(容量*加载因子)
HashMap的数组初始化,不在构造方法里面(构造方法会判断初始容量、负载因子是否合法,不合法,强行转成2的指数次幂,保障分布均衡),使用Put的时候再初始化。

第一次put的时候,判断数组有没有初始化,如果没有直接初始化数组,然后去判断要插入的key,没有key,直接(putForNullKey)添加值,直接返回。如果值不为空,先进行hash运算,得出哈希值(hash散列,位扰动,尽可能减少Hash碰撞),接下来将这个Hash运算成存储的索引下标(与运算( 运算规则:两个数都转为二进制,然后从高位开始比较,如果两个数都为1则为1,否则为0。)==>Hash值&数组长度-1; PS:保证结果在0到length-1的范围,否则就会出先索引越界异常)不用%的原因,%的散列度不高,运算效率没二进制与高。)拿到索引位置后,遍历该节点上面的所有的节点,看一下有没有相同的key,有的相同的key,把新值替换老值。如果没有,那就添加新的节点(实际添加节点的时候,会判断是否满足扩容机制原来的两倍(扩容机制JDK7是键值对数量>=满足阈值,并且插入的数组上有键值对才会扩容)扩容完成后,将老值添加到新的数组上 (transfor()首先拿到新数组的长度,然后遍历集合死循环e键值对,将老e指向老的头节点,新的next指向头节点下面的节点,将重新的rehash,调用indexFor拿到在新数组的位置,把值复制过去,新next指向新数组上的头节点,将e指向老节点的next。第一轮循环结束,然后e会指向老节点的下个节点,如此循环,直到e未null为止),在添加新值进去,将下标指向原来数组的那个头部节点)。

JDK1.7 HashMap链表回环的原因:

可以理解成 头插法,JDK 1.8 是尾插法

再多线程情况下:线程1、2都要去扩容,原来的结构是:B存在数组上,A存在B的链表上,如果线程1扩容、复制值完毕(假设有两个元素添加到链表上,数组上存的是A(e=a,next=B),该数组上的链表村的是B(e=b,next=null))线程1扩容完毕,线程二唤醒了,他去读取数据,先读取数组上的A(e=a,next=B)存入数组,然后读取B(e=b,next=A),此刻就埋下了链表回环的伏笔。当结束后e=next,就变成e=a,但是e.next就会得到A的next,也就是B,这样就形成回环,死锁了。

JDK8的结构
数组+链表+如果链表长度大于8就将链表转为红黑树了。

总结1.7与1.8中 HashMap:

相同点:

默认初始容量都是16,默认加载因子都是0.75。容量必须是2的指数倍数

扩容时都将容量增加1倍

初始时表为空,都是懒加载,在插入第一个键值对时初始化

键为null的hash值为0,都会放在哈希表的第一个桶中

不同点:

1.7是数组+链表,1.8则是数组+链表+红黑树结构

1.7是头插法,1.8是尾插法