查找

本来是想根据数，二叉树，图，栈，队列，查找，排序总结到一个md文件里面的，但是内容可能会很多就不太方便合起来整理，就先写查找算法吧

哈希查找

  • 是一种时间复杂度为O(1)的一种效率极高的查找方法，与常见的遍历查找不同，哈希算法是通过数组元素数值与哈希表下标构建的一种查找方法，因此我们不需要遍历整个数组，即可对其进行访问。
  • 如果不发生碰撞效率极高，因此设计散列函数也十分重要。如H(key) = (keyx3) MOD 7

哈希算法的特点

  • 1、哈希算法具有特殊的哈希表

  • 2、哈希算法不用遍历即可查找访问目的元素

  • 3、哈希算法基于一个特殊的哈希函数所构建

  • 4、哈希表存在哈希碰撞（哈希冲突）

哈希查找算法之线性探测法

  • 在开放定址算法里，线性探测法是散列解决冲突的一种方法
    • 当hash一个关键字时，发现没有冲突，就保存关键字。
    • 如果出现冲突，则就探测冲突地址下一个地址，依次按照线性查找，直到发现有空地址为止，从而解决冲突。

装填因子

  • 一般情况下，设散列表空间大小为m，填入表中的元素个数是n,则称α=n/m为散列表的装填因子，例如大小为17，元素为11，装填因子为0.65.实用时，常见散列表大小设计使得α=0.5~0.8为宜。
  • 装填因子（元素个数/散列表长度）

###散列表的性能分析

散列表主要涉及在查找上面，避免冲突是他要解决的，衡量性能也从这里分析，影响产生冲突多少有以下三个因素：

  • 散列函数是否均匀
  • 处理冲突的方法
  • 散列表的装填因子α

题目

关键字集合{7、8、30、11、18、9、14}，散列函数为：H(key) = (keyx3) MOD 7， 设装填因子（元素个数/散列表长度）为0.7，那么 散列表的长度为 10

  • 设计散列表(长度为10，下标为0-9)
0 1 2 3 4 5 6 7 8 9

  • 计算key对应的哈希数组下标

    • 如元素7 ==> (7 * 3) % 7 ==> 0 —>因此填入散列表下标为0
    • 如元素14 ==> (14 * 3) % 7 ==> 0 —>因此填入散列表下标为0，但是由于第一个元素7占用了散列表下标为0的位置，发生了冲突，所以往后探测发现散列表下标为1的位置为空，于是14放入1(散列表下标)。

  • 最终的散列表为：

0 1 2 3 4 5 6 7 8 9
7 14 8 11 30 18 9

性能–平均查找长度

  • 查找成功的平均查找长度 = （插入元素时的比较次数之和）/ 关键字个数

    • （1+1+1++1+3+3+2）/ 7

  • 查找不成功的平均查找长度 = （每个位置查找失败到查找到的比较次数）/ 关键字个数

    • （3+2+1+2+1+5+4）/7

    • 等概率情况下，查找0~6位置查找失败的查找次数为：

      • 地址0，到第一个关键字为空的地址2的距离为3，因此查找不成功的次数为3

      • 地址1， 到第一个关键为空的地址2的距离为2，因此查找不成功的次数为2.

      • 地址2， 到第一个关键为空的地址2的距离为1，因此查找不成功的次数为1.　

      • 地址3，到第一个关键为空的地址4的距离为2，因此查找不成功的次数为2.

      • 地址4，到第一个关键为空的地址4的距离为1，因此查找不成功的次数为1.

      • 地址5，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为5，因此查找不成功的次数为5.

      • 地址6，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为4，因此查找不成功的次数为4.

        ​

      　　

      ​

      ​