【老生常谈系列】hashMap 1.7 和1.8的区别

【老生常谈系列】hashMap 1.7 和1.8的区别

之前做过一篇关于hashMap 1.7 和1.8原理分析，在这里再次做一下小结

HashMap 1.7 数据结构

数组+链表。

entry是hashmap的最小单元

每个entry都存有下一个元素的指针，组成一个单向的链表。同一条entry链表的的数据key，计算得到的hash值一定相同（这个是经过HashMap特定的hash计算方法，而不是key本身的hashcode）

put 过程

1. 当key为null ，则加入到table[0]
2. key不为null，就计算key的hash值，根据hash值找到数组的下标。
3. 如果当前的位置上有值，则遍历当前位置上所有对象，如果key完全相同的，就覆盖这个值。
   如果key都不相同，就将要当前值封装成entry ，加入当前链表的头结点处
   如果当前位置没有值，就直接封装成entry加入当前位置

get 过程

1. 根据key计算hash值，进而得到数组的下标，如果当前位置没有值，就返回空，如果当前位置有值，就遍历当前位置上的链表，如果存在一个key完全相等，则返回。如果不存在就返回空null
   所以极端条件下，如果hash碰撞十分严重，链表就会非常的长，这样一来，遍历链表，查询的性能就会变低。.

为什么hashmap容量的大小要设置为2的n次方？

因为当数组的长度为2的N次方的时候，不同的key算的数组的位置的相同的概率小，分布更加均匀。（为什么小，就涉及到位运算）

1.7扩容（最消耗性能）

当存放的元素的个数，大于或者等于，haspmap的容量和负载因子的乘积时，就会成倍的扩容（默认是16* 0.75），新建一个两倍容量的数组，将原来的数组迁移。

扩容的过程中，会重新计算每个元素在数组中的位置，迁移到新的table中。 （扩容过程会消耗资源，会给GC带来压力，因为旧数组失去引用后，会被GC在回收）

为什么不是复制进去呢？因为数组的长度变了，hash的规则也就变了，计算的位置也不一样了。

jdk 1.8 hashmap 1.8 hashMap 数据结构

1.8 hashmap底层采用 数组 + 链表和红黑树实现的。。
初始容量为16，默认的负载因子是0.75，每次扩容会变为原来的2倍，就是2的N次方，
如果当前位置的链表中元素个数大于8的时候，就会转为红黑树。

为什么要用红黑树？

因为在链表模式下，当发生过多的哈希碰撞的时候，链表会越来越长，查询速度会变慢

什么时候转红黑树，什么时候退化成链表

红黑树的出现时机（链表树化）：1. 链表的长度达到8； 2. 元素的总数量达到64。

红黑树退哈成链表： 红黑树中元素的数量小于6。

哈希桶扩容的条件：元素数量 >= 长度（16）× 加载因子（0.75）

1.8put过程：

根据key计算hashcode，然后计算再数组中的下标，如果当前位置上没有值，就直接插入，如果当前位置上有值，就进行遍历，如果存在一个key完全相同，就进行覆盖，如果不存在就通过尾插法插入到链表或者红黑树。如果链表的长度大于8，就自动转为红黑树。

1.8get过程：

根据key计算hashcode，然后计算在数组中的下标位置，如果不存在元素，就返回null，如果存在就进行遍历，如果存在一个key完全相同(hashcode相同，再比较equals)，就返回值，不存在就返回null

问题？

https://blog.csdn.net/weixin_44844089/article/details/105868599

为什么转为红黑树？ 一开始不用红黑树？

1）因为当长度过长，遍历链表的时间也会原来越长，用红黑树可以减少遍历时间
2）如果一开始就使用红黑树，那么就要进行左旋，右旋，变色等 *** 作，在元素个数较小的时候会消耗时间，并且遍历时间消耗与链表没什么区别

可不可以使用二叉树，不用红黑树？为什么阈值是8？

使用二叉树可能会出现只有左子树或者右子树的情况，这样的极端情况下和链表没什么区别
8是因为泊松分布，单个hash槽中元素为8的概率小于百万分之一

一般使用什么作为key？

一般使用String Integer这种不可变的类作为key，他们创建以后hashcode就是定值，不可更改，已经实现了hashcode 和equals方法

为什么key要重写hashcode，和equals?

因为数据插入过程是先计算hashcode，如果两个对象的hashcode相同，那么会定义到同一个位置，但是因为equals不相同，就会重新当做一个新对象插入。达不到我们要的key不重复的效果。

hashmap如何解决线程不安全的情况？

可以使用ConcurrentHashMap或者hashtable，但是hashtable的加锁粗暴，会锁住整个map，ConcurrentHashMap只是锁一个节点

HashTable类是线程安全的，它使用synchronize来做线程安全，全局只有一把锁，在线程竞争比较激烈的情况下hashtable的效率是比较低下的

hashMap如何解决hash冲突？

hash冲突之后，会将当前位置的数据变成一个链表，使用尾插法插入，如果链表长度大于8，就转为红黑树。
转为红黑树的原因是，当hashcode冲突很大时，链表很长，查询性能变慢

hashmap什么时候会触发扩容？

当hashMap的容量达到最大容量值* 负载因子。这个容量是指数组的容量

hashMap扩容时候，每个entry都要重新计算一次hash吗？

在1.7中是需要进行重新hash
在1.8中做了优化，只需要看原来的hash值在扩容之后新增的那一位是0还是1,0的话数组索引没变，是1的话索引变成原索引+原来数组大小

第一个图中可以看出来，JDK1.8是先存储，后扩容。扩容条件只有大于容量*负载因子

JDK1.8的数据结构是数组+链表+红黑树，Node中存储着链表节点next 也是Node结构。

我们可以看出图片标记1处 如果旧值不存在链表，则根据hash值和新容量&计算数组下标并赋值。但是存在链表

如果旧值的hash和旧的容量计算&为0，则扩容后的位置等于原来坐标。

如果旧值的hash和旧的容量计算&为1，则扩容后的位置等于原来坐标+旧的容量

jdk1.8之前并发 *** 作hashmap时为什么会有死循环的问题？

在1.8之前是采用的头插法，并发时候线程不安全，可能两个线程同时进行扩容，节点中的next指针会互相引用，这样就会导致一个链表中会出现循环链表。
（并发过程中头插法，next指针出现了循环链表、）

1.8之后采用了尾插法，就不会出现这个问题。

为什么hashmap容量是1 << 30 ？

1 << 30 = 230，而int的最大值是231 -1，因为hashmap的个数要设置为2的N次方，所以就不能设置为最大值，故而设置为2的30次方。

为何1.8 hashMap随机增删、查询效率都很高的原因是？

原因: 增删是在链表上完成的，而查询只需扫描部分，则效率高。

hashmap线程不安全的地方在哪儿？

1. 在put的过程中，会根据key计算hash值，找到数组中的位置，然后会进行非空判断，如果不存在值就插入。
   这里如果是多线程的 *** 作，多个key具有相同的hash值，那么有的值就会被覆盖，导致数据丢失。
2. 1.7中会产生循环链表（并发过程中头插法，next指针来回指向就出现了循环链表）
3. 可能会造成put非null元素后get出来的却是null，在transfer那一块的代码里面，遍历元素，
   

红黑树的五条规则 ？

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

https://www.zhihu.com/question/312327402/answer/1263993419

在树的结构发生改变时（插入或者删除 *** 作），往往会破坏上述条件 3 或条件 4，需要通过调整使得查找树重新满足红黑树的条件。

总结：

1.hashMap和hashtable区别

hashTable是线程安全的
hashMap的键可以为null
将hashtable加锁的方式说明一下，是用sy关键字锁住整个数组，所以推荐用ConcurrentHashMap进行线程安全的解决。

hashmap的底层实现。

1.数据结构
2.put get 过程
3. 扩容方式
4. hash函数（扩容时候，不需要每次都重新计算位置，只需要看扩容后的那一位hash值，是0，还是1）