数据结构 哈希搜索结构

我们之前学过的查找方法有很多: 1.静态搜索 顺序查找:O(N)。 二分查找:O(logN)。 2.动态搜索 二叉搜索树:最优查询效率O(N)。 AVL树:O(logN)。 但是上述的查找都是要经过元素比较才能进行查找的。查询的效率取决于比较的次数。 哈希结构 我们理想的搜索方法是:不进行元素比较,而是对每个元素的存储格式进行改造,通过某种方式,将元素与存储结构建立一一对应的关系。这样就可以通过这种关系快速地找到对应的元素。 插入时: 让插入的元素经过某些函数计算出它的插入位置,进行插入。 查找时: 先计算出此元素的位置,再根据位置找到结构这种对应的数,进行比较。 这种方式的结构就是哈希搜索结