algorithm - 检查一个值是否属于哈希

Question

我不确定这是否真的可行，所以我在这里问。有谁知道允许这样的算法吗？

const values = ['a', 'b', 'c', 'd'];
const hash = createHash(values); // => xjaks14sdffdghj23h4kjhgd9f81nkjrsdfg9aiojd
hash.includes('b'); // => true
hash.includes('v'); // => false

这段代码的作用是首先从值列表中创建某种散列，然后检查特定值是否属于该散列。

Answer 1

一般哈希函数

散列函数的主要思想是减少空间，即函数非单射，因为它们从较大的域映射到较小的域。

因此它们会产生碰撞。也就是说，有不同的元素 x 和 y 映射到相同的哈希值:

h(x) = h(y)

所以基本上你丢失了给定参数 x 的信息。

但是，为了回答是否包含所有值的问题，您需要保留所有信息(或至少所有非重复信息)。对于几乎所有实用的哈希函数来说，这显然是不可能的。

可能的散列函数是身份函数:

h(x) = x for all x

但这并没有减少空间，不实用。

一个自然的想法是计算各个元素的哈希值，然后将它们连接起来，比如

h(a, b, c) = (h(a), h(b), h(c))

但这又不会减少空间，哈希值与消息一样长，不实用。

另一种可能性是删除所有重复项，因此给定值[a, b, c, a, b] 我们只保留[a, b, c]。但是，在大多数示例中，这只会稍微减少空间，同样不切实际。

但是无论你做什么，你都不能减少非重复项的数量。否则您将无法回答某些值的问题。例如，如果我们使用 [a, b, c, a] 但只保留 [a, b]，我们无法回答 "was c 包含“ 正确。

---

完美哈希函数

但是，存在完美哈希函数的领域(Wikipedia)。这些是内射的哈希函数，它们不会产生冲突。

在某些领域他们很感兴趣。

对于那些您可能能够回答该问题的人，例如，如果计算逆运算容易。

---

加密哈希函数

如果您谈论加密哈希函数，答案是否。

那些需要具有三个属性(Wikipedia):

• 原像阻力 - 给定 h 应该很难找到 m : hash(m) = h
• 第二个原像阻力 - 给定 m 应该很难找到 m' : hash(m) = hash(m')
• 抗碰撞 - 应该很难找到 (m, m') : hash(m) = hash(m')

非正式地，您特别是:

A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value.

如果您现在有这样一个哈希值，您将能够通过询问是否包含某些值来轻松地重建它。使用它，您可以轻松地故意构造碰撞和类似的东西。

然而，细节将取决于特定的哈希算法。

举个简单的例子，让我们使用之前的简单删除所有重复项的算法:

[a, b, c, a, a] -> [a, b, c]

在那种情况下，我们会找到像

这样的消息

[a, b, c]
[a, b, c, a]
[a, a, b, b, c]
...

所有映射到相同的哈希值。