哈希表与STL映射

本文的重点是：比较和对比哈希表和STL映射。哈希表是如何实现的？如果输入的数量很小，可以使用哪些数据结构选项来代替哈希表？

哈希表

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

• 值不是按排序顺序存储的。
• 此外，由于哈希表使用键来查找将存储值的索引，因此插入或查找可以在摊销O（1）时间内完成（假设哈希表中几乎没有冲突）。
• 在哈希表中，还必须处理潜在的冲突。这通常是由 锁链 ，这意味着创建一个链接列表，其中包含键映射到特定索引的所有值。

哈希表的实现： 传统上，哈希表是通过链表数组实现的。当我们想要插入一个键/值对时，我们使用哈希函数将键映射到数组中的一个索引。然后将该值插入该位置的链表中。 注： 链表中数组特定索引处的元素没有相同的键。相反，这些值的哈希函数（键）是相同的。因此，为了检索特定密钥的值，我们需要在每个节点中存储确切的密钥和值。

总之，一个哈希表将由一组链表实现，链表中的每个节点都包含两个数据：值和原始键。此外，我们还需要注意以下设计标准：

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

STL地图

容器映射是包含在 C++标准库 .此类的定义位于命名空间std的头文件“map”中。

STL映射内部实现： 它被实现为一棵自平衡的红黑树。最常见的两种自平衡树可能是 红黑树 和 平衡二叉树 .为了在插入/更新后平衡树，两种算法都使用旋转的概念，其中旋转树的节点以执行重新平衡。虽然在这两种算法中，插入/删除操作都是O（logn），但在红黑树的情况下，重新平衡旋转是O（1）操作，而在AVL中，这是O（logn）操作，这使得RB树在重新平衡sage的这方面更有效，这也是更常用的可能原因之一。

哈希表和STL映射的区别

1. 空键： STL映射允许一个空键和多个空值，而哈希表不允许任何空键或值。
2. 线程同步： 如果不需要线程同步，Map通常比hash表更受欢迎。哈希表是同步的。
3. 线程安全： STL映射不是线程安全的，而Hashmaps是线程安全的，可以与多个线程共享。
4. 价值顺序： 在STL映射中，值是按排序顺序存储的，而在哈希表中，值不是按排序顺序存储的
5. 搜索时间： 对于较小的数据，可以使用STL映射或二叉树（虽然需要O（logn）时间，但输入的数量可能很小，可以忽略不计），对于大量数据，首选哈希表。

相关文章

• BST相对于hashmap的优势
• Java中HashMap和HashTable的区别

本文由 布拉马尼赛 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。