RS哈希程序

Question

请问有人可以告诉我RS字符串哈希算法的工作原理或算法吗？我需要它，但在谷歌上找不到。请至少帮助我提供算法，我想自己实现它。

- Sujit Agarwal

Answer 1

您是指罗伯特·塞奇威克的字符串哈希算法吗？

uint a = 63689, uint b = 378551
foreach ( byte x ; bytes ) {
    value = value * a + x;
    a *= b;
}
return value;

以下内容引用自 http://pallas.telperion.info/d/hash/

。

哈希（Hash）是指将任意长度的消息压缩至某一固定长度的消息摘要（Message Digest），并且该摘要是唯一的，即不同的输入一定会产生不同的输出。因此，哈希可以看作是一种单向加密，不能通过摘要反向推出原始消息。哈希在密码学、数字签名、信息安全等领域得到广泛应用。

- Jeff Foster

---

请问这段代码是用哪种语言编写的？ - Sujit Agarwal

它是用D语言编写的（至少根据原始网站）。希望将其复制到您选择的语言中非常简单。 - Jeff Foster

Pallas的链接已经失效了，你能更新一下吗？谢谢。另外，这个哈希函数可以用于整数向量吗？ - Rich

@JeffFoster 为什么在调用 a *= b; 时不用担心溢出问题？ - John

溢出问题并不重要，因为我们的目的不是创造 “正确” 的答案，而是一个一致的答案。 - Jeff Foster

Answer 2

Python的实现如下：

def RSHash(key):
    a = 63689
    b = 378551
    hash = 0
    for i in range(len(key)):
        hash = hash * a + ord(key[i])
        a = a * b
return hash

- Hitman_99

---

“hash” 没有截断为 32 位。这段代码会返回一个非常长的哈希值。 - swdev

调用 a *= b; 时为何不用担心溢出？ - John

Answer 3

C++ 实现如下：

unsigned int RSHash(const std::string& str)
{
   unsigned int b    = 378551;
   unsigned int a    = 63689;
   unsigned int hash = 0;

   for(std::size_t i = 0; i < str.length(); i++)
   {
      hash = hash * a + str[i];
      a    = a * b;
   }

   return hash;
}
/* End Of RS Hash Function */

- iDebD_gh