Haskell 中的 Pearson 哈希实现

Question

我必须为学校编写这个 Pearson Hash，但我从未听说过它，所以很难想象它是如何工作的。这让事情变得更加困难，我很久以前就学会了 haskell，但我几乎忘记了它。

事情是这样的：他们告诉我这个函数的语法是这样的：

pearsonHash :: [Int] -> [Int] -> Int

Pearson Hash 算法为：

h := 0
for each c in C loop
    index := h xor c
    h := T[index]
end loop
return h

他们说：设C为字节的输入序列，h为要计算的值。 pearson hash 的第一个参数应该是一个预定义的 T 列表，其中包含 [0..255].

的排列

有测试用例：

pearsonHash ([0..127] ++ [255,254..128]) [1..10]   ==  11
pearsonHash [255,254..0] [ ord c | c <- "Hello" ]  ==  189

我觉得应该是True.

这只是工作的一部分（意味着这只是很多功能中的一个），所以我不想让你代替我解决这个问题，我只需要帮助解决这个功能，因为我被这个卡住了。

Answer 1

h := 0
for each c in C loop
    index := h xor c
    h := T[index]
end loop
return h

好的，所以这看起来非常必要。当您看到这样的循环时，您可能想要做的是将 "loop body" 变成一个函数，然后循环本身将是 foldr 或 foldl。所以你的代码最终看起来像

hashStep :: [Int] -> Int -> Int -> Int
hashStep ts h c = ...???...

pearsonHash :: [Int] -> [Int] -> Int
pearsonHash ts cs = foldr (hash_step ts) 0 cs

现在，你能想出 hashStep 应该做什么吗？

Haskell 中的 Pearson 哈希实现

Pearson Hash implementation in Haskell

hash

haskell

pearson