哈希表与 STL 映射的区别

本文重点介绍：Hash表 和 STL Map 的比较和区别。 哈希表是如何实现的？ 如果输入的数量很少，可以使用哪些数据结构来代替哈希表？

哈希表

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

• 值不按排序顺序存储。
• 由于哈希表使用键来查找将存储值的索引，因此可以在平均 O(1) 时间内完成插入或查找(假设哈希表中的冲突很少)。
• 在哈希表中，还必须处理潜在的冲突。 这通常通过链接来完成，这意味着创建其键映射到特定索引的所有值的链接列表。

哈希表的实现：传统上，哈希表是用一个链表数组实现的。 当我们想要插入一个键/值对时，我们使用散列函数将键映射到数组中的索引。 然后将该值插入到该位置的链表中。

注意：链表中数组特定索引处的元素不具有相同的键。 相反，哈希函数(键)对于这些值是相同的。 因此，为了检索特定键的值，我们需要在每个节点中存储确切的键和值。

总而言之，哈希表将使用链表数组实现，链表中的每个节点都保存两条数据：值和原始键。 此外，需要注意以下设计标准：

• 希望使用一个好的散列函数来确保键分布良好。 如果它们没有很好地分布，那么会遇到很多碰撞，并且找到元素的速度会下降。
• 不管哈希函数有多好，我们仍然会遇到冲突，所以我们需要一种方法来处理它们。 这通常意味着通过链表链接，但这不是唯一的方法。
• 可能还希望实现根据容量动态增加或减少哈希表大小的方法。 例如，当元素个数与表大小的比值超过某个阈值时，可能希望增加哈希表大小。这意味着创建一个新的哈希表并将条目从旧表传输到新表。 因为这是一项昂贵的操作，我们要小心不要太频繁地这样做。

STL映射

容器映射是包含在 C++ 标准库中的关联容器。 这个类的定义在命名空间std的头文件“map”中。

STL Map内部实现：
它被实现为一个自平衡的红黑树。 最常见的两种自平衡树可能是红黑树和 AVL 树。 为了在插入/更新后平衡树，两种算法都使用旋转的概念，其中树的节点被旋转以执行重新平衡。 虽然在这两种算法中，插入/删除操作都是 O(log n)，但在红黑树重新平衡旋转的情况下，这是一个 O(1) 操作，而对于 AVL，这是一个 O(log n) 操作，使得 RB树在这方面的效率更高是sage的再平衡和更常用的可能原因之一。

哈希表和 STL 映射的区别

• 空键：STL Map 允许一个空键和多个空值，而哈希表不允许任何空键或空值。
• 线程同步：如果不需要线程同步，映射通常优于哈希表。 哈希表已同步。
• 线程安全：STL Maps 不是线程安全的，而 Hashmap 是线程安全的，可以与多个线程共享。
• 值顺序：在 STL 映射中，值按排序顺序存储，而在哈希表中，值不按排序顺序存储。
• 搜索时间：对于较小的数据，可以使用 STL Map 或二叉树(虽然需要 O(log n) 时间，但输入的数量可能足够小，可以忽略此时间)，对于大量数据，首选哈希表。