--- ### 哈希表  - 哈希冲突：当我们要插入node的时候会首先计算这个node对应的hashcode，hashcode经过**扰动函数**处理后得到**新的hashcode**值，再将hashcode转换为数组下标。如果此时数组中的这一个数组下标下没有node，就可以直接插入node。但是这个数组下标存在node，这个现象就称为**哈希冲突**，这个时候就需要遍历这个数组下标下的链表，如果链表中存在node和待插入的node相等，就将原node覆盖，如果链表中不存在相同的node，就将待插入的node插到链表末尾，作为之前末端Node的next，同时新Node的next==null。 `注意，node由key和value构成，key不可重复，value可以重复` - 所谓的扰动函数就是就是HashMap的hahs方法。使用hash方法就是扰动函数为了防止一些实现较差的hashcode方法。换句话说就是使用扰动函数后可以减少碰撞。-->处理一些极端的情况 ```java //JDK8 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /* Object key为传入的key，如果key为null的话，返回hashcode=0； 如果key不为null的话返回hashcode -->(h = key.hashCode()) ^ (h >>> 16) 即： 首先对key进行相应的hash算法计算，计算出一个哈希值 -->h =key.hashCode() 然后将这个h右移16位，然后将做异或操作 -->(h = key.hashCode()) ^ (h >>> 16) 得到最终的hashcode */ ``` - 为什么右移16位，做异或操作？为了保留高位和低位的信息，表现目标值的信息，减少碰撞。举例说明： ``` 这是因为计算数组下标是通过hashcode$(len-1)计算的 首先，假设有一种情况，对象 A 的 hashCode 为 1000 1000 0011 1100 0000， 对象 B 的 hashCode 为 1110 0010 1000 1010 0000。 如果数组长度是16，也就是 15 （0000 1111）与运算这两个数， 你会发现结果都是0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。 但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（相同为0，不同为1），这样的话，就能避免我们上面的情况的发生。 总的来说，使用位移 16 位和 异或 就是防止这种极端情况。但是，该方法在一些极端情况下还是有问题，比如：10000000000000000000000000 和 10000000001000000000000000 这两个数，如果数组长度是16，那么即使右移16位，在异或，hash 值还是会重复。但是为了性能，对这种极端情况，JDK 的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash 时间，性价比不高 ———————————————— 版权声明：本文为CSDN博主「NO0b」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/q5706503/article/details/85114159 ``` - 如何解决哈希冲突？ - 如果哈希码分布比较均匀（这要求合适的哈希算法）以及数组的长度也足够大，那么就会减少比较的次数。初始化的数组的长度长度为2的幂次方(16)。这是为了减少哈希冲突。 - 数组下标的计算公式为：$(n-1) \& hashcode$,其中$n$表示数组的长度。具体解释如何计算数组下标：一般的操作为计算出元素的hashcode之后，利用$hashcode\%n$，即使用求余操作计算数组下标。当数组的长度$n$为2的幂次方时，$hashcode\%n==(n-1) \& hashcode$，并且采用$\&$运算的效率更高(因为计算机本质上就是进行0，1的运算),这也解释了为什么数组的长度长度为2的幂次方。 举个例子，假设$hashcode==17，n==2$，$hashcode\%n==17 \% 2 == 1 $，$(n-1) \& hashcode=(2-1)\&17==(00001)\&(10001)==00001==1$。 - 为什么数组的长度是2的幂次方？ - 1.当数组的长度$n$为2的幂次方时，$hashcode\%n==(n-1) \& hashcode$。 - 2.扩容、使计算得到的数组下标分布更加的均匀，减少哈希碰撞； - 扩容只需左移即可； - 关于分布均匀的话，假如二进制是100000这样数字，无论你hash多么分布，始终得到的还是这个结果，2次幂减1保证了只要hash够均匀分布，这个下标就是均匀的，和计算时移16位相呼应。 **保证 & 中的二进制位全为 1**，才能最大限度的利用 hash 值，并更好的散列，只有全是1 ，才能有更多的散列结果;[参考](https://blog.csdn.net/q5706503/article/details/85114159) - JDK1.8之后，当链表长度大于阈值（默认为8）时，将链表转换为红黑树，以减少搜索时间（遍历红黑树的时间复杂度为O（logn)，而遍历链表的时间复杂度就是O（n））。（将链表转换为红黑树前会判断，如果当前数组长度小于64，会选择先进行数组扩容（`resize()`），而不是转换为红黑树） - 数组长度默认是16 - 为什么阈值设为8？ 与泊松分布有关 - 为什么扩容因子是0.75 -->数组更长了，哈希碰撞也会更少。数组长度与碰撞次数是服从泊松分布的，发现在0.75处碰撞的几率最小 - hashmap在1.8的时候为什么要采用尾插法（**同一位置上新元素总会被放在链表的尾部位置**） - 1、JDK 1.7 采用头插法（**同一位置上新元素总会被放在链表的头部位置**）来添加链表元素，存在**链表成环**的问题，1.8 中做了优化，采用尾插法来添加链表元素 - 2、HashMap 不管在哪个版本都不是线程安全的，出了并发问题不要怪 HashMap，从自己身上找原因 - 尾插法[参考](https://juejin.cn/post/6844904180465795079) - HashMap本就不是面向多线程的,那么1.8中尾插法避免resize死循环的说法有何意义? - 保证程序的可执行 虽然本身不是面向并发的，但是难免会有人这样用，如果出了问题，尾插法可以保证程序正常执行，只是其中的数据会有异常，头插就整个都卡死在环形列表里了 - transient修饰属性后，该属性将不会被序列化 - 链地址法，探测法 - 链地址法：就是数组加链表的结构：由Node节点组成链表之后，HashMap定义了一个Node数组，这个数组记录了每个链表的第一个节点。 [参考](https://www.cnblogs.com/aobing/p/12014271.html) **hashmap扩容分为两步** - **扩容：创建一个新的Entry空数组，长度是原数组的2倍。** - **ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。** > 为什么要重新Hash呢，不直接复制过去呢？ > **因为长度扩大以后，Hash的规则也随之改变。** > Hash的公式---> index = HashCode（Key） & （Length - 1） > 原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了,之前的所有数据的hash值得到的位置都需要变化。 Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。 --- ### `ConcurrentHashMap`和`Hashtable`的区别 主要区别：线程安全的实现方式不同 - `ConcurrentHashMap`使用分段锁，即将数组分割成多个部分，每个部分使用一个锁 - `Hashtable`使用全局锁，即整个数组只使用一把锁，多线程访问时效率比较底下。 ### ConcurrentHashMap成员变量使用volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用CAS操作和synchronized结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。 如下图，线程A锁住A节点所在链表，线程B锁住B节点所在链表，操作互不干涉。 ------------------------------------------------ 版权声明：本文为CSDN博主「腾讯NEXT学位」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/weixin_35523284/article/details/112096437