一个递归构建的哈希函数？

Question

是否有一种（广为人知的）字符串哈希函数，可以由s的子集的哈希值计算得出。 例如：

哈希(0到x)等于哈希(0到x/2)加哈希(x/2到x) // 加或任何其他数学运算

- hasanatkazmi

---

哈希函数是否应该满足交换律，即 hash(0 到 x) 是否等于 hash(x/2 到 x) + hash(0 到 x/2)？ - martinus

以下是关于编程的内容，请将其翻译成中文。返回仅翻译后的文本：可以或不可以都无所谓。 - hasanatkazmi

Answer 1

你可以使用任何喜欢的哈希函数构建哈希树。因此，如果您只需要一个能够从数据部分计算的自定义哈希函数，您可以从任何知名的哈希函数构建它。 Tiger Tree Hashes是相当常用的哈希树变体，它使用Tiger算法。

- sth

---

+1 这将既是“安全的”，又是递归的...总结函数中的“+”应该是单向数学函数。 - Jorge Córdoba

我已经在Tiger上工作了一段时间了，这种哈希算法有点难以理解，你有什么建议或想法吗？ - hasanatkazmi

Answer 2

我不认为有这样的“哈希”函数。当然，数学函数是存在的...但哈希函数的目的是使哈希尽可能地独立于条目，以便哈希尽可能随机。

如果你仔细想一下，你的哈希函数从一开始就存在缺陷......毕竟我可以计算：

Hash("password") = Hash("pass") + Hash("word")

然后

Hash("word") = Hash("wo") + Hash("rd")

等等...最终递归构建将等于递归构造......这对于哈希函数来说是不好的。

- Jorge Córdoba

---

这意味着他想要一个依赖于安全性的加密哈希。哈希函数有许多用途，并不一定依赖于安全性，例如用于快速随机数据库检索（例如使用哈希作为启发式方法查找类似记录的快速方法）。请参阅哈希函数的应用程序http://en.wikipedia.org/wiki/Hash_function#Applications - Charles Ma

Answer 3

有许多哈希函数可以解决您的问题。在我看来，最好的，并且适用于大多数应用程序的是类似于此处定义的内容：

http://en.wikipedia.org/wiki/Rolling_hash#Rabin-Karp_rolling_hash

在实现中选择一些好的和大的常量非常重要。您需要进行一些数学运算（模算术）以在O（1）中实现连接（从H（A）和H（B）获取H（AB））。您也可以反过来做（例如，从H（AB）和H（B）计算H（A））

- Milo

Answer 4

一个简单的校验和（对某个值取模）符合这个描述，但在许多情况下，它会被认为是一种相对于哈希函数的各种特性而言相当差劲的哈希。例如，这样的哈希可以很容易地被“破解”（如果在某些加密方案中使用），并且它还会为相似的输入产生相同的值，其中输入中的几个字符的顺序被改变。

- mjv