Hash 关联容器


类别：容器	组件类型：概念

描述

Hash 关联容器是实现为哈希表的关联容器。 [1] Hash 关联容器的元素并不一定按照任何有意义的顺序排列；特别是，它们没有进行排序。对 Hash 关联容器执行大多数操作的最坏情况复杂度根据容器的大小呈线性增长，但平均情况复杂度为常量时间；这意味着对于仅存储和检索值以及排序无意义的应用程序，Hash 关联容器通常比已排序关联容器快很多。

细化

关联容器

关联类型

除了关联容器要求中定义的类型外，还引入了以下新类型。

哈希函数	`X::hasher`	是哈希函数模型的类型。`X::hasher`参数类型必须为`X::key_type`.
键相等	`X::key_equal`	二元谓词，其参数类型是`X::key_type`。类型为`key_equal`的对象返回`true`（如果其参数是同一个键）且返回`false`（如果其参数不是同一个键）。`X::key_equal`必须是等价关系。

符号

`X`	是 Hash 关联容器模型的类型
`a`	X::value_type 类型`X`
`t`	X::value_type 类型`的对象`
`k`	X::value_type 类型`X::key_type`
`p`, `q`	X::value_type 类型`X::iterator`
`n`	X::value_type 类型`X::size_type`
`h`	X::value_type 类型`X::hasher`
`c`	X::value_type 类型`X::key_equal`

定义

Hash 关联容器的哈希函数X是参数类型为X::key_type返回值类型为size_t的一元函数。哈希函数必须是确定性的（也就是说，无论何时使用同一个参数调用该函数，它都必须始终返回相同的值），但哈希函数返回值应尽可能一致：理想情况下，没有两个键哈希到同一个值。 [2]

Hash 关联容器中的元素被组织到存储段中。Hash 关联容器使用哈希函数值确定一个元素被分配到哪个存储段。

Hash 关联容器中的元素个数除以存储段数称为负载因子。负载因子小的 Hash 关联容器比负载因子大的 Hash 关联容器快。

有效表达式

除了关联容器中定义的表达式外，还必须满足以下表达式。

名称	表达式	返回类型
默认构造函数	X() X a;
含存储段数的构造函数	X(n) X a(n);
含哈希函数的构造函数	X(n, h) X a(n, h);
含键相等的构造函数	X(n, h, k) X a(n, h, k);
哈希函数	`a.hash_funct()`	`X::hasher`
键相等	`a.key_eq()`	`X::key_equal`
删除键	`a.erase(k)`	`size_type`
删除元素	`a.erase(p)`	`void`
删除范围	`a.erase(p, q)`	`void`
查找	`a.find(k)`	`迭代器`if`a`可变，否则`const_迭代器`
计数	`a.count(k)`	`size_type`
相等范围	`a.equal_range(k)`	`pair<迭代器、迭代器>`if`a`可变，否则`pair<const_迭代器、const_迭代器>`.
分段计数	`a.bucket_count()`	`X::size_type`
大小改变	`a.resize(n)`	`void`

表达式语义

名称	表达式	前提条件	语义	后置条件
默认构造函数	X() X a;		利用`hasher()`作为哈希函数，`key_equal()`作为键相等函数，创建一个空的容器。	容器的大小为`0`。Bucket 计数是一个未指定的默认值。哈希函数为`hasher()`，键相等函数为`key_equal()`.
含存储段数的构造函数	X(n) X a(n);		使用`n`创建至少拥有`hasher()`作为哈希函数，`key_equal()`作为键相等函数，创建一个空的容器。	容器的大小为`0`个 bucket 的空容器。Bucket 计数大于或等于`n`。哈希函数为`hasher()`，键相等函数为`key_equal()`.
含哈希函数的构造函数	X(n, h) X a(n, h);		使用`n`创建至少拥有`h`作为哈希函数，`key_equal()`作为键相等函数，创建一个空的容器。	容器的大小为`0`个 bucket 的空容器。Bucket 计数大于或等于`n`。哈希函数为`h`，键相等函数为`key_equal()`.
含键相等的构造函数	X(n, h, k) X a(n, h, k);		使用`n`创建至少拥有`h`作为哈希函数，`k`作为键相等函数，创建一个空的容器。	容器的大小为`0`个 bucket 的空容器。Bucket 计数大于或等于`n`。哈希函数为`h`，键相等函数为`k`.
哈希函数	`a.hash_funct()`		返回`a`.
键相等	`a.key_eq()`		使用的哈希函数`a`.
删除键	`a.erase(k)`		返回`k`使用的键相等函数`a`销毁键与`a.count(k)`.	`相同的元素并从`中移除。 [2] 返回值是被擦除的元素数量（即旧的`a.count(k)`. `a`a.size()`k`.
删除元素	`a.erase(p)`	`p`值减少`a`.	不包含键为`p`的元素`a`.	`相同的元素并从`是
删除范围	`a.erase(p, q)`	`中可取消引用的迭代器`销毁`a`.	指向的元素并从`中移除。减少了 1。`[p, q)`a`.	`相同的元素并从`是`中的有效范围`销毁范围`[p,q)`.
查找	`a.find(k)`		中的元素并从`k`中移除。从`减少`i	到`减少`j`k`.
计数	`a.count(k)`		返回一个指向键与`a`相同的元素的迭代器，或`k`.
相等范围	`a.equal_range(k)`		a.end()`（如果不存在该类元素）。`返回值不是`，就是返回值键与`相同`a`相同的元素的迭代器，或`k`返回`k`中的元素数量	其键与`相同`返回对`P`满足`a.count(k)`[P.first, P.second)`p`值减少`a`是包含`a`中所有元素的范围。 [3] 如果没有任何元素的键与`，就是返回值键与`相同，则返回值为空范围。`之间的距离`P.first`k`.
分段计数	`a.bucket_count()`		和`a`.
大小改变	`a.resize(n)`		P.second`a`.	存储桶计数`a`将至少为`n`。指向元素的所有迭代器`a`依然有效。[3]

复杂性保证

具有存储桶计数的默认构造函数、具有哈希函数的构造函数以及具有键等效的构造函数，均为摊销常数时间。

散列函数和键等效是摊销常量时间。

删除键的平均复杂度为O(count(k))。最坏情况为容器大小的线性时间。

删除元素是摊销常数时间。

删除范围的平均复杂度为O(N)，其中N为要删除的范围的长度。最坏情况为容器大小的线性时间。

查找的平均复杂度为常数时间。最坏情况为容器大小的线性时间。

等值范围的平均复杂度为O(count(k))。最坏情况为容器大小的线性时间。

计数的平均复杂度为O(count(k))。最坏情况为容器大小的线性时间。

存储桶计数是摊销常数时间。

调整大小为容器大小的线性时间。

不变量

模型

注释

[1]有很多针对哈希表的文献。参见克努斯的第 6.4 节。(D. E. Knuth，计算机编程的艺术。第三卷：排序和搜索。艾迪生-韦斯利，1975 年。)

[2]如果散列函数不佳（即，许多不同的键散列到相同的值），那么这会影响性能。最坏情况是每个键都散列到相同的值；在此情况下，大多数散列关联容器操作的运行时复杂度为容器大小的线性时间。

[3]调整大小不会使迭代器失效；但是，它不一定保留迭代器之间的排序关系。即是中的有效范围返回对[p,q)为指向散列关联容器的迭代器，使得中的有效范围紧靠[p,q)之前，那么无法保证中的有效范围在容器调整大小后依然紧靠[p,q)之前。关于元素排序的唯一保证是连续存储不变量：具有相同键的元素始终彼此相邻。

另请参阅

关联容器、已排序关联容器、唯一的散列关联容器、多个散列关联容器，