数据结构基础：哈希
哈希涉及将哈希算法应用于数据项（称为哈希键）以创建哈希值。哈希算法将很大范围的值（例如所有可能的字符串或所有可能的文件）映射到较小的值集（例如 128 位数字）。
哈希有两个主要应用。哈希值可用于加快数据检索，也可用于检查数据的有效性。
当我们要从文件中检索一条记录时，搜索文件以查找所需记录所需的时间会随着记录数量的变化而变化。如果我们可以为记录的键生成一个哈希，我们可以使用该哈希值作为记录的“地址”并直接移动到它；这花费的时间与文件中的记录数量无关。
可以使用哈希来检查数据的有效性。这可以用于检查文件是否传输正确，以及检查文件是否在我将其上传到某个地方到您将其下载之间的某个时间点被故意篡改。如果我发布了文件和从文件中生成的哈希值，您可以从收到的文件中生成一个哈希值并比较这些哈希值。如果哈希算法是一个好的密码哈希，那么事故或恶意行为极不可能即使稍微修改了文件，但它仍然会产生相同的哈希值。
为了构建一组哈希值，我们使用哈希算法来创建哈希表。看下面的图表，通过应用哈希算法，每个数据项（或哈希键）都有一个哈希值。
现在，如果我们决定搜索
| 哈希键 | 哈希函数 | 哈希值 |
|---|---|---|
| "Sam Doe" | 应用哈希函数 | 哈希值 = 3 |
我们可以搜索哈希表以查找哈希值 3，如果我们找到了它，我们就知道 Sam Doe 是存在的。
但是，如果我们搜索不存在的项怎么办？看看这个例子
| 哈希键 | 哈希函数 | 哈希值 |
|---|---|---|
| "John Thompson" | 应用哈希函数 | 哈希值 = 9 |
现在我们可以搜索哈希表，可以看到哈希值 = 9 没有条目，因此该数据不存在，我们不必搜索所有数据来证明这一点。
哈希应该是可重复的，这意味着每次我们将其应用于相同数据时，我们都应该得到相同的哈希值。这要求我们创建一个哈希算法或函数
看看这个（如果你忘记了 MOD 的工作原理，去查看！）
hashKey MOD 6
如果我们将它应用于以下哈希键列表
| 哈希键 | 哈希算法 | 哈希值 |
|---|---|---|
| 12345 | 12345 MOD 6 | 3 |
| 67564 | 67564 MOD 6 | 4 |
| 34237 | 34237 MOD 6 | 1 |
| 23423 | 23423 MOD 6 | 5 |
| 00332 | 00332 MOD 6 | 2 |
一旦我们计算出哈希值，我们就可以开始构建哈希表，注意因为我们使用的是 MOD 6，所以我们有 6 个不同的哈希值
| 哈希值 | 哈希键 |
|---|---|
| 0 | |
| 1 | 34237 |
| 2 | 00332 |
| 3 | 12345 |
| 4 | 67564 |
| 5 | 23423 |
现在，如果你被问到哈希键23448是否是给定数据的成员，你会做以下操作
- 使用哈希键，应用哈希算法并计算哈希值
- 在哈希表中检查哈希值
- 如果它存在，你找到了数据，如果它不存在，数据就不存在
23448 MOD 6 = 0 Nothing attached to 0 in the hashing table Therefore 23448 isn't stored
|
练习：哈希表 为以下哈希键和哈希算法创建一个哈希表 HashKey MOD 8
答案
为以下哈希键和哈希算法创建一个哈希表 (HashKey + 12) MOD 8
答案
你可以在以下哈希表中找到哈希键 3245 吗？该哈希表基于哈希算法：((HashKey + 67)) MOD 8
答案 不。因为 (3245 + 67) MOD 8 = 0，哈希表中没有数据存储在该键下 描述以下内容
答案 The hashing key is the raw data in which to be hashed. 哈希算法是执行函数将哈希键转换为哈希值的算法。哈希值是将哈希键传递给哈希算法后产生的结果。 描述如何创建哈希表 答案 哈希表由所有有序的哈希值及其对应的信息组成。
解释如何使用哈希值来检查是否存在某项内容 答案 哈希值用于检查是否存在某项内容，因为可以重新哈希数据，然后查询哈希表，这比搜索文本更有用，因为计算机在搜索数字方面比搜索文本更快。
|
| 完美哈希 | 冲突键 |
|---|---|
 |
 |
你可能已经注意到了这一点，当我们用完唯一的哈希值时会发生什么？当两个哈希键给出相同的哈希值时会发生什么？看看以下示例的最后一行，该示例基于哈希算法 HashKey MOD 6
| 哈希键 | 哈希算法 | 哈希值 |
|---|---|---|
| 12345 | 12345 MOD 6 | 3 |
| 67564 | 67564 MOD 6 | 4 |
| 34237 | 34237 MOD 6 | 1 |
| 23423 | 23423 MOD 6 | 5 |
| 00332 | 00332 MOD 6 | 2 |
| 00338 | 00338 MOD 6 | 2 !!! 冲突！ |
当两个哈希键导致相同的哈希值时，这称为冲突。这会导致问题，因为我们不能再快速找到数据是否在我们的哈希表中，因为另一个数据可能具有相同的哈希值。解决这个问题的方法有很多，我们将介绍两种
当两个哈希键创建相同的哈希值时，我们将冲突键放在下一个空闲的哈希值中。
当两个哈希键产生相同的哈希值时，我们会利用链表将冲突的键存储在同一个位置，并将所有匹配该哈希值的键连接起来。
MD5
MD5("The quick brown fox jumps over the lazy dog")
= 9e107d9d372bb6826bd81d3542a419d6
即使消息中出现微小的变化，也会（以极高的概率）导致哈希值发生很大变化。
MD5("The quick brown fox jumps over the lazy dog.")
= e4d909c290d0fb1ca068ffaddf22cbd0
正如你在学习数据库时所了解的那样，我们经常需要使用主键在表中搜索数据。主键是存储在每个记录中的唯一值。它通常是一个数字，但如果没有数字主键，我们仍然需要能够搜索数据。例如，下表显示了某个班级中一些学生的信息，我们将根据每个学生的姓名进行搜索。
| 姓名 | 出生日期 | 头发颜色 |
|---|---|---|
| John Smith | 19072000 | 棕色 |
| Lisa Smith | 07031999 | 红色 |
| Sam Doe | 12121954 | 金色 |
| Sandra Dee | 01012006 | 金色 |
| Aubrey Carringtoe | 12101967 | 金色 |
| Aubrey Carring | 22102000 | 黑色 |
| Aubrey Carrington | 22102000 | 金色 |
| Aubrey Carringy | 31092007 | 无 |
| Aubrey Carringtone | 04042004 | 金色 |
| ... | ... | ... |
根据每个学生的姓名进行搜索可能需要一些时间，因为我们可能需要搜索
Anthony Tarkovsky
这可能需要检查数千条不同的记录和 17 个字符才能确定我们是否找到了它们。如果数据量更大，可能需要更长的时间。我们需要一种快速的方法来为每个数据项应用索引键，以便我们能够快速搜索数据。将索引键附加到每个数据项（或哈希键）被称为**哈希**，索引值被称为**哈希值**。这个哈希值不是随机的，而是取决于要进行哈希处理的哈希键，因此每次使用相同的哈希算法对相同数据进行哈希处理时，都会得到相同的哈希值。
例如，如果我们将每个姓名（或哈希键）进行哈希处理，并且我们发现 Anthony Tarkovsky 的哈希值为 12，那么我们只需要检查哈希表，看看 12 是否存在，而不是在姓名字段中搜索所有 17 个字符。
由于你无法从哈希值推断出原始值，因此哈希也被用来存储密码。安全措施不完善的公司将密码保存在文本字段中，这使得密码更容易被盗。存储密码的更安全方法如下：更聪明的公司会这样做。
- 用户输入密码“thisisreallym3”。
- 数据库系统将密码哈希为“fjj34N6*34£sdf234&”并将其存储在数据库中。
现在，当客户返回网站并输入密码时，系统会执行以下操作：
- 用户输入密码。
- 输入的密码会立即进行哈希处理，并将哈希值与数据库中的值进行比较。
- 如果值相同，则允许用户登录；如果值不同，则拒绝用户登录。
这有利于处理以下情况：
- 脚本小子入侵系统并窃取用户数据库。
- 他们获得的用户详细信息中只包含密码的哈希值。
- 哈希密码对于在没有哈希算法的情况下找出真实密码毫无用处（即使有哈希算法，它也很少有用！）。
- 即使用户在所有网站都使用相同的密码，他们在这个网站和其他网站上的帐户也不会受到威胁。
哈希算法应该做到以下几点：
- 冲突较少。
- 产生范围广泛的哈希值。
- 对于相同的输入，始终产生相同的哈希输出。