哈希表的介绍和引用

本文概述

  • 为什么要使用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?
  1. 如果U(键的Universe)较大, 则可能无法存储大小为[U]的表T。
  2. 密钥组k相对于U可能较小, 因此分配给T的空间将会浪费。
因此, 哈希表需要较少的存储空间。密钥为k的间接寻址元素通过散列存储在插槽k中, 哈希存储在h(k)中, 其中h为哈希fn, 哈希(k)为密钥k的值。哈希fn所需的数组范围。
哈希表的应用 【哈希表的介绍和引用】哈希表的一些应用是:
  1. 数据库系统:特别是那些需要有效随机访问的数据库。通常, 数据库系统尝试在两种类型的访问方法之间进行开发:顺序访问和随机访问。哈希表是高效随机访问的组成部分, 因为它们提供了一种在固定时间内定位数据的方法。
  2. 符号表:编译器用来维护程序符号信息的表。编译器经常访问有关符号的信息。因此, 必须非常有效地实现符号表。
  3. 数据字典:支持添加, 删除和搜索数据的数据结构。尽管哈希表和数据字典的操作类似, 但是其他数据结构也可以用于实现数据字典。
  4. 关联数组:关联数组由排列的数据组成, 这样一个数组的第n个元素对应于另一个数组的第n个元素。关联数组有助于通过几个关键字段为数据的逻辑分组建立索引。

    推荐阅读