本文概述
- 为什么要使用HashTable?
- 哈希表的应用
哈希表中的每个位置称为插槽, 可以容纳一个项目, 并由一个从0开始的整数值命名。
项与该项在哈希表中所属的插槽之间的映射称为哈希函数。哈希函数接受键并返回其哈希编码或哈希值。
假设我们有一组整数54、26、93、17、77、31。我们要求作为“余数方法”的第一个哈希函数只是简单地获取该项并将其除以表大小, 然后将余数作为其哈希值返回, 即
h item = item % (size of table) Let us say the size of table = 11, then54 % 11 = 1026 % 11 = 493 % 11 = 517 % 11 = 677 % 11 = 031 % 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的空间将会浪费。
哈希表的应用 【哈希表的介绍和引用】哈希表的一些应用是:
- 数据库系统:特别是那些需要有效随机访问的数据库。通常, 数据库系统尝试在两种类型的访问方法之间进行开发:顺序访问和随机访问。哈希表是高效随机访问的组成部分, 因为它们提供了一种在固定时间内定位数据的方法。
- 符号表:编译器用来维护程序符号信息的表。编译器经常访问有关符号的信息。因此, 必须非常有效地实现符号表。
- 数据字典:支持添加, 删除和搜索数据的数据结构。尽管哈希表和数据字典的操作类似, 但是其他数据结构也可以用于实现数据字典。
- 关联数组:关联数组由排列的数据组成, 这样一个数组的第n个元素对应于另一个数组的第n个元素。关联数组有助于通过几个关键字段为数据的逻辑分组建立索引。
推荐阅读
- C# HashSet类介绍和用法示例
- PHP如何使用Ds\Map count()函数(代码实例)
- PHP如何使用DS\Map clear()函数(用法示例)
- Java如何使用TreeMap(解析和用法示例)
- C++如何使用STL中的map find()函数(示例)
- C++ STL中的unordered_map用法指南
- PHP Ds Map capacity()函数用法示例
- PHP Ds Map diff()函数用法解读
- 数据结构(在Scala中的HashSet用法指南)