找到适合拉宾，卡普字符串搜索算法

什么是可用于实现Rabin-Karp string search algorithm一些好的哈希函数好的哈希函数？我只知道多项式哈希的，但它有一些缺陷 - 最明显的是，如果散列做模2 ，有哪些是保证经常产生碰撞测试（使用另一模量是不切实际的，因为mod操作非常贵）。那么，有没有一个快速，易于编写的好的散列函数？找到适合拉宾，卡普字符串搜索算法

P.S.我知道buzhash，但我想知道是否有其他的替代方案...

来源

2012-10-04 Artyom

mod（％）并不贵。在上个世纪80年代它*使用*的价格很高。问题：为什么散列函数应该*快* *？ – wildplasser

BTW：modulo（1 << 64）肯定不贵。如果你使用64位*无符号*类型，那么就是*免费*。 – wildplasser

@wildplasser他对特定的测试评论似乎意味着这个问题正在从编程竞赛的角度问，其中模1 << 64是不切实际的：http://codeforces.com/blog/entry/4898 – ffao

因为它不是一个安全哈希，你只需要一个“好”的指纹，我会建议像Tabulation hashing。洞操作将比mod操作快大约多倍。

来源

2012-10-05 01:37:46 iampat

找到适合拉宾，卡普字符串搜索算法

回答

相关问题