哈希

散列表

散列表也叫哈希表，Hash表或者Hash Table。是一种Key-Value数据结构。

散列表是数组的一种扩展，由数组演化而来。利用了数组支持按照下标随机访问数据的特性。

散列表的名词：

• 键：也叫关键字。

• 散列函数：也叫哈希函数，将键转换为数组下标的映射方法。

• 散列值：也叫哈希值，散列函数得到的值。

散列表实现机制

• 散列函数将元素的键映射为下标，然后将元素数据存储在数组中对应下标的位置。

• 查找时，用散列函数，将键转换为数组下标，从对应的数组下标位置获取数据。

散列函数

散列函数设计要求：

• 计算得到的散列值是一个非负整数。

• 如果key1 == key2，那么hash(key1) == hash(key2)。

• 如果key1 != key2，那么hash(key1) != hash(key2)。

散列冲突

对于不同的key，要使计算出的散列值完全不一样几乎不可能。

无冲突的哈希函数设计困难，数组存储空间有限，都是造成散列冲突的原因。

散列冲突解决办法

常用方法有两类：

• 开放寻址法

• 链表法

开放寻址法

思想：

如果出现散列冲突，就重新探测一个空闲位置。

探测方法：

• 线性探测

  插入数据时，如果位置被占用，就从当前位置开始一次往后查找，直到有空闲位置为止。

  查找数据时，将数组中下标为散列值的元素与要查找的元素对比，如果相等则结束，如果不等则依次往后查找。

  删除数据时，将删除元素标记为deleted。

  插入、查找、删除操作的最坏时间复杂度为O(n)。

• 二次探测

  移动步长变成了二次方，如0^2, 1^2, 2^2...。

• 双重探测

  使用一组散列函数，如果第一个散列函数计算出的位置被占用，则使用下一个散列函数进行计算。

链表法

散列表的每个槽，对应一条链表。

散列值相同的元素，会被放到相同槽位的链表上。

散列表碰撞攻击

精心构造数据，使其散列到同一个槽中。如果使用链表法解决冲突，这是散列表就会退化成链表。

散列表的查询效率会急剧恶化，并且消耗大量CPU和线程资源，导致系统无法响应其它请求。

进而达到拒绝服务攻击DoS的目的。

装载因子

为了保证散列表操作效率，一般会要求散列表中有一定比例的空闲槽位。

空闲位置的多少使用装载因子来衡量：

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

装载因子越大，散列表中元素越多，空闲位置越少，散列冲突概率越大。

当装载因子过大时，可以动态扩容。

当装载因子过小时，可以动态缩容。

动态扩容

当装载因子到达阈值时，先申请新空间，但是并不搬移老的数据。

有新数据插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个值，放入新的散列表。

多次插入操作过后，老数据就完成了搬移。

查找数据时，需要先从新散列表中查找，如果没有找到，再去老的散列表中查找。