移位折叠散列以生成数据库中记录的索引

Question

我正在做一项作业，我被要求实现一个 shift fold 函数来散列数据库中记录的 String 类型键，并 return 确定该记录在数据库中的位置。据我了解，这意味着 sfold 函数必须生成与该记录在数据库中的位置相匹配的散列。

方法代码如下：

    public static long sfold(String s, int M) {
        int intLength = s.length() / 4;
        long sum = 0;
        for (int j = 0; j < intLength; j++) {
            char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray();
            long mult = 1;
            for (int k = 0; k < c.length; k++) {
                sum += c[k] * mult;
                mult *= 256;
            }
        }

        char c[] = s.substring(intLength * 4).toCharArray();
        long mult = 1;
        for (int k = 0; k < c.length; k++) {
            sum += c[k] * mult;
            mult *= 256;
        }
        
        return (Math.abs(sum) % M);
    }

这会生成一个介于 0 和记录数 - 1 (M-1) 之间的随机数字。问题是数字不是唯一的，可能不会生成所有可能的数字。那么如何使用它来return记录在数据库中的位置呢？

我的想法是从字符串键生成散列，获取散列数字，按该数字对记录进行排序，然后将它们插入数据库，但就像我说的那样，该方法不会产生唯一数字并且无法保证获取所有数字。

Answer 1

“缺乏唯一性”称为碰撞，有不同的解决方法。细节在维基百科中有很好的解释：https://en.wikipedia.org/wiki/Hash_table#Collision_resolution

主要有两种方法：

单独链接使用额外的存储空间 space：如果字符串散列为 table 中已有的数字，它会溢出到辅助存储空间 space。在 in-memory 数据结构中，额外的存储空间通常是链表。
Open addressing 查找未使用的 space：如果字符串散列为 table 中已有的数字，则它存储在同一个 [=46] 中的其他地方=], 根据您事先决定的策略。

你的问题很严重：

mult *= 256;

乘以 2 的幂意味着您将丢弃信息：仅在 8 个字符 mult = 0 之后您将忽略字符串的其余部分。将乘数更改为质数，例如 127，即可解决此问题。

你这里还有一个问题：

return (Math.abs(sum) % M);

Math.abs 有一个特殊情况，它不是 return 正数：Long.MIN_VALUE。解决它的一种方法是在之后取绝对值 余数：

return Math.abs(sum % M);

移位折叠散列以生成数据库中记录的索引

shift fold hashing to generate indices of records in database

java

hash

hashtable