我實現了一個自定義的HashMap類（在C++中，但不應該）。實現很簡單 -如何提高HashMap迭代的複雜度？
- 一個大數組包含指向Items的指針。
- 每個項目包含鍵值對和一個指向項目的指針（以在發生鍵衝突時形成鏈接列表）。
- 我也爲它實現了一個迭代器。
我的遞增/遞減迭代器的實現不是非常有效。從當前位置，迭代器掃描下一個非空條目的散列數組。這是非常低效的，當地圖稀疏填充（這將是我的用例）。
任何人都可以建議更快的實現，而不會影響插入和查找等其他操作的複雜性嗎？我的主要用例是find，secondary是插入。迭代甚至不需要，我只是想知道這是爲了學習。
PS：爲什麼我實現了一個自定義類？因爲我需要查找具有一定容錯性的字符串，而準備好的哈希映射只能提供完全匹配。
編輯：爲了澄清，我正在談論遞增/遞減已獲得的迭代器。是的，這主要是爲了遍歷整個地圖。
在我的情況下字符串（鍵）中的錯誤發生在OCR錯誤。所以我不能使用錯誤處理技術來檢測輸入錯誤。拳頭性格錯誤的機會幾乎與最後一個相同。
此外，我的鍵總是字符串，一個字是確切的。條目數將少於5000.所以2^16的哈希表大小對我來說就足夠了。即使它仍然是人口稀少，但沒關係。
我的散列函數：
哈希碼大小是16位。
字長的前5位。 ==>最大可能的密鑰長度= 32。合理的，因爲密鑰是一個單詞。
最後11位的char代碼總和。我只存儲英文字母字符，並且不需要區分大小寫。所以26個代碼就足夠了，0到25.所以一個32'z'= 25 * 32 = 800的密鑰，這個在2^11之內。如果將來需要，我甚至可以添加區分大小寫。
現在，當你比較包含錯誤與正確的一個關鍵， 說「地獄」與「你好」的關鍵 1.長度大約是相同 2和他們的字符會由不同的總和丟失/添加/扭曲的字符。
在散列碼中，前5位用於長度，整個表具有用於每個可能長度的鍵的固定部分。所有部分的大小相同。第一部分存儲長度爲1，長度爲2的第二部分等等。
現在'你好'存儲在第5部分，長度爲5。'當我們試圖找到'你好'時， 'hello'的哈希碼=（長度-1）（字符之和）=（4）（7 + 4 + 11 + 11 + 14）=（4）（47） =（00100）（00000101111）
同樣， '直升機' 的哈希碼=（3）（36） =（00011）（00000100100）
- 我們跳到它的水桶，並沒有找到它在那裏。
- 所以我們試着檢查一個扭曲的字符。這不會改變長度，但可以將字符總數改爲最大-25到+25。所以我們從25個地方向後搜索到25個地方。即我們在同一部分檢查（36-25）到（36 + 25）的總和部分。我們不會找到它。
- 我們檢查是否有其他字符錯誤。這意味着正確的字符串將只包含3個字符。所以我們去第三部分。現在，由於額外的字符而產生的字符總和會增加最多25個字符，因此必須予以補償。因此，在第三部分搜索適當的25個地方（36 - 0）到（36 - 25）。我們再次找不到。
- 現在我們考慮一個缺少字符的情況。所以原始字符串將包含5個字符。哈希碼的第二部分是原始字符串中字符的總和，它將更多地取決於0到25的因子。因此我們在第5部分（36 + 0）到（36 + 25）中搜索相應的25個桶。現在，47（「hello」的總和部分）位於此範圍內，我們將找到哈希碼的匹配項。答：我們也知道這場比賽是由於缺少一個人物而造成的。所以我們比較一下允許容差爲1的字符。我們得到一場比賽！
實際上，這已被實現以允許在關鍵字中出現多個錯誤。 它也可以優化爲只使用25個位置（因爲它只有一個字符）等等。 此外，檢查25個地方似乎過分，因爲我們已經知道密鑰的最大和最小字符。但是如果出現多個錯誤，它會變得複雜。
我不明白，當你試圖找到一個值時，你不應該立即用給定的鍵轉到數組中的第一個「Item」，然後遍歷一個鏈表？如果你不得不遍歷整個數組，那麼你的數組太小或者你的散列函數不是很好（這種情況發生的唯一方法就是碰撞是否存在_tons_）。 – Jared 2014-12-13 06:42:43
@Jared I *認爲*（很可能不正確）他說的是迭代整個哈希映射*，而不僅僅是一個碰撞鏈。我很高興知道更清晰，我同意。 – WhozCraig 2014-12-13 07:01:46
你是說你想把''hello''和''hwllo'''映射到同一個散列值（因爲它們是相似的 - 注意'e'和'w'很容易被意外地鍵入另一個基於他們在QWERTY鍵盤上的位置）。因此，你想快速查找本質上相似的字符串組？因爲如果你說要查看每個字符串並進行比較（並找到最接近的字符串），那麼你沒有描述任何可以被遠程解釋爲散列表的東西。 – Jared 2014-12-13 07:56:39