哈希表

它是一组以某种方式存储的项的集合，以便以后可以轻松找到它们。

哈希表中的每个位置都称为槽，可以容纳一个项目，并以从0开始的整数值命名。

项目与哈希表中项目所属的槽之间的映射称为哈希函数。 哈希函数接受一个键并返回其哈希编码或哈希值。

假设我们有一组整数 54、26、93、17、77、31。 我们的第一个哈希函数需要是“余数法”，只需将项目除以表大小，然后返回余数作为其哈希值，即

现在，当我们需要搜索任何元素时，我们只需要将其除以表的大小，就可以得到哈希值。 因此，我们得到 O (1) 搜索时间。

现在取更多一个元素 44，当我们对 44 应用哈希函数时，我们得到 (44 % 11 = 0)，但 0 哈希值已经有一个元素 77。这个问题称为冲突。

冲突： 根据哈希函数，两个或多个项目需要在同一个槽中。 这被称为冲突。

图： 使用哈希函数 h 将键映射到哈希表槽。 因为键 K2 和 k5 映射到同一个槽，所以它们发生冲突。

为什么使用哈希表？

1. 如果 U（键的宇宙）很大，则存储大小为 [U] 的表 T 可能是不可能的。
2. 键的集合 k 相对于 U 可能很小，因此为 T 分配的空间将浪费。

因此，哈希表需要的存储空间更少。 使用键 k 的间接寻址元素存储在槽 k 中，使用哈希处理存储在 h (k) 中，其中 h 是哈希 fⁿ，hash (k) 是键 k 的值。 哈希 fⁿ 需要数组范围。

哈希表的应用

哈希表的一些应用是

1. 数据库系统： 特别是那些需要高效随机访问的系统。 通常，数据库系统尝试在两种类型的访问方法之间进行开发：顺序和随机。 哈希表是高效随机访问的组成部分，因为它们提供了一种在恒定时间内定位数据的方法。
2. 符号表： 编译器利用的表，用于维护程序中有关符号的数据。 编译器经常访问有关符号的信息。 因此，必须非常有效地实现符号表。
3. 数据字典： 支持添加、删除和搜索数据的数据结构。 尽管哈希表和数据字典的操作相似，但可以使用其他数据结构来实现数据字典。
4. 关联数组： 关联数组由排列的数据组成，以便一个数组的第 n^个 元素对应于另一个数组的第 n^个 元素。 关联数组对于通过多个键字段索引数据的逻辑分组很有用。