如何在地图中存储值？

Question

在std :: unordered_map中存储了密钥的哈希，以便它可以在O（1）中找到我们的值，但是如果2个不同的密钥（例如，密钥的类型为string）的哈希彼此相等怎么办？能带来问题吗？在此先感谢）

Answer 1

这被称为冲突。这也是我们在谈论哈希映射时谈论“ buckets”的原因，因为在同一“ bucket”中包含多个具有相同哈希值的键是完全正常的。

这意味着lookup始终是一个两个阶段的过程：

1. 找到正确的存储桶。
2. 在存储桶中查找密钥。

还要注意，即使具有不同哈希值的键仍可以保留在同一存储桶中，因为哈希值通常大于表的大小，因此哈希表将哈希进一步减小为较小的大小，例如通过对表格的大小取模。

有多种不同的策略可以处理，最受欢迎的两种是：

• Separate Chaining：存储桶本身就是另一个集合，例如列表或树。 （通常是一个列表。）这意味着查找整个哈希表的最坏情况步骤复杂度是查找存储桶数据结构的最坏情况下步骤复杂度，例如如果是列表，则为O（n），最坏的情况是所有键都具有相同的哈希值。 （通常选择一个列表是因为它非常简单，而其他数据结构虽然略微加快了查找速度，但通常它们的插入操作要复杂得多，因此会降低速度。）
• Open Addressing：我们没有在一个存储桶中放置多个条目，而是搜索了一个空存储桶。有多种策略：
  • 线性探测：尝试下一个存储桶，然后再尝试下一个，再尝试下一个，依此类推。
  • Quadratic Probing：尝试下一个存储桶，然后尝试第四个，第九个，第十六个，依此类推。
  • Double Hashing：使用第二个哈希函数，并尝试第1 * hash2(key)，2 * hash2(key)，3 * hash2(key)，4 * hash2(key)个存储桶，依此类推。

[在两种情况下，您都需要定期重新调整哈希表的大小。在第二种情况下，仅仅是因为在某个时候它将充满。在第一种和第二种情况下，都可以使存储桶更小，搜索速度更快。

如果使用指数大小调整，则通常仍具有O（1）的摊销最坏情况步骤复杂度，用于插入，删除和查找。