哈希表和哈希映射有什么区别？（与Java无关）

Question

哈希表和哈希映射有什么区别？（与Java无关）

4

在我最近一次软件工程师职位的面试中，我被问到了这个问题：哈希表和哈希映射表有什么区别？我问面试官是否特指Java，因为在Java中，哈希表是同步的，而哈希映射表不是（实际上，在谷歌搜索后，有大量关于Java中比较哈希表和哈希映射表的信息，但这并不是我想要的答案），但他说不是，并希望我解释这两者的差异。

我对这个问题感到非常困惑和震惊（实际上现在还是困惑），因为在我看来，哈希表或哈希映射表只是术语的问题。事实上，只有Java有这两个术语，在其他像C++这样的语言中，甚至没有哈希表这个术语。在面试中，我只是解释了哈希原理，并说哈希映射表和哈希表都应该基于此原理实现，我不知道这两者之间是否有任何区别。面试官显然不信服，并寻找其他答案，当然，在那一轮后，我被拒绝了。

所以回到主题，如果有的话，哈希映射表和哈希表在一般情况下（不特指Java）可能有什么区别呢？

- Optimus Prime

跟进一下，看起来在C#中字典和哈希表之间有所不同，但这并不是我要找的。 - Optimus Prime

可能是重复的问题，链接为 https://dev59.com/FlwY5IYBdhLWcg3wup5c - Tony Delroy

3个回答

1

面试官可能想要了解的是...

- 哈希表是一个较低级别的概念，不暗示或必须支持任何键和值的区分或分离（即您可以使用哈希表实现哈希值集），而 - 哈希映射必须支持不同的键和值，因为需要从键到值进行映射/关联；两者是不同的，即使在某些实现中它们总是存储在内存中的相邻位置，例如相同结构体/ std::pair<> 的成员。

示例：一个（糟糕的）哈希表实现，阻止其用作哈希映射。

考虑：

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. ...
    }
    ...
};

上面硬编码的哈希函数调用将插入的值视为二进制块，以及对整个t的memcmp，意味着您无法将T设置为std :: pair 并将哈希表用作从int到string的哈希映射。因此，它是一个不能用作哈希映射的哈希表的示例。

你或许可以考虑使用一个哈希表，但它并没有提供任何方便的特性来作为哈希映射。例如，如果API被设计成仅处理值-h.insert(t); h.erase(t); auto i = h.find(t);，但允许调用者指定任意自定义比较和哈希函数，以限制他们的操作只针对t的键部分，那么哈希表可以被（滥）用作功能性哈希映射。

为了澄清与makadev现有答案的关系，我不同意以下观点：

"HashTable [使用] 键哈希来查找相应的值";这是错误的，因为它假设了键-值映射。
"HashMap[...]。映射本质上是抽象的，可能不是一个表格。平衡树或tries或其他数据结构/映射也是可能的。";这是错误的，因为哈希映射的主要机制仍然是将键哈希到表/数组中的桶（索引）：一些哈希表/映射可以使用其他数据结构（数组、链表、树...）来存储在相同桶中发生冲突的元素，但这是一个不同的问题，不是哈希表和哈希映射之间区别的一部分。

- Tony Delroy

一个有效的观点，但回到重点，“...这只是术语”。你的HashTable不是我所说的数据结构HashTable。同样，你的HashMap也不是我所指的通过哈希键抽象映射，而更像我所知道的HashTable，除了“不暗示支持键和值的区分或分离”。顺便说一句，这实际上对我来说没有意义。为什么你想要一个像HashTable或HashSet这样的查找数据结构，却没有区分键的存在检查呢？ - makadev

@makadev：“这只是术语” - 共享数据结构、设计模式等术语的理解，让我们能够简洁而有意义地描述和讨论系统。你编写的系统越多，需要帮助维护、演进或使用的人就越多，这点就越重要。无论如何，“为什么你想要一个查找数据结构，比如哈希表或哈希集合，没有区分键值 - 例如用于存在性检查？”- 哈希集合可能存储文本文件中出现的单词：没有明确的键与值 - 每个单词既是键又是值。并不是说word1与word2不可区分。 - Tony Delroy

-2

实际上，HashTable已经过时了，使用HasHMap是最好的方法，因为HashTable是同步的。如果不需要线程安全的实现，则建议使用HashMap代替HashTable。如果需要线程安全的高并发实现，则建议使用java.util.concurrent.ConcurrentHashMap代替HashTable。

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

- Yasir Shabbir Choudhary

2

该问题并不特定于Java。 - Revanth Kumar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- makadev · Accepted Answer

在计算机科学中，由于措辞的不同，有所区别。

哈希表是一种使用键哈希来查找相应值的表格状数据结构。这只是一种键值映射的形式之一。可能会有不同的实现方式，如不同的哈希函数、哈希碰撞解决方案和表格增长策略等等。只有在需要自己创建哈希表时才会感到有趣。

哈希映射是一种使用哈希键的键值对映射。映射本身是抽象的，可能不是一个表格。平衡树、tries或其他数据结构/映射也是可能的。

你可以简单地说哈希表是底层数据结构，哈希映射可能利用了哈希表。

字典是另一种抽象级别，因为它可能根本不使用哈希——例如使用全文二进制搜索查找或其他比较方式。这些都是在不考虑特定编程语言的情况下，能够从这些词中得到的内容。

-- 在过多思考之前，你能否确定面试官是否真正了解他/她所谈论的内容？你们讨论了技术细节，还是他们只是听/问并偶尔发表评论？有时面试官会对他们首先不真正了解的问题提出最荒谬的答案。就像你自己写的那样，通常只是术语。软件开发人员经常可以互换使用这些术语，除了可能在Java等编程语言中确实存在差异的情况。