哈希表和哈希图有什么区别？（不特定于 Java）

Question

在我最近一次软件工程师职位面试中，有人问我这个问题：hashtable 和 hashmap 有什么区别？我问面试官他是否具体说明 Java 因为在 Java 中 hashtable 是同步的而 hashmap 不是（实际上在谷歌搜索后有大量信息可以比较 Java 中的 hashtable 和 hashmap 所以这不是我正在寻找的答案）但他拒绝了，并想让我解释一下这两者的区别。

对于这个问题，我真的很疑惑和震惊（其实现在还在疑惑）。 IMO、hastable 或 hashmap 只是一个术语问题。实际上只有 Java 有这两个术语，而在 C++ 等其他语言中，它们甚至没有术语 hashtable。面试的时候只是解释了hashing的原理，说hashmap和hashtable都是按照这个原理来实现的，不知道这两者有没有区别。面试官肯定不服气，在找其他答案，当然我在那轮之后就被拒了。

所以回到主题，hashmap 和 hashtable 之间的一般差异（不特定于 Java）可能有什么区别？

Answer 1

计算机科学中的措辞有所不同。

哈希表是某种查找table，使用键散列在类似table 的数据结构中查找相应的值。那只是一种键值映射。您可能知道有不同的实现。不同的哈希、哈希共谋解决方案和 table 增长策略等等。仅当您出于任何原因需要制作自己的哈希 table 时才有趣。

HashMap 是键值对与散列键的某种映射。映射本身是抽象的，它可能不是 table。平衡树或尝试或其他数据 structures/mappings 也是可能的。

你可以简化说HashTable是底层数据结构，HashMap可能就是利用了HashTable。

字典是另一个抽象层次，因为它可能根本不使用散列——例如全文二进制搜索查找或其他比较方式。这就是您在不考虑某些编程语言的情况下可以得到的全部内容。

-- 在考虑太多之前。你能肯定地说 - 你的面试官知道 he/she 在说什么吗？您是否讨论了技术细节，或者他们只是 listen/ask 并且有时发表评论？有时面试官只是针对他们一开始并不真正理解的问题提出最可笑的答案。就像您自己写的一样，一般来说它只是术语。软件开发人员经常使用可互换的术语，除了那些真正有差异的人，例如 Java.

Answer 2

面试官可能一直在寻找洞察...

a hash table 是一个较低级别的概念，并不暗示或不一定支持任何 区分或分离键和值（即您可以使用散列table实现值的散列集），而
a hash map 必须支持不同的键和值，因为从键到值必须有一个 mapping/association；两者是不同的，即使在某些实现中它们总是并排存储在内存中，例如相同结构的成员/std::pair<>.

示例：（错误的）哈希 table 实现阻止用作哈希映射。

考虑：

template <typename T>
class Hash_Table
{
    ...
    bool insert(const T& t)
    {
        // work out which bucket t hashes to...
        size_t bucket = hash_bytes((void*)&t, sizeof t) % num_buckets_;

        // see if t is already stored in the bucket...
        if (memcmp((void*)&t, (void*)&buckets_[bucket], sizeof t) == 0)
            ...
        ... handle collisions etc. ...
    }
    ...
};

上面，硬编码调用哈希函数，将插入的值视为二进制 blob，以及整个 t 的 memcmp，这意味着您不能 T 说一个 std::pair<int, std::string> 并使用散列 table 作为从 ints 到 strings 的散列映射。因此，这是一个哈希 table 的示例，它不能用作哈希映射。

您 可能会也可能不会 还考虑一个哈希 table ，它根本不提供任何方便的使用功能作为散列映射而不是散列映射。例如，如果 API 被设计为 就好像 只处理值 - h.insert(t); h.erase(t); auto i = h.find(t); - 但它允许调用者指定任意自定义比较和散列函数，这些函数可以将它们的操作限制在 t 的关键部分，然后散列 table 可以（滥用）用作功能散列映射。

为了澄清这与 makadev 现有答案的关系，我不同意：

"A HashTable [uses] key hashes to lookup the corresponding value"；错误，因为它采用键->值映射。
"A HashMap [...]. Mapping is abstract as such and it may not be a table. Balanced trees or tries or other data structures/mappings are possible too."；错误，因为散列映射的主要机制仍然是 table/array 中存储桶（索引）的键的散列：一些散列 tables/maps 可能使用其他数据结构（数组、链表、树.. .) 来存储在同一个桶中发生碰撞的元素，但这是一个不同的问题，而不是散列 tables 和散列映射之间的区别的一部分。

Answer 3

实际上 HashTable 已经过时了，HasHMap 是最好的使用方法，因为 Hashtable 是同步的。如果不需要 thread-safe 实现，建议使用 HashMap 代替 Hashtable。如果需要 thread-safe highly-concurrent 实现，则建议使用 java.util.concurrent.ConcurrentHashMap 代替 Hashtable。

第二个区别是HashMap扩展了Map接口，是否扩展了HashSet Dictionary接口

哈希表和哈希图有什么区别？ （不特定于 Java）

What are the differences between hashtable and hashmap? (Not specific to Java)

hashmap

hashtable

哈希表和哈希图有什么区别？（不特定于 Java）