查找思维导图

查找算法相关知识思维导图，本图的知识包括线性表查找、树表查找以及散列表查找（杂湊法、散列法）－－散列表Hash（哈希表）三部分，适用于预习、复习的参照。

查找

• 线性表查找
  • 顺序查找
  • 折半查找
  • 分块查找
• 树表查找
  • 二叉排序树
  • 平衡二叉树
  • B－树
  • B+树
• 散列表查找（杂湊法、散列法）－－散列表Hash（哈希表）
  • 思想：通过对某元素的关键字值进行运算，直接求出元素的地址，即使用关键字到地址的直接转化方式，无需反复比较
  • 术语
    • 散列函数和散列地址——p=H(key)
      • H：散列函数
      • p：散列地址
    • 散列表
      • 有限连续的地址空间==常用一维数组，散列地址就是数组下标
      • 用来存储按散列函数计算得到相应散列地址的数据记录
    • 冲突和同义词——key1!=key2而H(key1)=H(key2)
      • 冲突：:key1!=key2而H(key1)=H(key2)的现象
      • 同义词：key1与key2互成为同义词
  • 散列函数的构造方法
    • 考虑因素
      • 散列表长度
      • 关键字
        • 长度
        • 分布情况
      • 计算散列函数所需时间
      • 记录查找频率
    • 关键问题－－构造散列函数原则
      • 简单：不存在很大的计算量－－查找效率低下
      • 均匀：函数值尽量均匀散步在地址空间－－保证存储空间有效利用，减少冲突
    • 散列函数实现方法
      • 直接定址法
        • H(key)=a*key=b
        • 不足
          • 使用中不能提前知道key值集合
        • 适用范围：
          • 提前知道关键码
          • 关键吗集合不大，较为连续且不离散
      • 除留余数法
        • H(key)=key mod p
        • 不足
          • p选取不当，导致冲突率上升
        • 优点
          • 最简单、最常用
          • 不要求事先知道关键码的分布
      • 数字分析法
        • 对不同数据进行不同分析，写出合适的H(x)
      • 平方取中法
      • 折叠法
  • 冲突处理方法
    • 开放地址法
    • 链地址法（开散列方法、拉链法）==闭散列表
    • 开散列方法
      • 思路：由关键码得到的散列地址发生冲突，寻找下一个空的散列地址，存入记录
      • 寻找下一个空散列地址的方法
        • 线性探测法
          • 公式：Hi=(H(key)+di)MODm (di=1,2,...,m-1)
          • 堆积现象：非同义词对同一个散列地址争夺现象
        • 二次探测法
          • 公式：Hi=(H(key)+di) (di=1^2,-1^2,2^2,-2^2,...,q^2,-q^2且q<=m/2)
        • 随机探测法
          • 发生冲突时，下一位移量是一个随机数列
          • 公式：Hi=(H(key)+round) (round为随机数)
        • 再hash法
    • 闭散列方法
      • 拉链法
      • 建立公共溢出区
  • 散列表查找方法
  • 缺陷
    • 一般不适合在允许多个记录有同样关键码的情况下使用
      • 消除冲突
    • 不适用于范围查找
      • 查找最大值或者最小值
      • 不可能找到某一范围内的记录