1

如果我们在使用键时unordered_map定义hash和函子。preduser-defined

地图的模板语法如下：

template < class Key,                                     // map::key_type
       class T,                                           // map::mapped_type
       class Compare = less<Key>,                         // map::key_compare
       class Alloc = allocator<pair<const Key,T> >       // map::allocator_type
       > class map;

在 map 的情况下，没有hash和predfunctors 选项。在map. 如果发生碰撞，那么为什么我们没有像 in 中的hashandpred函子unordered_map呢？我在这里错过了什么吗？

4

2 回答 2

5

std::map不是哈希表，因此不使用哈希函数。相反，它需要operator<对地图中包含的值进行排序。

于 2019-09-26T12:21:21.797 回答
5

std::map并且std::unordered_map是两种不同类型的容器，它们都提供了键值对映射。他们如何做到这一点是完全不同的。

std::map使用树结构来实现。通常这是一个 RBTree，但任何可以保证最坏情况O(logN)操作的树都可以工作。这意味着它只需要一个键类型的比较运算符，因为您可以获得总排序并使用实现严格弱排序的比较器检查是否相等。这意味着您永远不会发生哈希冲突，因为您没有使用哈希。

std::unordered_map基于哈希表实现。由于它对密钥进行哈希处理，因此您需要一个哈希运算符。您还需要一个比较运算符，因为两个值可以散列到相同的值（散列冲突）。如果没有比较运算符，您将无法判断重复哈希是否真的是重复项。

于 2019-09-26T12:25:42.827 回答