数据结构之散列表

水深无声 2022-04-18 02:11 254阅读 0赞

# 概述 #

散列表的英文名叫“Hash Table”，所以，我们也叫它为哈希表。  
散列表利用数组支持下标随机访问数据的特性，是数组的一种扩展，由数组演化而来。

# 散列函数 #

我们需要把键值key映射为数组的下标。所以需要一个映射的函数，这个映射的函数就是散列函数。  
散列函数有三个基本要求：

1.  散列函数计算得到的散列值是一个非负整数
2.  如果 k e y 1 = k e y 2 key1=key2 key1=key2，那么 h a s h ( k e y 1 ) = h a s h ( k e y 2 ) hash(key1)=hash(key2) hash(key1)=hash(key2)
3.  如果 k e y 1 ≠ k e y 2 key1≠key2 key1̸=key2，那么 h a s h ( k e y 1 ) ≠ h a s h ( k e y 2 ) hash(key1)≠hash(key2) hash(key1)̸=hash(key2)

前两点很好理解也很容易实现。不过第三点在key值特别大且无规律情况下是很难实现的。就算是业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。

# 散列冲突的解决 #

既然散列冲突很难避免，那么就需要考虑一下解决方案。有两个常用的散列冲突解决方法：

1.  开放寻址法
2.  链表法

# 设计一个好的工业级散列表 #

要设计出一个好的工业级散列表，需要该散列表可以应对各种异常情况，避免在散列冲突的情况下性能急速下降。  
需要考虑如下几点：

1.  设计一个合适的散列函数
2.  装载因子过大时，选择合适的方式进行扩容
3.  发生散列冲突时，选择合适的冲突解决方法解决散列冲突
4.  应对散列碰撞攻击

### 设计一个合适的散列函数 ###

在选择散列函数时要考虑两点：

1.  散列函数的计算过程要短
2.  散列计算结果尽可能均匀分布

有几个常用的散列函数设计方法：数据分析法、直接寻址法、平方取中法、折叠法、随机数法。

### 用合理的方式进行扩容 ###

在装载因子过大时，我们要对散列表进行扩容，如果是一次性迁移数据，那么势必会造成某次插入的效率极低，所以应当将迁移数据工作分布在每次的插入操作时做。

### 解决散列冲突的方法 ###

对于工业级的散列表来说，因为存储的数据很有可能规律难寻，所以极有可能出现散列冲突，那么如何解决散列冲突就极为重要了。常用的散列冲突解决方法有两个：

1.  开放寻址法  
    优点：查询效率高、易于序列化  
    缺点：更浪费内存空间，在极端情况下查找时间复杂度退化为 O ( n ) O(n) O(n)  
    适合场景：数据量小、装载因子小
2.  链表法  
    优点：内存利用率高、对大装载因子的容忍度高  
    缺点：存储对象小的情况下会使内存有些浪费  
    使用场景：存储大对象、大数据量、装载因子可能会比较大

### 散列碰撞攻击 ###

散列碰撞攻击是指一些攻击者专门制造一些数据，使得所有的数据在散列之后，都被散列在同一个槽里。假设我们使用链表法解决冲突，那么就会使本来 O ( 1 ) O(1) O(1)的数据查询时间复杂度退化为 O ( n ) O(n) O(n)。在数据量巨大的情况下这是非常影响服务器性能的。  
我们可以使用链表法解决散列冲突，并将简单链表替换为其它更高效的动态数据结构，比如跳表和红黑树。这样即使出现散列冲突，在极端情况下退化为查询时间复杂度 O ( l o g n ) O(logn) O(logn)，就算是数据量很大的情况，也能够避免可怕的散列碰撞攻击。

# 散列表和链表一起使用 #

散列表的优势在于可以高效的查询、插入和删除元素。不过，由于存储的位置都是经过散列函数打乱了，所以遍历时十分不方便。因此要与链表一起使用，互补长短。