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

Question

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

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

Answer 1

给定 424-124-9675，您可以决定将其分组的位置。例如：

左起每3位：hash = 424 + 124 + 967 + 5
从右起每3位：hash = 675 + 249 + 241 + 4
破折号是：hash = 424 + 124 + 9675

虽然这是一种非常弱的散列方法 - 很容易发生冲突。

Answer 2

使用了Fold shift和Fold boundary两种折叠方法。

折叠移位

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

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

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

折叠边界

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

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

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

Answer 3

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

例如，假设您要散列 10 位机器号。如果数组大小为 1,000，您会将 10 位数字分成三组三位数字和一组一位数字。在问题机器编号的示例中，您将计算 424 + 124 + 967 + 5 = 1520 的键值。您可以使用 % 运算符来 trim 这样的总和，因此最高索引是 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;
    }
}

我找到了团建方法here。但它使组从右到左。所以，我使用 String#subString() 方法从左到右进行分组。

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

What is Folding technique in hashing and how to implement it?

java

algorithm

data-structures

hash

hashtable