HashMap相关问题

HashMap实现原理

HashMap是以键值对的形式存储数据，内部是通过数组+链表结构实现，在1.7之后的版本，链表结构可以升级为红黑树，提高查询效率

• key和value都支持为null；key为null时hash值是0，取模后也是0 ，也是就是会存放在数组第一个链表中

HashMap的put、get、remove过程

put过程：

• 先根据key值计算Hash值

• 再根据hash值与数组长度进行取模运算，计算出要落在数组哪个位置上

• 接着判断数组是否为空，为空的话对数组进行初始化，默认数组容量是16

• 然后判断该数组位置是否已经存在元素，如果不存在则直接创建Node结点放入数组对应位置

• 如果存在则继续判断是否是红黑树，如果是红黑树则在红黑树中创建或者更新Node结点

• 如果是链表结构，则先插入元素，然后判断链表中元素个数是否已经到达阈值8个，如果到达了，并且数组容量大于64个，则将当前链表升级为红黑树结构，如果不足64则进行一次扩容

  • 在扩容时，红黑树会进行拆分，拆分过程中会判断红黑树中结点是否少于阈值6个，如果是的话变回链表结构

  • remove元素时判断根节点和左右子节点是否为null来决定是否转回链表结构，而没有根据阈值6来判断

• 最后插入完元素后，会判断当前元素总的个数是否达到阈值，默认是数组容量的3/4，如果达到了则进行扩容

  • 3/4是根据空间和时间综合判定的，如果设置过小，则扩容频繁，如果设置过大，则hash冲突概率增加，查找效率更低

get过程：

• 先通过key计算hash值，然后与数组长度取模运算确定在数组中的位置

• 然后判断数组中对应元素key值是否相同，相同则返回该结点的value值

• 接着判断是否是红黑树，如果是的话从红黑树中查找该key对应结点

• 如果是链表则遍历链表中每一个元素找到key值相同的Node结点并返回value值

remove过程：

• remove过程和查找差不多，也是先计算hash值，取模计算出数组位置，然后判断是否红黑树等等，找到元素后从原来位置删除

• 从红黑树中删除之后，会判断根节点以及其左右结点是否为空来决定要不要转回链表结构

容量转为2的n次幂

• int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;

• 现将设置的容量减1，然后不断进行右移和或运算，目的是将低位上的数都转为1(0000 1111)；最后再+1,形成(0001 0000)这种结构，结果必然是2的n次方

Hash算法和Hash冲突问题

• (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

• key可以为null

• hash值的计算：key的hash值与它的高16位右移后进行异或运算，目的是为了降低低16位相同的概率，从而减少hash碰撞

  • 这是因为跟数组长度-1进行与运算时，数组长度-1的高位基本都是0，进行与运算后结果也是0 ，如果两个数高位不同，低位相同，就会导致计算结果一致，发生hash碰撞；

  • 所以需要降低低位相同的概率，就能减少hash碰撞

• 为什么进行异或运算，而不是与运算或者或等其他运算？

  • 因为如果进行与运算，会导致结果趋向于0更多

  • 进行或运算，结果趋向于1更多

  • 只有进行异或运算，结果0和1的个数会趋于一样多，这样结果随机性就更大，hash碰撞概率就小很多

• 降低hash冲突办法：

  • 计算hash值的时候进行异或运算

  • 降低负载因子(load factor)，增加数组容量大小

计算数组中的位置

• (n - 1) & hash

• 根据Hash值和数组长度减1进行与运算；相当于对数组长度取模运算，保证取模后结果在数组长度范围内；与运算速度要比取模运算快

  • 数组容量大小是2的n次方，可以保证数组大小-1后与hash值与运算后结果在数组范围内，取代模运算，效率更高

HashMap扩容机制

• 扩容时会先判断容量是否有初始化，如果没有则先初始化为默认容量16或者传入的容量，容量最大不能超过2的30次方

• 然后判断当前容量是否超过阈值，默认是当前容量的3/4，如果超过则进行扩容，每次扩容会把容量增加到原来的2倍

• 接着会将原来数组中的数据根据hash值复制到扩容后的数组中，在拷贝数据过程中，原有链表或者红黑树会被拆分成两份，一部分会保存在原有数组位置，另一部分会存在当前数组位置加上原有数组容量大小的位置

• 根据if ((e.hash & oldCap) == 0) 判断链表中的元素是否需要移动，如果等于0则不移动，否则移动到当前数组位置加上旧数组容量大小的位置：newTab[j+oldCap]

  • 因为同一个Hash值跟数组扩容前和扩容后的大小进行取模运算后，只有两种情况，要么跟原来位置不变，要么比原来位置多原来数组容量大小

• 扩容导致死循环问题

  • 因为在1.7版本中，HashMap扩容时采用的是头插法，也就是拷贝旧数组中元素到新数组中时，新元素是插入到链表头部的，当并发时可能出现多个线程同时在扩容，当其中一个线程正在将元素A移动到新的位置时，A的下一个元素时B，另一个线程正在将B插入A的前面，但是A指向B的链接还没有断开，B就指向了A，这就会导致A和B互相链接着形成环状，当调用get方法遍历链表时就可能会卡死在这里永远无法退出循环

HashMap如何保证线程安全

HashTable

• 底层实现也是数组+链表

• 使用了Synchronized同步锁，会锁住整个HashTable对象，效率低

• 线程安全，key和value都不能为null

ConcurrentHashMap

• 线程安全

• 将整个Map分成N个段Segment保存在数组中，每个Segment又可以看做一个小型的HashMap，内部由数据+链表结构实现，Segment继承自可重入锁；

• 锁分段技术，每一个Segment都是一个可重入锁，每次只会锁住该段中的元素，不会影响到其他段中元素的读写

• 扩容采用段内扩容，每次扩容只针对当前Segment，不会对整个表扩容

• 有些操作需要锁定整个表，比如获取所有元素个数size，或者判断某个元素是否在表中containsValue操作

  • 在计算size时会先尝试几次不加锁统计，当发现算了几次结果都一样时，则任务没有新增或者删除，如果有变化则强制将所有Segment加锁后再统计

• jdk1.8后的变化：

  • 整体结构改成跟HashMap1.8版本差不多，也就是数据+链表+红黑树结构

• 舍弃了Segment，改为通过synchronized锁住数组中的元素，也就每个链表的头元素，以及CAS操作保证线程安全性

• 扩容时为了保证线程安全，移动元素之前会修改链表头节点的hash值成-1，其他线程检测到正在扩容则会先协助扩容移动元素

• 获取size元素个数时，直接获取每个数组元素链表下元素个数并求和，不需要加锁，使用了单独的对象保存每个链表下元素个数，当个数发生变化时使用CAS保证线程安全

• 参考地址：https://blog.csdn.net/qq_26542493/article/details/105651338

HashMap是否有序，如何保证有序？

无序的，LinkedHashMap可以保证有序

为什么容量必须是2的N次方

• 很多地方用到二进制运算，比如计算hash值，计算数组中的位置，扩容等；使用2的N次方转成二进制就是一个1，其他都是0，方便二进制运算

参考链接：https://blog.csdn.net/qq_26542493/article/details/105482732