哈希表和STL映射的区别

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

Hash table

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

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

哈希表的实现:哈希表传统上是用一个链表数组来实现的。当我们想插入键/值对时，我们使用哈希函数将键映射到数组中的索引。然后该值被插入到链表的那个位置。注意:链表中位于数组特定索引处的元素没有相同的键。相反，对于这些值，散列函数(key)是相同的。因此，为了检索特定键的值，我们需要在每个节点中存储确切的键和值。总结一下，哈希表将使用一个链表数组来实现，其中链表中的每个节点都保存着两段数据:值和原始键。此外，我们还需要注意以下设计标准:

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

STL Map

容器映射是c++标准库中包含的一种关联容器。这个类的定义在命名空间std. STL map内部实现的头文件“map”中:它被实现为一个自平衡的红黑树。最常见的两种自平衡树可能是红黑树和AVL树。为了在插入/更新之后平衡树，两种算法都使用了旋转的概念，即旋转树的节点来执行重新平衡。虽然在这两种算法中，插入/删除操作都是O(log n)，但在红黑树重新平衡旋转的情况下是O(1)操作，而在AVL中是O(log n)操作，这使得RB树在重新平衡sage方面更高效，这也是更常用的可能原因之一。

哈希表和STL映射的区别

1. 空键:STL Map允许一个空键和多个空值，而哈希表不允许任何空键或值。
2. 线程同步:如果不需要线程同步，通常首选Map而不是hash table。哈希表同步。
3. 线程安全:STL map不是线程安全的，而hashmap是线程安全的，可以被多个线程共享。
4. 值顺序:在STL映射中，值是按排序顺序存储的，而在哈希表中，值不是按排序顺序存储的
5. 搜索时间:对于较小的数据，您可以使用STL Map或二叉树(虽然它需要O(log n)时间，但输入的数量可能小到可以忽略不计)，对于大量的数据，首选哈希表。

让我们用表格的形式来看看它们的区别: