哈希表 Hash

定义

哈希表是一种数据结构，也有人称为散列表。用于存储具有与每个键相关联的键的值。此外，如果我们知道与值关联的键，则它有效地支持查找。因此，无论数据大小如何，插入和搜索都非常有效。

哈希函数

在直接访问中，带有密钥k的值存储在插槽k中。使用哈希函数，我们可以计算出每个值都指向的表（插槽）的索引。使用给定键的哈希函数计算的值称为哈希值，它表示该值映射到的表的索引。
h：哈希函数
k：应确定其哈希值的键
m：哈希表的大小（可用插槽数）。一个不接近2的精确乘方的素数是m的一个不错的选择。

实例

例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构。

哈希表的应用

用于实现数据库索引。
用于实现关联数组。
用于实现”设置”数据结构。

优点

数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间

缺点

消耗比较多的内存

哈希碰撞

如果不同的输入得到了同一个哈希值，就发生了”哈希碰撞”（collision）。

很多网络服务会使用哈希函数，产生一个 token(AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8)，标识用户的身份和权限。这个字符串就是一个哈希值。如果两个不同的用户，得到了同样的 token，就发生了哈希碰撞。服务器将把这两个用户视为同一个人，这意味着，用户 B 可以读取和更改用户 A 的信息，这无疑带来了很大的安全隐患。黑客攻击的一种方法，就是设法制造”哈希碰撞”，然后入侵系统，窃取信息。

如何防止哈希碰撞

• 防止哈希碰撞的最有效方法，就是扩大哈希值的取值空间。
• 16个二进制位的哈希值，产生碰撞的可能性是 65536 分之一。也就是说，如果有65537个用户，就一定会产生碰撞。哈希值的长度扩大到32个二进制位，碰撞的可能性就会下降到 4,294,967,296 分之一。

• 更长的哈希值意味着更大的存储空间、更多的计算，将影响性能和成本。开发者必须做出抉择，在安全与成本之间找到平衡。

  生日攻击

  哈希碰撞的概率取决于两个因素（假设哈希函数是可靠的，每个值的生成概率都相同）

• 取值空间的大小（即哈希值的长度）

• 整个生命周期中，哈希值的计算次数

这个问题在数学上早有原型，叫做”生日问题”（birthday problem）：一个班级需要有多少人，才能保证每个同学的生日都不一样？
如果至少两个同学生日相同的概率不超过5%，那么这个班只能有7个人。事实上，一个23人的班级有50%的概率，至少两个同学生日相同；50人班级有97%的概率，70人的班级则是99.9%的概率。
这意味着，如果哈希值的取值空间是365，只要计算23个哈希值，就有50%的可能产生碰撞。也就是说，哈希碰撞的可能性，远比想象的高。实际上，有一个近似的公式。

上面公式可以算出，50% 的哈希碰撞概率所需要的计算次数，N 表示哈希的取值空间。生日问题的 N 就是365，算出来是 23.9。这个公式告诉我们，哈希碰撞所需耗费的计算次数，跟取值空间的平方根是一个数量级。
这种利用哈希空间不足够大，而制造碰撞的攻击方法，就被称为生日攻击（birthday attack）。

数据导数

至少两个人生日相同的概率，可以先算出所有人生日互不相同的概率，再用 1 减去这个概率。
我们把这个问题设想成，每个人排队依次进入一个房间。第一个进入房间的人，与房间里已有的人（0人），生日都不相同的概率是365/365；第二个进入房间的人，生日独一无二的概率是364/365；第三个人是363/365，以此类推。

因此，所有人的生日都不相同的概率，就是下面的公式。
上面公式的 n 表示进入房间的人数。可以看出，进入房间的人越多，生日互不相同的概率就越小。
这个公式可以推导成下面的形式。

那么，至少有两个人生日相同的概率，就是 1 减去上面的公式。

哈希碰撞公式

根据泰勒公式，指数函数 ex 可以用多项式展开。

如果 x 是一个极小的值，那么上面的公式近似等于下面的形式。

现在把生日问题的1/365代入。

因此，生日问题的概率公式，变成下面这样。

假设 d 为取值空间（生日问题里是 365），就得到了一般化公式。

上面就是哈希碰撞概率的公式。