1

在 C++ 中，对于每个无序关联容器（如unordered_map、unordered_set、unordered_multimap），我们需要定义一个哈希函数。正如维基百科所指出的，

struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
  }
};

struct hash_X是 的自定义散列函数struct X。但是这个函数有什么作用呢？为什么我们需要哈希函数？可以有任何其他类型的自定义散列函数吗？如果是这样，我们如何比较任何两个这样的功能之间的效率。

4

2 回答 2

3

散列函数的目标是将任意数据结构的内容映射到整数，这样您可能遇到的大多数项目映射到不同的整数，并且您可能遇到的完整项目集一起相遇在整数集合上均匀分布。unordered_map有了这样的功能，就可以很容易地构建一个快速查找任意项目的容器（例如）。

我意识到这个定义有点抽象。更具体地说，请考虑您在上面从 Wikipedia 中给出的示例。i它将结构的,j和字段异或k在一起以形成哈希值。这是一个有效的散列函数（它将结构合并为一个整数）。但是，如果i和j都k具有相似的值范围，那么它可能不是一个非常好的散列函数。例如，(1,2,3)两者(3,1,2)都将散列到相同的值。

一个理想的散列函数通常看起来更像一个随机数生成器：对于可预测的输入，它给出看似随机的输出。（但请记住，相同的输入必须始终给出相同的输出。）数据结构的最佳散列函数实际上取决于您将要散列的数据类型。

这套讲义看起来涵盖了大部分要点： http ://www.cs.cornell.edu/Courses/cs312/2008sp/lectures/lec21.html

你可以通过谷歌搜索找到其他人。

于 2013-12-07T02:38:42.033 回答
1

简短的回答：非常快速地查找元素。

与将元素存储到某种形式red-black trees（或另一个 AVL 树）中的有序容器相反，无序容器indexed buckets用于包含节点。按索引检索存储桶具有O(1)复杂性。

Hash function是一个函数，它接受一个元素并将其转换为这样的整数索引。

因此，由于索引的域小于所有元素的域，collision可能会出现更多的元素可以放入一个桶中，从而降低元素查找的有效性。因此，最小的冲突概率绝对是哈希函数要争取的属性。另一个应该是哈希计算的有效性。

有关更多分析，请参见完美哈希函数

于 2013-12-07T02:38:04.410 回答