数据结构 哈希搜索结构

我们之前学过的查找方法有很多：
1.静态搜索
顺序查找：O(N)。
二分查找：O(logN)。
2.动态搜索
二叉搜索树：最优查询效率O(N)。
AVL树：O(logN)。
但是上述的查找都是要经过元素比较才能进行查找的。查询的效率取决于比较的次数。

哈希结构

我们理想的搜索方法是：不进行元素比较，而是对每个元素的存储格式进行改造，通过某种方式，将元素与存储结构建立一一对应的关系。这样就可以通过这种关系快速地找到对应的元素。

插入时：
让插入的元素经过某些函数计算出它的插入位置，进行插入。
查找时：
先计算出此元素的位置，再根据位置找到结构这种对应的数，进行比较。

这种方式的结构就是哈希搜索结构，某些函数就是哈希函数，存储数据的表格为哈希表，计算出每个元素的位置位哈希表的下标。

举个例子：

如何来设计一个比较好的哈希函数？
1.保证哈希函数值域必须在表格范围内。 也就是通过哈希函数计算出来的下标，必须在哈希表下标范围内。
2.尽量保证哈希函数的值域均匀分布。
3.哈希函数尽可能简单。

哈希冲突

那么我们如果按照上述哈希函数的计算方法，哈希地址（下标）肯定会有重复的。但是此时对应位置上已经有元素了，这就是哈希冲突。

那么我们如何来解决哈希冲突呢?
1.闭散列。
2.开散列。