什么是散列中的折叠技术以及如何实现它？

Question

我在一个数据结构研讨会上听说我们可以将一个键分成数字组，然后进行组的加法。这确保了所有数字都贡献了哈希码。一组中的位数对应于数组的大小。

例如，我有一个机器号说 424-124-9675 ，如何使用折叠技术制作哈希函数？

原文由 Yogesh Umesh Vaity 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

根据 Tony 和 Sumeet 的回答，我对数字折叠做了更多研究，并决定实施 Robert Lafore 在他的数据结构书中解释的技术。

例如，假设您要散列 10 位机器号。如果数组大小为 1,000 ，您会将 10 位数分成三组三位数和一组一位数。在有问题的示例中，机器号是 424-124-9675 ，因此您将计算键值 424 + 124 + 967 + 5 = 1520 。您可以使用 % 运算符来修剪此类总和，因此最高索引为 999 。在这种情况下， 1520 % 1000 = 520 。

如果数组大小为 100 ，则需要将 10 位密钥分成五个两位数： 42 + 41 + 24 + 96 + 75 = 278 和 278 % 100 = 78 。

当数组大小是 10 的倍数时，更容易想象这是如何工作的。但是，为了获得最佳结果，它应该是质数。

这是我实现的数字折叠技术的 Java 代码：

 public class DigitFolder {
    public static void main(String[] args) {
        int hashVal = hashFunc(424124967);
        System.out.println(hashVal);
    }
    public static int hashFunc(int key) {
        int arraySize = 1021;
        int keyDigitCount = getDigitCount(key);
        int groupSize = getDigitCount(arraySize);
        int groupSum = 0;
        String keyString = Integer.toString(key);
        int i;
        for (i = 0; i < keyString.length(); i += groupSize) {
            if (i + groupSize <= keyString.length()) {
                String group = keyString.substring(i, i + groupSize);
                groupSum += Integer.parseInt(group);
            }
        }
        // There is no remaining part if count is divisible by groupsize.
        if (keyDigitCount % groupSize != 0) {
            String remainingPart =
                   keyString.substring(i - groupSize, keyString.length());
            groupSum += Integer.parseInt(remainingPart);
        }
        return groupSum % arraySize;
    }
    public static int getDigitCount(int n) {
        int numDigits = 1;
        while (n > 9) {
            n /= 10;
            numDigits++;
        }
        return numDigits;
    }
}

我在 这里 找到了组制作方法。但它使组从右到左。所以，我使用了 String#subString() 方法来制作从左到右的组。

原文由 Yogesh Umesh Vaity 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

使用的折叠方法有两种类型 Fold shift 和 Fold boundary 。

折叠移位

您将密钥分成大小与所需地址大小相匹配的部分。只需添加零件即可获得所需的地址。

密钥：123456789，所需地址大小为3位。

123+456+789 = 1368。为了将大小减小到 3，删除 1 或 8，因此密钥将分别为 368 或 136。

折叠边界

您再次将密钥分成大小与所需地址大小相匹配的部分。但是现在您还应用折叠，除了中间部分，如果它在那里的话。

密钥：123456789，所需地址大小为3位

321（应用折叠）+456+987（应用折叠）= 1764（丢弃 1 或 4）

原文由 Sumeet 发布，翻译遵循 CC BY-SA 3.0 许可协议