std::unordered_set/std::unordered_map中KeyEqual的使用价值

Question

我知道这个问题可能有些模糊，但我想知道在std的哈希容器中自定义比较器什么时候会很有用。

我知道在有序容器中它很有用，但对于哈希容器来说似乎有点奇怪。原因是根据比较器相等的元素的哈希值需要相同，并且我认为在大多数情况下，这实际上意味着将查找/插入元素转换为某种公共表示形式(更快且更容易实现)。

例如： - 不区分大小写字符串集合：如果要正确地进行哈希，您需要将整个字符串转换为大写/小写。 - 分数集合（其中2/3 == 42/63）：您需要将42/63转换为2/3，然后对其进行哈希...

所以我想知道是否有人可以提供一些自定义std :: unordered_模板参数的实际用途的示例，这样我就可以在编写未来代码时识别这些模式。 注意1：“对称论”（std::map使比较器可定制，因此std::unordred_也应该是可定制的）是我考虑过的，我不认为它有说服力。 注意2：为简洁起见，我在帖子中混合了2种比较器(<和==)，我知道std::map使用<，std::unordered_map使用==。

- NoSenseEtAl

---

你的一个说法是错误的。假设你将分数存储为一对整数，并且{a，b}的哈希函数是std::hash<float>(static_cast<float>(a)/b)。为什么在哈希之前需要将{42, 63}转换为{2,3}？ - JaMiT

Answer 1

根据https://en.cppreference.com/w/cpp/container/unordered_set，内部元素并没有按特定顺序排序，而是组织成桶。一个元素被放置在哪个桶中完全取决于其值的哈希。这样可以快速访问单个元素，因为一旦计算出哈希值，它就指向确切的桶。

因此，哈希函数定义了元素所在的桶，但一旦确定了桶，为了找到元素，将使用运算符 == 。

基本上，运算符 == 用于解决哈希冲突，因此需要使您的哈希函数和运算符 == 一致。此外，如果您的运算符 operator == 表明两个元素相等，则集合不允许重复。

对于自定义，我认为不区分大小写的 set 的 string 是一个很好的想法：给定两个字符串，您需要提供不区分大小写的哈希函数以允许 set 确定要存储字符串的桶。然后，您需要提供自定义的 KeyEqual 以允许set实际检索元素。

我曾经处理过的一个案例是允许用户插入字符串，保持其插入顺序但避免重复。因此，给定这样的结构：

struct keyword{
  std::string value;
  int sequenceCounter;
};

你想根据 {{value}} 检测重复项。我想到的一个解决方案是使用带有自定义比较器/哈希函数的 {{unordered_set}}，仅使用 {{value}}。这允许我在允许插入之前检查键是否存在。

- CuriouslyRecurringThoughts

Answer 2

一个有趣的用途是为给定对象集定义内存高效的索引（数据库术语）。

示例

假设我们有一个程序，其中包含一个由这个类的N个对象组成的集合：

struct Person {
    // each object has a unique firstName/lastName pair
    std::string firstName;
    std::string lastName;

    // each object has a unique ssn value
    std::string socialSecurityNumber;

    // each object has a unique email value
    std::string email;
}

我们需要通过任何唯一属性的值高效地检索对象。

实现比较

时间复杂度是在字符串比较为常数时间（字符串长度有限）的情况下给出的。

1）单个unordered_map

使用单个键（例如email）索引的单个map：

最初的回答

std::unordered_map<std::string,Person> indexedByEmail;

• 时间复杂度：查找除email以外的任何唯一属性都需要遍历映射表：平均O(N)。
• 内存使用：重复使用email值。这可以通过使用具有自定义哈希和比较的单个set来避免（请参见3）。

2) 多个unordered_map，没有自定义哈希和比较

对于每个唯一属性都有一个映射表，并且使用默认哈希和比较：

std::unordered_map<std::pair<std::string,std::string>, Person> byName;
std::unordered_map<std::string, const Person*> byEmail;
std::unordered_map<std::string, const Person*> bySSN;

• 时间复杂度：通过使用适当的映射，任何唯一属性的查找平均为O(1)。
• 内存使用：低效，因为所有字符串都会被复制。

3) 多个unordered_set，自定义哈希和比较：

通过自定义哈希和比较，我们可以定义不同的unordered_set，它们只会对对象的特定字段进行哈希和比较。这些集合可以用来执行查找，就像在2中存储项目一样，但不会复制任何字段。

"Original Answer" 翻译成 "最初的回答"

using StrHash = std::hash<std::string>;
// --------------------
struct PersonNameHash {
    std::size_t operator()(const Person& p) const {
        // not the best hashing function in the world, but good enough for demo purposes.
        return StrHash()(p.firstName) + StrHash()(p.lastName);
    }
};
struct PersonNameEqual {
    bool operator()(const Person& p1, const Person& p2) const {
        return (p1.firstName == p2.firstName) && (p1.lastName == p2.lastName);
    }
};
std::unordered_set<Person, PersonNameHash, PersonNameEqual> byName;

// --------------------
struct PersonSsnHash {
    std::size_t operator()(const Person* p) const {
        return StrHash()(p->socialSecurityNumber);
    }
};
struct PersonSsnEqual {
    bool operator()(const Person* p1, const Person* p2) const {
        return p1->socialSecurityNumber == p2->socialSecurityNumber;
    }
};
std::unordered_set<const Person*, PersonSsnHash, PersonSsnEqual> bySSN;

// --------------------
struct PersonEmailHash {
    std::size_t operator()(const Person* p) const {
        return StrHash()(p->email);
    }
};
struct PersonEmailEqual {
    bool operator()(const Person* p1, const Person* p2) const {
        return p1->email == p2->email;
    }
};
std::unordered_set<const Person*,PersonEmailHash,PersonEmailEqual> byEmail;

• 时间复杂度：通过任何唯一属性进行查找仍然是平均O(1)。
• 内存使用：比2）要好得多：没有string重复。

现场演示

- Vincent Saulue-Laborde

Answer 3

哈希函数本身以某种方式提取特征，比较器的工作是区分特征是否相同
使用数据的“外壳”，您可能不需要修改比较器
简而言之：在数据上放置一个特征外壳。 特征负责进行比较

事实上，我并不太理解您的问题描述。我的语言逻辑上不可避免地有些混乱。请理解。 :)

- zjw

---

我不明白你想说什么。也许你应该解释一下你的意思，而不是发明一个关于“shell”的含义，并期望其他人理解你没有写出来的东西？另外，最后一段基本上表明你在不理解问题的情况下回答了它；这很少会有好结果。 - JaMiT