7.【散列查找】

文章目录

• 散列表（又称：哈希表）
• 【拉链法】散列查找、查找效率分析
• 常⻅的散列函数
• • 1. 除留余数法 —— H(key) = key % p
  • 2. 直接定址法 —— H(key) = key 或 H(key) = a*key + b
  • 3. 数字分析法 —— 选取数码分布较为均匀的若⼲位，作为散列地址
  • 4. 平⽅取中法——取关键字的平⽅值的中间⼏位，作为散列地址。
• 处理冲突的⽅法——开放定址法
• • ① 线性探测法： di = 0, 1, 2, 3, …, m-1；即发⽣冲突时，每次往后探测相邻的下⼀个单元是否为空
  • ②平⽅探测法。当di = 0^2^, 1^2^, -1^2^, 2^2^, -2^2^, …, k^2^, -k^2^时
  • ③伪随机序列法。di 是⼀个伪随机序列，如