散列查找

散列查找

• 链地址法解决冲突时，采用的时顺序存储与链式存储相结合的方式
• 散列查找以计算散列函数的方式查找，然后比较关键字以确定是否查找成功
• 冲突是不可避免的，与装填因子无关
• 散列查找成功的平均查找长度与装填因子有关，与表长无关
• 开放定址法的堆积问题，是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起，导致关键字查询需要经过较长的探测距离，降低了散列效率
• 散列表的查找效率取决于
  • 散列函数
  • 处理冲突的方法
  • 装填因子
• 产生堆积现象，即产生冲突，它对存储效率、装填因子和散列函数均不会有影响，而平均查找长度会因为堆积现象而增大
• 装填因子越大，说明哈希表中存储的元素越满，发生冲突的可能性就越高，导致平均查找长度越大
  • 散列函数、冲突解决策略也会影响发生冲突的可能性