数据结构-散列表

散列思想

编程语言中常见的三大数据结构：标量、序列、映射

映射如 HashMap、HashTable 等，是一种散列表数据结构

散列表基于数组的随机访问特性，本质上散列表是数组的一种扩展

散列思想举例：

10 名学生参加比赛，编号分为 0 到 9，如何将学生信息存储到合适的数据结构？

​ 使用一个长度为 10 的数组，使用选手编号作为下标进行存储，这样取出存储信息的复杂度为 O(1)

如果每位学生的编号是年级号 + 班级号 + 选手编号，该如何存储呢？

​ 截取编号中的选手编号部分，作为数组下标进行存储

上述示例中，运用了散列思想，其中选手编号叫做键，截取的方法叫做散列函数，通过散列函数得到的值叫做散列值或哈希值，是根据散列值来确定数组下标的

散列函数

散列函数是一个将键值转换成散列值的函数，散列函数在散列表中起到非常关键的作用

散列函数得到的值，用作散列表底层数组的下标，因此散列函数的基本设计要求是

1. 散列函数计算得到的散列值需要是一个非负整数
2. 如果 x1 = x2, 那 f(x1) = f(x2)
3. 如果 x1 != x2，那 f(x1) != f(x2)

对于第三点，是我们的理想情况，在真实实现下，要想找到一个不同的 key 对应的散列值不一样的散列函数，几乎是不可能的。著名的 MD5、SHA、CRC等哈希算法，也无法避免这种情况，这种情况被称为散列冲突

而且，数组的存储空间是有限的，这样会加大散列冲突的概率

散列冲突

常见的解决散列冲突的算法有两类，开放寻址和拉链

开发寻址法

开发寻址法的核心思想是，如果出现了散列冲突，意味着两个不同键值要存到同一个下标，我们可以重新探测一个空闲位置进行存放

比较简单的探测方法-线性探测

当发生冲突时，我们可以从散列值的位置开始，依次向后查找，看是否有空闲位置，知道找到为止

如图，当 key 经过散列，得到下标 2，但是该位置已经有数据且键值不等于 key，就依次向后查找，遍历到尾部没有找到空闲位置就从头开始，最终在下标 1 处找到了空位

在查找元素时，先得到散列值，然后和位置上的数据进行比较，key 不相等就向后查找，直到找到，如果直到找到一个空闲位置还没有找到，则说明元素不存在

存在的问题：

​ 在删除元素时，当我们查找到元素存储位置时，删除该位置元素，那么发生哈希冲突时，该位置后面的元素将无法被查找到，导致算法失效

解决的方法：

​ 将要删除的位置进行特殊标记，当线性探测时，遇到特殊标记继续探测下去

除了线性探测外，还有两种比较经典的探测方法，二次探测和双重散列

二次探测和线性探测类似，但步长是 1 的平方、2 的平方、3 的平方等等

双重散列是使用多个散列函数，发生冲突时就使用下一个函数进行散列

不管采用哪种探测方法，当空闲位置不多时，冲突的概率将大大提高，所以需要保证散列表中有一定比例的空闲位置。用装载因子来表示空位的多少

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

散列表的性能会随着装载因子增大、冲突增多而下降

当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因

拉链法

拉链法是一种更为常见的散列冲突解决办法，数组中存储链表结构，当产生冲突时，直接将散列值相同的元素存到对应的链表中

链表插入的时间复杂度是 O(1)，所以拉链法插入的时间复杂度也是 O(1)

当查找、删除一个元素时，先通过散列函数计算出数组下标，再遍历链表查找或删除，这两个操作的时间复杂度和链表长度 k 成正比，也就是 O(k)，对于分布比较均匀的散列函数，k = 数据个数 / 散列表数组长度

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表

Java 中 HashMap 使用了拉链法配合红黑树解决哈希冲突

使用场景

如何设计一个企业级的散列表?

1. 设计合适的散列函数，不能太复杂，且散列值需要均匀分布

2. 选择合适的散列冲突解决办法

3. 定义合适的装载因子阈值，根据需要动态扩容或缩容

   对于扩容时的数据搬移问题，可以不一次性搬完，而且每次新数据插入时，搬移部分老数据，可以将复杂度摊还到 O(1)

1. Java HashMap

   HashMap 默认的初始大小是 16，可以通过修改默认初始大小，减少动态扩容的次数

   最大装载因子默认是 0.75，当 HashMap 中元素个数超过0.75 * 散列表的容量的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小

   HashMap 底层采用拉链法来解决冲突。当出现拉链过长时，会严重影响 HashMap 的性能。在 JDK1.8 版本中，为了对 HashMap 做进一步优化，引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树，以提高增删改查的性能

   HashMap 的散列函数（capicity 表示散列表的大小）

   int hash(Object key) {
       int h = key.hashCode()；
       return (h ^ (h >>> 16)) & (capicity -1); 
   }
   

   hashCode() 函数获得对象的 hash code，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;
   }
   

2. Java LinkedHashMap

   散列表中数据是经过散列函数打乱之后无规律存储的，所以普通的 HashMap 是无序的

   LinkedHashMap 通过散列表和链表组合实现按增加顺序和访问顺序遍历元素

   // 10 是初始大小，0.75 是装载因子，true 是表示按照访问时间排序
   HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
   m.put(3, 33);
   m.put(1, 11);
   m.put(2, 22);
   
   m.put(3, 26);
   m.get(2);
   
   for (Map.Entry e : m.entrySet()) {
     System.out.println(e.getKey());
   }
   

   LinkedHashMap 采用的 hash 算法和 HashMap 相同，但是扩展了 Entry（结点，JDK8 中叫 Node）

   结点中增加了前后两个指针，构成一个双向链表，用来维护顺序

   

   如果设置了按访问顺序排序，在访问元素时会对链表元素顺序进行调整

3. LRU 缓存

   通过链表实现 LRU 缓存淘汰算法的原理：

   维护一个按照访问时间排序的链表，越靠近头部是越早使用的。当缓存空间不够时，删除头部结点

   需要缓存某个数据时，先查找是否存在，不存在则追加到尾部，存在则移动到尾部

   仅仅使用链表实现 LRU 缓存的复杂度为 O(n)，配合散列表可降低时间复杂度为 O(1)

   

   使用双向链表存储数据，每个结点有前驱指针 prev、后继指针 next，用于连接数据，还有 hnext 指针，用来在散列表中使用拉链法解决冲突

   通过散列表快速查找特性，查找数据的复杂度为 O(1)，又双向链表删除结点只需要 O(1) 的时间复杂度，所以删除元素的复杂度也是 O(1)