寻找学习用的高质量哈希表/无序映射实现？
- 我在找一些好的源代码，最好是用C、C++或Python写的，这样我可以理解哈希函数是怎么实现的，还有哈希表是怎么用这个函数来实现的。
- 关于哈希函数和哈希表实现的材料非常不错。
提前谢谢大家。
3 个回答
1
你的问题有点问题：哈希表的种类和用途一样多。
处理哈希冲突和重新分配的方法有很多，具体取决于你的需求。你可能会找到一个大致适合的解决方案，但如果我是你，我会像Dennis建议的那样去维基百科看看，了解各种实现的细节。
正如我所说，你可以从两个方面来考虑这些策略：
- 处理哈希冲突：用桶，哪种桶？开放寻址？双重哈希？……
- 重新分配：是冻结哈希表还是使用摊销线性？
另外，你想要内置的多线程支持吗？使用atomic操作可以实现无锁的多线程哈希表，这在Java中已经被Cliff Click证明过了（谷歌技术讲座）。
正如你所看到的，没有一种方法适合所有情况。我建议你先学习一些基本原理，然后再深入了解具体的实现细节。
- C++中的
std::unordered_map使用链表作为桶，并采用冻结哈希表的策略，通常不考虑适当的同步问题。 - Python的
dict是语言的基础，我不太清楚他们选择了什么策略。
1
如果你想学习，我建议你看看 java.util.HashMap 的Java实现。这个代码写得很清晰，文档也很完善，而且相对较短。虽然它不是C、C++或者Python，但你可能不想去看GNU libc++即将推出的哈希表实现，那里面的内容复杂得让人头疼，主要是因为C++标准模板库的复杂性。
首先，你应该先阅读一下 java.util.Map 接口的定义。然后你可以直接深入了解 java.util.HashMap 的细节。如果还有什么不明白的地方，可以在 java.util.AbstractMap 中找到补充信息。
一个好的哈希函数的实现和编程语言无关。它的基本任务是把一个任意大的值集合映射到一个较小的值集合（通常是某种整数类型），这样得到的值就能均匀分布。
3
哈希表在Python中非常重要，它不仅用来实现'dict'（字典）类型，还用于类和命名空间的实现。因此，这个功能在这些年里经过了不断的改进和优化。你可以在这里查看字典对象的C语言源代码：这里.
每种Python类型都有自己独特的哈希函数——你可以查看其他对象的源代码，了解它们是怎么实现的。