数据结构 哈希搜索结构
我们之前学过的查找方法有很多:
1.静态搜索
顺序查找:O(N)。
二分查找:O(logN)。
2.动态搜索
二叉搜索树:最优查询效率O(N)。
AVL树:O(logN)。
但是上述的查找都是要经过元素比较才能进行查找的。查询的效率取决于比较的次数。
哈希结构
我们理想的搜索方法是:不进行元素比较,而是对每个元素的存储格式进行改造,通过某种方式,将元素与存储结构建立一一对应的关系。这样就可以通过这种关系快速地找到对应的元素。
插入时:
让插入的元素经过某些函数计算出它的插入位置,进行插入。
查找时:
先计算出此元素的位置,再根据位置找到结构这种对应的数,进行比较。
这种方式的结构就是哈希搜索结构,某些函数就是哈希函数,存储数据的表格为哈希表,计算出每个元素的位置位哈希表的下标。
举个例子:
如何来设计一个比较好的哈希函数?
1.保证哈希函数值域必须在表格范围内。 也就是通过哈希函数计算出来的下标,必须在哈希表下标范围内。
2.尽量保证哈希函数的值域均匀分布。
3.哈希函数尽可能简单。
哈希冲突
那么我们如果按照上述哈希函数的计算方法,哈希地址(下标)肯定会有重复的。但是此时对应位置上已经有元素了,这就是哈希冲突。
那么我们如何来解决哈希冲突呢?
1.闭散列。
2.开散列。