10.2.3　哈希查找

10.2.3　哈希查找

哈希查找（Hash Search）算法通过哈希地址函数实现对存储结构里的每个元素赋予唯一地址值的方法来实现哈希表的构建，并通过元素与地址的一一对应关系进行查找。该算法查找速度很快，缺点是需要存储元素对应的地址。

哈希地址函数最常用的可以采用取余数方式来实现，其公式为元素%n（求余），其中n为元素个数。

用Python语言实现哈希查找算法，主要分三步进行：

第一步，用给定的哈希函数求每个元素对应的哈希地址，本书采用取余数求地址方法，并作为键，而对应元素作为值，存储到字典里——构建对应的哈希表；

第二步，若哈希地址发生冲突——出现重复地址现象，则可以通过地址增1方式试探性解决问题；

第三步，在哈希表里通过哈希地址查找对应的元素。

代码文件：10_2_3_HashRearch.py

(https://www.daowen.com)

上述代码执行结果如下：

在元素重复数值不多的情况下，适合用求余函数求哈希地址；若元素值重复率比较高，则需要采用其他哈希函数来求地址，确保地址之间低冲突，以提高算法效率。常见的求地址的哈希函数还包括数字折叠法、直接定址法、平方取中法、随机数法等，感兴趣的读者可以查阅相关资料。

说明

（1）哈希查找算法在分布式数据库寻址等方面有实际应用。

（2）哈希查找算法最大特点：元素和地址存在一对一映射关系，由此查找效率很高。