用線性探測字符串哈希

我被困在試圖弄清楚如何用線性探測字符串哈希。用線性探測字符串哈希

基本上，這個想法是散列字典（90000字）的每個字符串，並檢索所選單詞的字形。

這裏就是我所做的：

創建一個哈希表的大小
使用一個簡單的哈希函數2 * 90000，我哈希從字典中的每個字，得到一個值
檢查散列表索引是否爲空，如果是，則分配值，如果不是，則生成新的散列值。
後，每一個字都是在哈希表，我執行搜索
搜索詞將散列函數後收到的哈希值，在哈希表中是否存在該值，將檢查或不。
如果存在，它會比較使用排列的字符串。如果匹配成立，它將輸出它。如果不是，它將繼續使用新的哈希值查找。

問題是，整個過程非常緩慢......它索引很好，但搜索需要很長時間。

我出如何使這個想法更快..

感謝您抽出時間閱讀本。

來源

2010-01-25 tpae

您正在使用哪種數據結構來存儲散列字符串？ – Naveen 2010-01-25 05:46:11

我正在使用字符串數組，因爲它需要遵循線性探測。 – tpae 2010-01-25 05:55:40

先把所有的字母按字母順序排列，然後用任何哈希算法對結果進行哈希（crc32，md5sum，sha1，計算元音，任何東西......但計算元音會導致效率較低的解決方案），並將該單詞作爲葉節點存儲到該散列條目中（顯然，在鏈表中） - 對散列結果執行mod（x）以將桶限制爲2^x。

然後，當你去找到一個字謎，做你測試字完全相同的「插入」過程：按字母順序排列的字母，然後通過你的相同的哈希函數運行它。然後，對於每個葉節點，將字母順序的字母列表與保存的字母字母表列表進行比較。每場比賽都是一個字謎。（我通常不喜歡給家庭作業幫助，但這個太誘人了，現在我想寫一個有趣的小程序來找到給定字典中的所有字母。）

來源

2010-01-25 06:03:03 tylerl

問題是關於線性探測 - 他應該將該單詞存儲在下一個打開的存儲區中，而不是存儲在（不存在的）葉節點中。但是，對字母排序的建議比修改散列算法本身更好。 – 2010-01-25 06:27:09

+1用於排序字母，對於字謎它確實有意義，並且您甚至可以獲得所有字謎在同一個存儲桶中結束的好處。 – 2010-01-25 12:31:26

-1

您是否嘗試創建給定字符串的Anagrams？在這種情況下，只需創建一個字符串作爲輸入。對這些字符串進行散列有什麼意義？

編輯：首先，我會建議你得到給定的字符串的所有排列，然後通過字典文件包含所有單詞循環。這有一個好處，你不需要在內存中擁有所有的單詞。如果您想進一步優化，請根據字符串長度按升序或降序對整個文件進行排序，並繼續檢查字典文件中的字符串，直到您將< =更改爲下一個字符串的長度。

來源

2010-01-25 05:50:06 Jagannath

來搜索那個anagram是否是一個有效的單詞 – sud03r 2010-01-25 05:53:29

anagrams需要來自字典。由於有90000個單詞，因此使用排列依次遍歷它們應該更慢。 – tpae 2010-01-25 05:53:33

線性探測用於您正在使用的散列函數爲某些輸入字符串提供衝突的情況。在這種情況下，您將按順序搜索散列表，直到找到您的搜索關鍵字。

這種方法的缺點是，如果有一次碰撞，會有更多。

一種方法是，您可以使用Separate Chaining並使用平衡樹作爲存儲桶以改善查找。

如果您只是想提高性能，請確保沒有衝突（在這種情況下，查找完全是O（1）），如果存在，請增加散列表大小。

來源

2010-01-25 06:09:40 sud03r

對不起，但作業要求我使用線性探測.. :( – tpae 2010-01-25 07:22:59

-1

如果您正在搜索輸入詞的每個置換，這是問題的根源。一個單詞字母的排列數量可能會相當大。

取而代之，選擇一個散列函數，它對任何一個單詞的排列（anagram）都是一樣的。例如，基於單詞中字符的字符代碼總和。

來源

2010-01-25 06:21:11 ergosys

雖然這解決了即時問題，但它是一個非常糟糕的散列算法 - 將會有大量的碰撞。更好的解決方案是tylerl提出的一個更好的解決方案，它可以使用一種好的散列算法，並且仍然可以處理大量的排列 – 2010-01-25 06:25:51

我沒有說散列函數是什麼，只是它對於任何排列都是一樣的，如果你先排序字符，這符合我的標準。犯了一個壞例子，雖然 – ergosys 2010-01-25 06:30:10

這是行不通的，因爲不是所有的單詞長度都是一樣的 – tpae 2010-01-25 06:30:35

用線性探測字符串哈希

回答

相關問題