我正在閱讀這篇關于字串散列的文章。在“在字串陣列中搜索重復字串”部分，它聲稱您可以O(M*N*log(N))使用字串散列對時間復雜度為的相同字串進行分組。
查看文章中提供的此代碼示例
vector<vector<int>> group_identical_strings(vector<string> const& s) {
int n = s.size();
vector<pair<long long, int>> hashes(n);
for (int i = 0; i < n; i )
hashes[i] = {compute_hash(s[i]), i};
sort(hashes.begin(), hashes.end());
vector<vector<int>> groups;
for (int i = 0; i < n; i ) {
if (i == 0 || hashes[i].first != hashes[i-1].first)
groups.emplace_back();
groups.back().push_back(hashes[i].second);
}
return groups;
}
我對這段代碼如何正確感到非常困惑，因為它僅在hashes[i].first != hashes[i-1].first. 兩個字串可以不同而具有相同的哈希值，因此即使它們不同，也可以將兩個字串添加到同一組中？這個條件在我看來還不夠。
我錯了嗎？這段代碼正確嗎？為什么？
如果不是，那么這個演算法或至少這種復雜性真的可以實作嗎？
uj5u.com熱心網友回復：
您非常正確，兩個不同的字串可以具有相同的哈希值。這稱為散列沖突。但是，它歸結為您使用的哈希函式。有些散列函式不太可能找到沖突，因此您可以很好地使用該演算法而不必擔心它會崩潰。在密碼學中，我們依賴于密碼安全散列函式的這一特性（參見例如此處）。
事實上，你提到的來源宣告如下：
這是您必須牢記的重要部分。使用散列將不是 100% 確定性正確，因為兩個完全不同的字串可能具有相同的散列（散列沖突）。然而，在大多數任務中，這可以安全地忽略，因為兩個不同字串的哈希沖突的概率仍然非常小。我們將在本文中討論如何將碰撞概率保持在非常低的水平。
因此，正如您所說，該演算法在數學上并不正確。但是通過正確選擇哈希函式，它在實踐中崩潰的可能性可以忽略不計。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/380288.html