hash(哈希)算法原理

在日常生活中,信息的重要性不言而喻,我们常常需要使用搜索引擎来解决日常生活中的大量问题,其中的一项关键技术就是数据查找算法。因此,如何提高数据查找的效率是我们不断追求的目标。

之前介绍了常见的基础查找算法。后面还会对深度优先搜索算法和广度优先搜索算法进行介绍。查找算法一般可分为如下几种,如图 1 所示。
常见的数据查找算法
图 1:常见的数据查找算法

顺序查找是最简单的查找方式,需要把所有数据遍历一遍,所以效率相对较低,对大数据量的查找问题不太适合。二分查找的查找效率非常高,但是数据必须有序,而对数据排序通常需要更多的时间开销,因此只适用于在排好序的数据中查找。后面将介绍的深度优先搜索算法、广度优先搜索算法,是一种暴力查找法的优化算法,同样对大数据量的查找问题效率也不高。

艺术来源于生活,编程也一样来源于生活。在生活中,要想随时能够找到自己的东西,最好的办法就是把东西放到固定的地方,每次需要它的时候就去相应的地方找,用完以后再放回原处。例如,剪刀就放到阳台柜子的第二个抽屉,袜子就放到衣柜的第三层等。

哈希算法也是一样的原理。简单来说,就是把一些复杂的数据,通过某种函数映射关系,映射成更加易于查找的方式。每个数据都会映射为独一无二的地址,数据存储时,它会存储于这个地址,取数据时,还会在这个地址取。哈希算法就像一本字典,当需要查词的时候,通过目录找到页码,再到对应页码就能找到所需要的内容了。

这种映射关系有可能会发生多个关键字映射到同一地址的现象,称为冲突。在这种特殊情况下,需要对关键字进行第二次或更多次的处理,在其他的大多数情况下,哈希算法可以实现在常数时间内存储和查找这些关键字。