散列表

散列查找法的两项基本工作

• 计算位置：构造散列函数直接确定关键词存储位置
  散列函数的设计，主要目的是构造随机性：
  1. 计算简单：
     对于数字型：直接映射； 除留余数法；数字分析法；折叠法；平方取中法；
     对于字符关键词：ASCII码加和法
  2. 地址空间分布均匀
• 解决冲突：解决多个关键词位置相同的问题
  1. 开放地址法：
     线性探测：聚集现象严重
     平方探测：设计为 4K+ 3（一定可以遍历所有空位）
     双散列
     再散列
     装填因子一般是不超过0.5
  2. 链地址法