第五章散列查找

散列查找，其基本思想是通过由散列函数决定的键值与散列地址之间的对应关系来实现存储组织和查找运算。既是一种存储方式，又是一种查找方法。

第五章散列查找

• 基本概念
  • 基本思想是通过由散列函数决定的键值与散列地址之间的对应关系来实现存储组织和查找运算。既是一种存储方式，又是一种查找方法。
  • 散列技术时需要考虑的两个主要问题是：①如何构造（选择）"均匀的"散列函数？②用什么方法解决冲突？
• 散列函数的构造方法
  • 数字关键词的散列
    • 直接定址法
      • 直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)为:H(key)=key+C
      • 特点:方法计算简单，并且没有冲突。它适合于关键字的分布基本连续的情况，若关键字分布不连续，空号较多，将会造成较大的空间浪费。
    • 除留余数法
      • 除余数法是一种最简单也最常用的一种散列函数构造方法。散列函数:H(k)=k%p其中，p最好选取小于或等于表长m的最大素数1。
    • 数字分析法
      • 数字分析法是假设有一组关键字，每个关键字由n位数字组成，数字分析法是从中提取数字分布比较均匀的若干位作为散列地址。
    • 平方取中法
      • 取关键字平方的中间几位作为散列地址的方法折叠法
    • 折叠法
      • 折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些)，段的位数取决于散列地址的位数，由实际情况而定，然后将它们的叠加和(舍去最高进位)作为散列地址的方法
  • 字符串关键词的散列
    • 一个简单散列函数——ASCII码加和法
    • 简单的改进——前三个字符移位法
    • 好的散列函数——移位法
• 处理冲突的方法
  • 开放定址法
    • 原理
      • 一旦产生了冲突(该地址已有其他元素)，就按某种规则去寻找另一空地址。 首先散列函数算出一个值，代表该元素初始要放的位置，此时如果发生了第一次冲突，就在原地址上加一个di进行探测，发生第二次就再加di
    • 公式
    • 方法
      • 1线性探测
        • 以增量序列1，2，…,(TableSize-1)循环试探下一个存储地址。
      • 2平方探测
        • 平方探测法：以增量序列1²，-1²，2²，-2²…q²，-q²且q≤TableSize/2（向下取整）循环试探下一个存储地址。
      • 3双散列探
      • 4再散列法
        • 当散列表元素太多(即装填因子a太大)时，查找效率会下降，此时把散列表的规模扩大。那么此时原来散列表的元素不能单纯拷贝到新表中，必须重新计算位置，再依次放入新表。这就是再散列。
  • 分离链接法
    • 将相应位置上冲突的所有关键词存储在同一个单链表中
• 性能分析
  • 平均查找长度(ASL)用来度量散列表查找效率:成功、不成功关键词的比较次数，取决于产生冲突的多少
  • 影响因素
    • ( 1)散列函数是否均匀;
    • (2)处理冲突的方法;
    • (3)散列表的装填因子α。