散列表

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

  • 计算位置：构造散列函数直接确定关键词存储位置
    散列函数的设计，主要目的是构造随机性：
    1. 计算简单：
      对于数字型：直接映射； 除留余数法；数字分析法；折叠法；平方取中法；
      对于字符关键词：ASCII码加和法
    2. 地址空间分布均匀
  • 解决冲突：解决多个关键词位置相同的问题
    1. 开放地址法：
      线性探测：聚集现象严重
      平方探测：设计为 4K+ 3（一定可以遍历所有空位）
      双散列
      再散列
      装填因子一般是不超过0.5
    2. 链地址法
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容