为什么我们没有地图的哈希和捕食函子？

Question

在的情况下，unordered_map我们定义了hash和pred每当我们使用仿函数user-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，则没有hashand predfunctors选项。我们永远不会发生碰撞的情况map。如果发生冲突，那为什么不使用hash和pred函数unordered_map呢？我在这里想念什么吗？

Answer 1

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

Answer 2

std::map和std::unordered_map两种不同类型的容器，无论提供关键值对的映射。他们如何做到这一点却完全不同。

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

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