什么是散列中的折叠技术以及如何实现它?
What is Folding technique in hashing and how to implement it?
我在一个数据结构研讨会上听说我们可以将一个键分成数字组,然后进行组相加。这确保了所有数字都贡献了哈希码。一组中的位数对应数组的大小。
例如,我有一个机器号424-124-9675
,如何使用折叠技术制作哈希函数?
给定 424-124-9675,您可以决定将其分组的位置。例如:
左起每3位:hash = 424 + 124 + 967 + 5
从右起每3位:hash = 675 + 249 + 241 + 4
破折号是:hash = 424 + 124 + 9675
虽然这是一种非常弱的散列方法 - 很容易发生冲突。
使用了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)
根据 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()
方法从左到右进行分组。
我在一个数据结构研讨会上听说我们可以将一个键分成数字组,然后进行组相加。这确保了所有数字都贡献了哈希码。一组中的位数对应数组的大小。
例如,我有一个机器号424-124-9675
,如何使用折叠技术制作哈希函数?
给定 424-124-9675,您可以决定将其分组的位置。例如:
左起每3位:hash = 424 + 124 + 967 + 5
从右起每3位:hash = 675 + 249 + 241 + 4
破折号是:hash = 424 + 124 + 9675
虽然这是一种非常弱的散列方法 - 很容易发生冲突。
使用了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)
根据 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()
方法从左到右进行分组。