字符串的獨特屬性以構建高效的哈希表

C++中字符串的獨特屬性是什麼？爲什麼它們可以通過關係運算符進行比較（例如，在嘗試按字母順序排序字符串數組時）？我試圖利用這個「屬性」來建立一個沒有每個可能的字符串衝突的表的罰款哈希函數。另外，什麼數據結構可以爲此工作？我正在考慮一個矢量，因爲我不得不通過一個文檔而不知道它裏面有多少個獨特的單詞，而且我只想查看一次這個文檔。字符串的獨特屬性以構建高效的哈希表

來源

2015-11-26 Layomi Akinrinade

關係運算符通常是重載，它包含一些複雜函數，如c的'strcmp'。事實並非如此簡單。 – Petr

比較字符串就像比較基數 - 256位數字一樣。 –

C++標準字符串本質上是字符的向量。比較字符串意味着從一開始就逐字比較它們。我不確定'unique property'是什麼意思，但是對於你的用例，任何哈希算法都應該這樣做。如果我正確理解你的用例，你可能需要使用std :: set < YourHashType>或std :: map。這樣你就不必考慮是否已經添加了一個單詞。

來源

2015-11-26 16:01:48 mvd

最簡單的算法，計算出一個空結尾的C風格的字符串散列鍵如下：

UINT HashKey(const char* key) const 
{ 
    UINT nHash = 0; 
    while (*key) 
     nHash = (nHash<<5) + nHash + *key++; 
    return nHash; 
}

來源

2015-11-26 16:02:14

您可能想看看[P0029R0]（http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0029r0.html）中的組合方法，該方法能夠創建良好的（儘管可能不加密）散列值。 –

我同意這是一個複雜的話題，有很多方面，但我只是想提供一個基本的想法，如何實現一個字符串的哈希計算算法。 –

我想利用這一「屬性」，以建立一個對於每個可能的字符串都沒有碰撞的表格的精細哈希函數。

作爲pigeonhole principle的示例，您不能擁有無衝突散列函數。當您使用像std::strcmp這樣的函數進行詞法比較時（例如逐字母）比較字符串時，字符串的排序是唯一的，但只會使用比較而不是字符串的固有唯一屬性給出唯一順序。

如果您有一組有限的密鑰，您可以設計一個無衝突散列函數，它被稱爲perfect hashing。

來源

2015-11-26 16:13:12 Jason

字符串的獨特屬性以構建高效的哈希表

回答

相關問題