查找

  • 折半查找在查找不成功是和给定值进行关键词比较最多的树的高度为
  • 查找公式(low+high)/2

散列表

  1. 散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
  2. 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生。
  3. 散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。
  • 构造方法
  1. 直接定值法：直接取关键字的某个线性函数值为散列地址，散列函数为$H(key)=a*key+b,a和b是常数，这种方法计算简单，并且不会冲突，它适合关键字分布的基本连续情况，若关键词分布不连续，空位较多，将造成存储空间的浪费。
  2. 除留余数法：最简单最常用的方法，假定散列表表长为m，取一个不大于m但是最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为：H（key）=key%p。关键是选好p。使得每一个关键词通过该函数转换成等概率的映射到散列空间的任一地址，从而尽可能减少冲突的可能性；
  3. 数字分析法：设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，则应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合
  4. 平方取中法：顾名思义，取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，使得散列地址分布比较均匀。
  5. 折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址

冲突处理办法

  1. 开放地址法
  • 线性探测法：冲突发生时，顺序查看表中的下一个单元（当探测到表尾地址m-1时，下一个探测地址时表首地址0），直到找到一个空闲单元（当表未填满时一定能找到一个空闲单位）或查遍全表。
  • 平方探测法：设发生冲突的地址为d，平方探测法得到的新的地址序列为,,,,
  • 再散列法：需要两个散列函数，通过第一个散列函数H（key）得到的地址发生冲突时，则利用第二个散列表H（2key）计算该关键字的地址增量
  • 伪随机序列法：当发生地址冲突时，地址增量为伪随机树序列，成为伪随机序列表。
  1. 拉链法
  • 对于不同的关键字可能通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以吧所有的同义词储存到一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适应于经常进行插入和删除的情况。

-填装因子：定义一个表的装满程度 计算方法：