数据结构与算法之美 | 学习笔记15 —— 散列表设计

对于简单的散列表，网络攻击者可能会精心构造数据，使所有数据经过散列函数后到同一个槽中，当我们用链表法解决冲突时，这时散列表就会退化为链表，查询复杂度由$O(1)$退化到$O(n)$。导致查询时消耗大量CPU或线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。

一、设计散列函数

1. 散列函数不能过于复杂，不然会消耗很多计算时间；
2. 散列函数生成的值尽量随机分布；

1. 装载因子

对于动态的散列表，因为无法预知要加入数据的个数，随着数据慢慢增加，装载因子会慢慢变大，这时我们可以利用动态扩容的方法。当装载因子过大时，申请一个更大的散列表，再通过散列函数重新计算每个数据存储的位置，进行“搬移”。

对于支持动态扩容的散列表，参照数组的扩容，均摊时间复杂度为O(1)。
同时，如果数据删除过多，空闲空间越来越多时，也可以启用动态收缩。

2. 扩容效率

对于上面一次性扩容的情况，扩容操作时插入数据会变得很慢，所以，为了解决一次性扩容耗时过多的问题，在业务中将扩容操作分批完成，新老散列表同时存在。当查找时，先在新表中查找，再去老表中查找。这种情况下，任何时候插入一个数据的时间复杂度都是O(1)。

二、冲突解决方法选择

1. 开放寻址法

开放寻址法中数据都存在数组中，不额外占用空间，可以有效利用CPU缓存加快查询速度，并且序列化比较简单。但是，相比于链表法，冲突的代价更高，因此装载因子不能太大。
当数据量小，装载因子小时，适合用开放寻址法。Java中的ThreadLocalMap用的就是这种方法。

2. 链表法

链表法适合存储大对象、大数据量的散列表，在结构上更加灵活，支持更多的优化策略。
链表法对大装载因子的容忍度更高，因此对内存的利用率更高。但因为要存指针，对于比较小的对象的存储，相对来说比较消耗内存。同时，链表中结点的地址零散不连续，对CPU缓存是不友好的。
可以对链表法稍加改造，将其中的链表改造为跳表、红黑树等更高效的动态数据结构，使极端情况下退化的散列表查找时间为$O(nlogn)$，有效避免前面说的散列碰撞攻击。

三、Java中的HashMap

初始大小
默认初始大小为16，可更改。
装载因子和动态扩容
最大装载因子默认为0.75，当HashMap中元素个数超过0.75*capacity(散列表的容量)时，启动扩容为两倍大小。
散列冲突解决方法
底层用链表法解决，当链表长度超过8（可更改）时，链表会转换为红黑树，少于8个时，再转化为链表。
散列函数

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}

为什么要右移16位再与本身异或呢？

1. 首先hashCode()返回值int最高是32位，如果直接拿hashCode()返回值作为下标，大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般是很难出现碰撞的。
   问题是一个40亿长度的数组，内存是放不下的。
2. 所以，用自己的高半区和低半区做异或，混合原始哈希码的高位和低位，关键是以此来加大低位的随机性。为后续计算index截取低位，保证低位的随机性。
3. 这样设计保证了对象的hashCode的32位值只要有一位发生改变，整个hash()返回值就会改变，高位的变化会反应到低位里，保证了hash值的随机性。计算出来的整型值将“具有”高位和低位的性质。

其中String类型的对象的hashcode()为：

public int hashCode() {
  int var1 = this.hash;
  if(var1 == 0 && this.value.length > 0) {
    char[] var2 = this.value;
    for(int var3 = 0; var3 < this.value.length; ++var3) {
      var1 = 31 * var1 + var2[var3];
    }
    this.hash = var1;
  }
  return var1;
}

在插入或查找的时候，计算Key被映射到桶的位置，hash()扰动函数计算的值和hash表当前的容量减一，做按位与运算。

int index = hash(key) & (capacity - 1)

为什么要减一，又为什么要按位与运算？
因为A % B = A & (B - 1)，当B是2的指数时，等式成立。
本质上是使用了「除留余数法」，保证了index的位置分布均匀。

为什么HashMap的数组长度必须是2的整次幂？
数组长度是2的整次幂时，（数组长度-1）正好相当于一个“低位掩码”，“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。
以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。“与”操作的结果就是截取了最低的四位值。也就相当于取模操作。（来自Flash）

转载：https://blog.csdn.net/abc19940309/article/details/106134605