哈希表和散列表的区别引起混淆

Question

我有一个疑问：

我在很多帖子中读到，哈希表（Hash-maps）是作为二叉搜索树实现的，这使得各种操作的时间复杂度达到了对数级别。

而另一方面，哈希表（Hashtables）提供了常量时间获取。

但是，正如我在此贴中所读到的，就检索/搜索两个数据结构中的元素而言，没有提供任何不同之处。

所以，我的问题是 -

既然哈希表保证了提供恒定的搜索时间复杂度，那么它们的实现必须与哈希图的实现不同。 那么，如果哈希表不能提供常量时间搜索，为什么会有人使用哈希图？而且，它们为什么首先被实现为二叉搜索树？

我知道哈希图将键存储在排序形式中并提供了地图遍历功能。 但是，哈希表也可以提供相同的功能。

- Sankalp

---

在重新打标签之前，该问题既没有提到Java也没有提到C ++，但始终使用Java术语，并链接到一个特定于Java的问题。如果您从一开始就正确地对问题进行标记（并最好使用有关所询问语言的标准术语），这将有助于避免混淆。 - NPE

Answer 1

你的困惑源于以下内容：

哈希映射是通过二叉搜索树实现的

事实并非如此。没有一个合理的命名约定会使用“hashmap”这个术语来描述基于树的结构。

例如，在Java中，HashMap 是基于哈希表实现的，而 TreeMap 是基于树实现的。

C++ 标准容器的命名中既没有“hash”，也没有“tree”。与 HashMap 和 TreeMap 大致对应的两个容器分别是 std::unordered_map 和 std::map。

- NPE