如何为哈希表查找键实现基于3位的哈希函数

Question

我想在一个URL中有8个可能的字符，我们称它们为1、2、3、4、5、6、7、8。然后我想使用这些作为哈希表查找的关键字。我不想做典型的基于8位的哈希算法，而是想知道如何实现基于3位的平衡/高度随机的哈希算法(8个字符可以用3位编码(。因此(在JS中用于演示目的(，它将在给定3比特长的倍数输入的情况下生成一个平衡良好的哈希表。所以你可能有：

8
88
888
18
81
8181

作为散列的可能密钥。这些字符来自8个字符集。所以我要做的是从这个开始：

function hashBinary(bin) {
// iterate through 3 bits at a time
// build a nice random hash
}
function hashString(str) {
let binary8Bit = str.split('').map(x => parseInt(x))
// do something? to convert the 8-bit-chunk list to a 3-bit chunk list.
let binary3Bit = new ArrayBuffer()
// ... something
return hashBinary(binary3Bit)
}
hashString('8181')
hashString('88')

你是怎么开始正确地做这件事的？

尝试学习如何从头开始实现一个好的哈希算法，以及如何在非8位字符串上实现它。

Answer 1

正如评论中所指出的，任何好的通用哈希函数都应该与您的输入类型一样好——这就是哈希函数的优点。但如果您真的想要，您可以将字符串子集双射映射到自然数中，然后对数字进行散列。

一个非常简单的转换是将字符串解析为八进制数字，只是八进制数字是不同于01234567(此处为12345678(的字符。

function urlToInt(url) {
// adapt `urlDigitToOct` if you use something different than `12345678`
function urlDigitToOct = urlDigit => urlDigit - 1;
const oct = url.replace(/./g, urlDigitToOct);
return parseInt(oct, 8);
}

然而，这会认为您的一些url字符串是相等的。前导1s被解释为前导零，可以在不改变含义的情况下从头开始进行预处理或剪切。例如1＝11＝111和41＝141＝1141(但不是4！(。

如果不同的字符串总是导致不同的数字，那么每个url字符三个比特就不够了。您还需要存储有关字符串长度的信息。这里有一个更通用的解决方案，密集地枚举由给定的一组唯一字符组成的所有字符串
枚举的工作原理如下：0是空字符串，1是给定集合中的第一个字符，2是第二个字符，依此类推。在考虑了所有字符后，我们继续使用长度为2的字符串，然后是长度为3的字符串，依此类推

// use `digits = "12345678"` in your case
const digits = "abc";
const digitToVal = Array.from(digits).reduce((map, digit, idx) =>
map.set(digit, idx), new Map());
const base = digitToVal.size;
function urlToInt(url) {
// base^0 + base^1 + ... + base^(url.length-1) is a geometric series
const countShorterUrls = (1 - base ** url.length) / (1 - base);
return Array.from(url).reduce((acc, digit, idx) =>
acc * base + digitToVal.get(digit), 0) + countShorterUrls;
}
// manual test
["", "a", "b", "c", "aa", "cc", "aaa", "ccc", "aaaa"]
.forEach(url => console.log(`url "${url}" has number ${urlToInt(url)}`));

现在你处理的是所有的自然数，而不是所有字符串的子集，你可以像平时一样实现你的哈希算法