本文概述
它是项目的集合, 其存储方式使以后可以轻松找到它们。
哈希表中的每个位置称为插槽, 可以容纳一个项目, 并由一个从0开始的整数值命名。
项与该项在哈希表中所属的插槽之间的映射称为哈希函数。哈希函数接受键并返回其哈希编码或哈希值。
假设我们有一组整数54、26、93、17、77、31。我们要求作为“余数方法”的第一个哈希函数只是简单地获取该项并将其除以表大小, 然后将余数作为其哈希值返回, 即
h item = item % (size of table)
Let us say the size of table = 11, then
54 % 11 = 10 26 % 11 = 4 93 % 11 = 5
17 % 11 = 6 77 % 11 = 0 31 % 11 = 9| 项目 | 哈希值 |
|---|---|
| 54 | 10 |
| 26 | 4 |
| 93 | 5 |
| 17 | 6 |
| 77 | 0 |
| 31 | 9 |
现在, 当我们需要搜索任何元素时, 只需将其除以表大小, 即可获得哈希值。这样我们得到了O（1）搜索时间。
现在, 当我们在44上应用哈希函数时, 再获取一个元素44, 我们得到（44％11 = 0）, 但是0哈希值已经具有元素77。此问题称为冲突。
碰撞：根据哈希函数, 同一插槽中将需要两个或多个项目。据说这叫做碰撞。
图：使用哈希函数h将键映射到哈希表插槽。由于密钥K2和k5映射到同一插槽, 因此它们会发生冲突。
为什么要使用HashTable？
- 如果U（键的Universe）较大, 则可能无法存储大小为[U]的表T。
- 密钥组k相对于U可能较小, 因此分配给T的空间将会浪费。
因此, 哈希表需要较少的存储空间。密钥为k的间接寻址元素通过散列存储在插槽k中, 哈希存储在h（k）中, 其中h为哈希fn, 哈希（k）为密钥k的值。哈希fn所需的数组范围。
哈希表的应用
哈希表的一些应用是：
- 数据库系统：特别是那些需要有效随机访问的数据库。通常, 数据库系统尝试在两种类型的访问方法之间进行开发：顺序访问和随机访问。哈希表是高效随机访问的组成部分, 因为它们提供了一种在固定时间内定位数据的方法。
- 符号表：编译器用来维护程序符号信息的表。编译器经常访问有关符号的信息。因此, 必须非常有效地实现符号表。
- 数据字典：支持添加, 删除和搜索数据的数据结构。尽管哈希表和数据字典的操作类似, 但是其他数据结构也可以用于实现数据字典。
- 关联数组：关联数组由排列的数据组成, 这样一个数组的第n个元素对应于另一个数组的第n个元素。关联数组有助于通过几个关键字段为数据的逻辑分组建立索引。
