量子哈希
在本文中，我们将简要介绍一些实际应用中用于查找的哈希算法。除了用于查找，哈希算法还在巨型字符串匹配中有着重要的应用，这时的哈希算法被称为滚动哈希，因为它需要能够滚动计算。设计一个优秀的哈希算法并不容易。对于应用来说，选择合适的算法是至关重要的。（哈希竞猜游戏搭建，开发。源码部署）基于高速访问设计的哈希表是一种典型的”空间换时间”方法。哈希表可以被理解为一个线性表，其中的元素并不是紧密排列的，而是可能存在间隙。哈希表基于关键码值，并且可以直接访问数据结构。换句话说，它通过将键值映射到表中的某个位置来访问记录，以加快查找速度。这个映射函数被称为哈希函数，而存储记录的数组被称为哈希表。
哈希函数还有另外一种含义。在实际中，哈希函数指的是将一个大范围映射到一个小范围的函数。将大范围映射到小范围的目的通常是为了节省空间，使得数据更容易保存。此外，哈希函数经常应用于查找操作。因此，在考虑使用哈希函数之前，需要了解它的几个限制：1. 哈希的主要原理是将大范围映射到小范围，因此输入的实际值的数量必须与小范围相当或更小，否则会出现很多冲突。2. 由于哈希函数是单向函数，因此可以用它来对数据进行加密。3. 不同的应用对哈希函数有不同的要求，例如，用于加密的哈希函数主要考虑与单向函数的差距，而用于查找的哈希函数主要考虑映射到小范围的冲突率。关于应用于加密的哈希函数已经有很多讨论，在作者的博客中有更详细的介绍。因此，本文将重点探讨用于查找的哈希函数。哈希函数的主要应用对象是数组（例如字符串），而其目标通常是一个int类型。以下内容将按照这种方式进行说明。
哈希函数可以使数据序列的访问过程更快、更准确。通过哈希函数，可以更快地定位数据元素：1. 直接寻址方法：使用关键字的值或关键字的线性函数作为哈希地址，即H(key)=key或H(key) = a·key + b，其中a和b是常数（这种散列函数称为自函数）。2. 数值分析方法：在分析一组数据时，例如一组员工的出生日期，我们发现出生日期的后几个数字大致相同。在这种情况下，冲突的可能性将非常大。然而，我们发现出生日期的最后几位数字表示月份和详细日期之间存在很大差异。如果使用这些数字来构造哈希地址，则冲突的概率将明显降低。因此，数值分析方法是找出数字规律，并尽可能使用这些数据来构造冲突概率较低的哈希地址。3. 平方取中法：以关键字平方后的低位数字作为哈希地址。4. 折叠方法：将关键字切分成几个相近的部分。最后一部分可能有不同的数字，然后将这些部分的叠加和（去掉进位）作为哈希地址。5. 随机数法：选择一个随机函数，将关键字的随机值作为哈希地址，常用于关键字长度不同的情况。6. 除留余数法：将关键字的余数除以不大于哈希表长度m的数字p作为哈希地址，即H(key) = key MOD p，其中p是一个质数。
