c++ - 为什么我们没有 map 的 hash 和 pred 仿函数？

Question

在 unordered_map 的情况下，我们在使用 user-defined 键时定义 hash 和 pred 仿函数.

map 的模板语法如下:

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 和 pred 仿函数选项。在 map 的情况下我们永远不会发生冲突吗？如果发生冲突，那么为什么我们不像 unordered_map 那样拥有 hash 和 pred 仿函数？ 我在这里遗漏了什么吗？

Answer 1

std::map 和 std::unordered_map 是两种不同类型的容器，它们都提供键值对映射。不过，他们的做法完全不同。

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

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