查找算法【哈希表】 - 简介

查找算法【哈希表】 - 简介

线性表和树表中的查找都是通过比较关键字的方法进行的，查找效率取决于关键字的比较次数。

【问题】有没有一种查找方法，不进行关键字比较，就可以直接找到目标？

散列表是根据关键字直接进行访问的数据结构，通过散列函数将关键字映射到存储地址，建立关键字和存储地址之间的直接映射关系。

这里的存储地址可以是数组下标、索引、内存地址等。

【举个栗子】

例如，关键字key=(17,24,48,25)，散列函数H (key)=key%5，散列函数将关键字映射到存储地址下标，将关键字存储到散列表的对应位置，如下图所示。

在上图中，如果要查找48，就可以通过散列函数得到其存储地址，直接找到该关键字。

在散列表中进行查找的时间复杂度与表中的元素个数无关。在理想情况下，在散列表中进行查找的时间复杂度为O (1)。

【问题】

但是，散列函数可能会把两个或两个以上的关键字映射到同一地址，发生冲突，这种发生冲突的不同关键字叫作“同义词”。

例如，13通过散列函数计算的映射地址也是3，与48的映射地址相同，则13和48为同义词。

因此，在设计散列函数时应尽量减少冲突，如果冲突无法避免，则需要设计处理冲突的方法。