哈希表 vs STL Map

本文比较和对比了哈希表和 STL Map。哈希表是如何工作的？如果输入数量很少，除了哈希表之外，还可以使用哪些数据结构选项？

哈希表

哈希表通过在键上调用哈希函数来存储值。

• 这些值不以排序顺序存储。
• 此外，由于哈希表使用键来定位将保存值的索引，因此插入或查找可以在分摊的 O(1) 时间内完成（假设哈希表中的冲突很少）。
• 哈希表还必须处理潜在的冲突。这通常通过链式实现，即为所有键映射到特定索引的值创建链表。

哈希表的实现：哈希表传统上使用链表数组实现。当我们想要插入键/值对时，我们使用哈希函数将键映射到数组中的索引。然后将值放置在链表中该位置。数组特定索引处的链表元素不具有相同的键。相反，对于所有这些值，哈希函数（键）是相同的。因此，为了检索特定键的值，我们必须在每个节点中同时存储确切的键和值。总而言之，哈希表将使用链表数组实现，每个节点包含两个数据：值和原始键。此外，应考虑以下设计标准：

• 为了确保键均匀分布，我们希望使用一个好的哈希函数。如果它们不均匀分布，我们将有很多冲突，并且查找元素的速度会变慢。
• 无论哈希函数有多好，我们仍然会有冲突，因此我们需要一种处理它们的方法。这通常通过使用链表来实现，但这并非唯一的方法。
• 我们可能还希望包含根据容量动态增加或减少哈希表大小的方法。例如，如果元素与表大小之比超过某个阈值，我们可能希望增加哈希表的大小。这需要创建一个新的哈希表并将旧表中的条目复制到新表。我们希望避免过于频繁地执行此过程，因为它成本很高。

STL MAP

容器 map 是 C++ 标准库的一部分，是一个关联容器。此类的定义在命名空间 std 的头文件“map”中。内部 STL Map 实现：它实现为红黑自平衡树。最常见的两种自平衡树可能是红黑树和 AVL 树。为了在插入/更新后重新平衡树，两种算法都采用旋转的概念，其中树的节点被旋转。虽然两种算法中的插入/删除操作都是 O(log n)，但在红黑树的重新平衡中，旋转是 O(1) 操作，而 AVL 则是 O(log n) 操作，这使得红黑树在重新平衡方面更有效，也是它更常用的可能原因之一。

哈希表与 STL map：有什么区别？

• 空键： STL Map 可以有一个空键和多个空值，而哈希表不能有空键或空值。
• 线程同步： 如果不需要线程同步，通常优先选择 map 而不是哈希表。哈希表已经同步。
• STL Map 不是线程安全的，而 Hashmap 是线程安全的，可以被多个线程共享。
• 值顺序： STL map 中的值按排序顺序存储，而哈希表中的值不按排序顺序存储。
• 搜索时间： 对于较小的数据（尽管它需要 O(log n) 时间，但输入数量可能很小，使此时间可以忽略不计），可以使用 STL Map 或二叉树；对于较大的数据，可以使用哈希表。

让我们看看表格中的差异 -