我实现了一个自定义的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