如何给哈希集设计哈希算法
概念解释
什么是哈希算法
哈希函数算法也叫 数据摘要算法 ，对一串数据进行各种计算，最终得到一个新的数据，它 能代表原始的那串数据 ，但是无法还原成原始数据。哈希函数算法按照用途分为：
- 数据正确性校验 用的哈希函数算法
- 密码学安全 用的哈希函数算法
- 数据结构 管理数据时使用的简单哈希算法
什么叫「哈希碰撞」
不同的原始数据生成出相同的哈希值的情况叫「哈希碰撞」。一个哈希算法的设计需要尽可能避免其发生哈希碰撞。哈希碰撞率高的哈希算法是设计失败的哈希算法。
什么叫「密码学安全」
符合密码学安全的哈希算法不仅需要有极低的哈希碰撞率，而且必须确保攻击者难以通过一个已有的哈希值逆推出原始数据。
什么叫「数据正确性校验」
在传输数据的过程中，数据里附带了一个原始数据的哈希值。接收方在接收到数据后，对数据使用相同的哈希算法重新计算一遍，看看算出来的哈希值是否和发过来的哈希值相同，如果是，那就认定数据的传输是无误的。
常见哈希函数算法（以下这些不使用于哈希集等数据结构用途）
- 循环校验算法 CRC（通常不用于密码学范畴，主要用于进行数据正确性校验）
- CRC16（用于网络传输层验证网络数据包是否被正确传输）
- CRC32（除了众所周知的
CRC32 外，还有其它的版本比如 CRC32b、CRC32c 等）
- Message Digest（如 MD4、MD5。主要用于密码学范畴）
- MD4（由于安全问题已被弃用。例：Windows XP 的用户开机密码以
MD4 形式存储于其中的 sam 文件中，而不少「开机密码破解软件」可以无需联网直接破解出 密码原文 ）
- MD5（由于 使用广泛 ，不少人制作了 「MD5碰撞库」，这导致
MD5 在某些场合具有 安全风险 ，比如对 用户密码的哈希处理 ）
- 因此在使用
MD5 处理用户密码时，通常需要再对用户密码 加盐处理 。
- SHA 系列（安全哈希算法）
- SHA1（多年前谷歌公司花费一年的时间破解了它，于是说它有安全问题。因此被弃用）
- SHA2（因为上述原因导致大家不爱用
SHA1，现在的人喜欢使用它替代旧的 SHA1 的使用场景）。现在通常所说的「SHA256」「SHA512」其实是「SHA2-256」「SHA2-512」。
- SHA3 （2015 年诞生。由于出现了理论上可破解 MD5 和 SHA2 的说法，SHA3 应运而生。）
- BLAKE
- Argon
以上这些哈希算法不适合被用到诸如哈希集、哈希表等数据结构上。不适合的原因是因为这些算法的设计目标是 极尽最大可能可能减少哈希碰撞 ，从而符合 密码学安全 的要求或者 数据准确性校验时避免发生哈希碰撞 ，但是并不太在乎计算的速度和算出来的哈希值的长度。 给哈希集等类似的数据结构使用的快速哈希函数的设计 应当尽可能简化，并且放宽对哈希碰撞概率的要求。
什么是哈希表
哈希表、哈希集是一种数据结构，其使用「桶」作为数组单元，然后管理「桶数组」。所谓「桶」，是一种存储数据的容器，我们对它的要求是它要能存储多个数据。因此，「桶」可以是数组，也可以是链表。通常情况下的桶都被设计为链表形式。
哈希表常被用做 字典 ，也就是一个键（Key）对应一个值（Value），最典型的例子是某 学生管理系统 可以使用学生的「学号」作为 Key，而查询出来的值（Value）则是该学生的姓名和身份信息。使用哈希表查询数据的过程远远快于数组遍历的方式。
哈希集常被用做 集合 。不同于数组等其它数据结构，哈希集的内容不会重复。哈希集被用于交并补集合运算，并且能快速判断其是否包含有某个数据。同样，哈希集查询数据的速度远高于数组遍历。
常见的哈希表实现方法
在从哈希表里使用一个 Key 查询数据时，这个 Key 的哈希值被计算出来。这个哈希值被当作数组的 索引 来直接定位「桶」。读到这里，大家肯定会想到 Key 的哈希值应该是一串看似毫无规则的、位数很多、数值明显大于「桶数组」大小的值，事实上就是如此，绝大多数情况下哈希值会超出数组下标。此时可以使用各种方式缩短哈希值的长度来使其不超出数组长度，一个典型的做法是强制使桶数组长度符合 2 的 N 次方大小（实际需要的桶没那么多时则插入空桶，有时根据可能存储的数据的大致数量来预分配桶数组的大小），然后对哈希值做 位运算 ，只取其低位来作为数组 index，就不会超出桶数组下标了，然后使用这个 index 直接定位桶。这个桶里就有我们需要查询的数据，遍历匹配其元素内容即可得到我们需要的数据；或者我们如果要插入数据到哈希集/哈希表，则也是插入到这个桶里。
至此，一个最基本的哈希表/哈希集就实现了。
给哈希表设计适合其使用的哈希函数
数据结构中的哈希表需要的哈希函数 并不需要很讲究密码学安全 ，但是需要它足够简单，足够快，并且尽可能还是要减少碰撞概率的，但是 并不讲究极端的哈希碰撞避免概率 。
使用「学校班主任管理一个班级」的虚拟场景具体描述什么是哈希算法
在 某学校 的场景里，班主任负责管理班级学生。这里面的 班级 相当于 数据的容器（桶） ， 班主任 相当于 负责管理容器数据的软件 ，而 学生 则相当于 容器里的数据 。由于某种原因，比如班级里大量的人重名了，有很多个「李华」和「张三」，为了能根据学生的身体、面部特征等区分每一个人 （为了给一串串不同长度不同内容的数据进行「摘要」） ，班主任开始对学生 起外号 。这个起外号的过程就叫哈希计算。
首先我们假设每个同学的体型、外貌、生活习性等都具有非常鲜明的差异（以便于确保班主任起的外号不容易重复），那我先举三个例子：
- 比如某同学每个月才洗一次澡，还每天都喷很多廉价香水，班主任计算了一下，觉得可以根据他的气味给他起外号叫「深海鱼人」。
- 比如某同学有个习惯，无论什么场合，只要看见有人错误使用「的地得」这三个助词，他都会将其指出来。班主任给他起外号叫「的地得警察」。
- 比如某同学喜欢二次元，上衣印了个长着一双难以区分其为兔耳朵还是驴耳朵的二次元可爱女孩子的图画，下身印着「RHODES ISLAND」，班主任给他起外号叫「未成年博士」。
然后要给学生分班，此时，班主任按外号的字数来分班，比如「三个字的」「四个字的」「五个字的」。
班主任给在计算机上，给每人创建了一个文件夹，并对每个人拍了张照存入文件夹，然后文件夹的名字就是这个学生的外号。在此时，班主任已经完成了他对数据的摘要处理，并完成了哈希集的构建。
尝试设计哈希函数
设计1
size_t Hash(const char* data, size_t data_size)
{
size_t ret = 0;
for (size_t i = 0; i < data_size; i++)
{
ret += data[i];
}
return ret;
}
这应该是最简单的哈希函数了。全部数据加起来求和。缺点很明显：data 里的字符顺序的变化不会改变哈希值，这就导致了极高的碰撞率。它无法区分单词 reverse 和 reserve，会生成相同的哈希值。因此我们需要让哈希值的计算 考虑数据的顺序 。
设计2
size_t Hash(const char* data, size_t data_size)
{
size_t ret = 0;
for (size_t i = 0; i < data_size; i++)
{
ret += (size_t)data[i] << ((i % sizeof(size_t)) * 8);
}
return ret;
}
我们把数据左移了一下再加入到哈希值里，就能体现出数据的顺序性了。但是这样的哈希算法依然有个缺陷：它只能一次性接受数据，然后进行计算。它不能对很长的数据进行分段的计算，因此需要改进。
设计3
size_t Hash(size_t old_hash, const char* data, size_t data_size)
{
size_t ret = old_hash;
for (size_t i = 0; i < data_size; i++)
{
ret <<= 4;
ret += (size_t)data[i];
}
return ret;
}
此处的改动是先读取旧哈希值拿来计算，每次计算时使哈希值左移 4，这样的话，先来的数据就会被移动到高位，然后再加上后来的数据。但是这个算法 还是有问题 ：对于两个数据，如果第二个数据足够长且尾部经过了特殊的处理比如它的尾部和第一个数据相同，那么它就会 把所有的先来的数据都挤掉，导致哈希碰撞 。
设计4
size_t Hash(size_t old_hash, const char* data, size_t data_size)
{
size_t ret = old_hash;
for (size_t i = 0; i < data_size; i++)
{
size_t high = ret >> (sizeof(size_t) * 8 - 4);
ret <<= 4;
ret |= high; // 此处相当于执行了一个 ROL(4)
ret += (size_t)data[i];
}
return ret;
}
使用向左滚动 4-bit 的方式保留了高位，再加上数据。这个哈希算法是一个比较理想的哈希算法， 对字符串应该是足够好用的 。
尝试针对非字符串设计哈希函数
非字符串的情况下，我们的数据可能可以不以 char 为单位进行计算。char 太短了，每次进行那么多次的计算，只为处理一个 char，这样会让你的哈希函数效率降低。
此处例举一个以 int 为单位的哈希函数：
size_t Hash(size_t old_hash, const int* data, size_t data_count)
{
size_t ret = old_hash;
for (size_t i = 0; i < data_count; i++)
{
ret = (ret << 4) | (ret >> (sizeof(size_t) * 8 - 4));
ret += (size_t)data[i];
}
return ret;
}
好像也差不多，只不过每次处理的是一个 int。
结论
给哈希表/哈希集等数据结构设计的哈希函数需要考虑到以下几个方面：
- 哈希值要保留数据的顺序性
- 哈希算法要能分块处理数据
- 哈希算法要能在计算较长数据时保留早期加入哈希计算的数据的痕迹
最主要的：哈希表/哈希集使用的哈希算法要快。因此避免以下行为：
- 无意义的乘法和无法解释的魔法数字的使用
- 任何除法运算
- 对任意数据仅使用适用于字符串哈希计算的哈希算法
|Archiver|小黑屋|技术宅的结界
( 滇ICP备16008837号 )|网站地图
发表于 2024-2-19 18:25:22
发表于 2024-2-19 20:39:54
发表于 2024-2-20 02:26:28
