关于hashmap

hash表

  • 核心是基于hash值的桶和链表
  • O(1)的平均查找，插入，删除时间
  • 缺陷是hash碰撞（两个对象调用的hashCode方法计算的哈希值一致导致计算的教组索引值相同）

拿电话本来举例子：电话簿上 ABCD…的字母姓排序，Z后面可能是张学友，张三丰，一个字母后面可能有多个名字。Z是hash值，整个横框是hash桶，其整体构成了hash表，姓名之间发生了碰撞

Q1 JDK1.7为什么长度为2的幂

A1：hashmap的元素分配方式是按位与（hash（key）&（length-1）），只有当长度为2的幂的时候，我们对他的长度减一才能得到全部都是1的二进制值，这样对他进行按位与，才能非常快速拿到数据的下标，并且分布还是均匀的。

选取2的幂。减一后做与操作刚好截取hash值的低位。以16为例子，二进制是00….001111，做与操作截取的就是hash的低四位
为什么能减少碰撞？这是因为hashmap的hash值是hashCode右移16位得到的，这么做使得hash值的低位保留了高位的信息，所以只要低位就可以了。
如果你不右移，那么高位信息是被浪费的，只利用低位信息，哈希碰撞的几率会大大增加

HashMap的默认长度为16,是为了降低hash碰撞的几率

添加元素的过程

1.8后的hashmap

jdk1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突（两个对象调用的hashCode方法计算的哈希值一致导致计算的教组索引值相同）而存在的（“拉链法”解决冲突）。jdk1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为8）并且当前数组的长度大于64时，此时此索引位璽上的所有数据改为使用红黑树存储。

补充：将链表转换成红黑树前会判断，即便阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树，而是选择逬行数组扩容。

这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要逬行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以结上所述为了提高性能和减少搜索时间，底层阈值大于8并且数组长度大于64时，链表才转换为红黑树，具体可以参考 treeifyBin() 方法。

当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时，链表转换为红黑树时，效率也变的更高效。
————————————————
原文链接：https://blog.csdn.net/weixin_41105242/article/details/106972635