hashing的一些正确姿势
发布网友
发布时间：12小时前
共1个回答
热心网友
时间：2024-10-21 09:27
整数的hash函数研究可为后续应用奠定基础。首先定义hash函数及性质：给定[公式]范围内的整数，通过一个hash函数[公式]映射至[公式]范围内的数。令[公式]表示一个hash family，随机从[公式]中选取[公式]。定义hash函数性质如下：Universal性质保证任意两个不同的元素[公式]和[公式]映射后发生碰撞的概率较小；Strongly Universal性质在Universal基础上添加更多*，碰撞概率更小；d-universal性质是对Universal性质的推广。
一个喜爱的hash函数为[公式]，其中模数[公式]是[公式]内的随机质数。虽然在实践中不常用，但其形式简单，易于证明良好性质，如证明其为[公式]-universal的。
在实践选择[公式]固定为特定值如1000000007或998244353，违反了随机选择原则，可能导致特定adversary针对，影响算法表现。建议随机选择“本命素数”预先背下，模拟随机效果。
一个strongly universal的hash函数示例为[公式]，其中[公式]为[公式]的素数，hash family[公式]。
字符串的hashing
字符串与整数序列相似，因此可讨论字符串。对于长度为[公式]的字符串[公式]，映射至整数：[公式]。采用[公式]进制而非[公式]进制区分不同长度字符串。直接使用整数hash函数，例如[公式][公式]，其中模数[公式]是[公式]内的随机质数。映射整数较大但可应用前文证明的结论。BKDRHash函数定义为[公式]，其中选择进制31为素数，模数[公式]加速计算。BKDRHash在实践中仍受欢迎。
类似hash函数[公式][公式]，其中[公式]为随机整数，[公式]为任意大小为[公式]的素数。证明利用有限域[公式]上多项式根数*，碰撞概率不超过[公式]。
集合的hashing
计算multiset[公式]的hash值，其中[公式]。通过哈希表存储multiset，对每个桶排序后使用字符串hash函数处理，实现multiset到序列的映射。使用unordered_set等数据结构可实现此过程。
树的hashing
基于排序求最小表示的树hashing算法修改，实现简单且复杂度为[公式]。使用多层hash函数保证不同高度子树独立性，总复杂度同样为[公式]。错误率分析显示算法正确性较高，即使对于排序算法也需考虑高度不同情况。更简单方法是对点定义多元多项式[公式][公式]计算。
图的hashing
图同构问题复杂度未知，最佳算法复杂度为quasi-polynomial。对图hash难以提供有效方法。文献中提及的hash函数面临挑战，难以区分复杂图结构。建议民科们关注图同构问题，其具有影响力且算法设计相对容易，证明算法正确性更具挑战性。
