r 哈希表与 STL 映射的区别

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

哈希表

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

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

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

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

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

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

STL映射

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

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

哈希表和 STL 映射的区别

  • 空键:STL Map 允许一个空键和多个空值,而哈希表不允许任何空键或空值。
  • 线程同步:如果不需要线程同步,映射通常优于哈希表vSDiFFER。 哈希表已同步。
  • 线程安全: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
免责声明:以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性,因使用而带来的风险与本站无关!如本网站内容冒犯了您的权益,请联系站长,邮箱: ,我们核实并会尽快处理。