找到適合拉賓，卡普字符串搜索算法

什麼是可用於實現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

找到適合拉賓，卡普字符串搜索算法

回答

相關問題