本文重点介绍：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) 时间，但输入的数量可能足够小，可以忽略此时间)，对于大量数据，首选哈希表。
欢迎任何形式的转载，但请务必注明出处，尊重他人劳动成果。
转载请注明：文章转载自 有区别网 [http://www.vsdiffer.com]
本文标题：哈希表与 STL 映射的区别
本文链接：https://www.vsdiffer.com/vs/hash-table-vs-stl-map.html
免责声明：以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性，因使用而带来的风险与本站无关！如本网站内容冒犯了您的权益，请联系站长，邮箱：，我们核实并会尽快处理。