javascript - 如何使用无内存函数将 256 个唯一字符串映射到整数 (0..255)

Question

假设我有类似 foo 的字符串, bar , baz , hello , world等最多 256 个独特的字符串，所以不是很多。对于所有意图和目的，它可以很容易地是 200 个字符串或 32 个字符串。希望该解决方案可以处理任意大小的集合。

因此，您获取该字符串并以某种方式将其映射到 0-255 的整数。不只是这样做:

strings[currentString] = ID++
// strings['foo'] = 0
// strings['bar'] = 1
// strings['baz'] = 2
// ...

这取决于插入的顺序。理想情况下，它们可能会以某种方式从单个字符或字节的散列中唯一生成，我不确定。但它是一个没有内存的函数，它从一组已知大小的集合中获取任意字符串并将其映射到一个整数，因此更像是:

// strings['foo'] = 6 + 15 + 15 = 36
// strings['bar'] = 2 + 1 + 16 = 19
// ...

虽然这不会因为碰撞而起作用。我不确定如何着手设计这样的哈希函数。所以不知何故，在永远不会发生碰撞的情况下，其他方法会起作用。

function hash(string, size) {
  // return unique integer within size
}

hash('foo', 256) // something like 123
hash('bar', 256) // something like 101

hash('foo', 100) // something else like 50
hash('bar', 100) // something else like 25

我很想知道如何创建这样一个函数，因为它看起来非常困难，但对于这个问题来说并不是绝对必要的。

此外，希望使用基本的 JavaScript 来做到这一点，而不是任何特殊的辅助方法或特定于浏览器的东西。

可能的字符串集是预先知道的。

Answer 1

除非您提前知道所有 256 个字符串是什么，否则我不相信您正在寻找的是可能的。粗略地说，这里有一个证明:

假设存在一些f : S^* → [0, 255] (注意:S^* 表示所有有限长度的字符串)对于所有 256 个长度的子集 S ⊆ S^* , s_1, s_2 ∈ S, f(s_1) = f(s_2) <=> s_1 = s_2 .自 f不能保存它所看到的任何输入内存，它必须确定地将字符串映射到 [0, 255] 中的相同数字，无论它在哪个子集中。

然而，通过Pigeonhole Principle ，因为有超过 256 个字符串，我们必须至少有两个字符串映射到 [0, 255] 之间的相同值。 .特别是，这意味着如果我们取一个子集 S包含两个字符串，以上属性为 f被侵犯，矛盾。因此，f不存在。

---

如果允许您知道要散列哪些 256 个字符串，这绝对是可能的。一般来说，你要找的是 perfect hash function .

此链接提供了一个算法:https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf (引用第 56-57 页)

引用:

Method 1: an O(N^2)-space solution

Say we are willing to have a table whose size is quadratic in the size N of our dictionary S. Then, here is an easy method for constructing a perfect hash function. Let H be universal and M=N^2. Then just pick a random h from H and try it out! The claim is there is at least a 50% chance it will have no collisions.

Method 2: an O(N)-space solution

We will first hash into a table of size N using universal hashing. This will produce some collisions (unless we are extraordinarily lucky). However, we will then rehash each bin using Method 1, squaring the size of the bin to get zero collisions. So, the way to think of this scheme is that we have a first-level hash function h and first-level table A, and then N second-level hash functions h_1, ..., h_N and N second-level tables A_1, ..., A_N. To lookup an element x, we first compute i=h(x) and then find the element in A_i[h_i(x)].