散列表

发表于 | 分类于 | 评论数： | 热度： ℃
本文字数： 489 | 阅读时长 ≈ 1 分钟

概念

散列表即为直接将查找的关键字与索引位置相关联，散列表建立了关键字和存储地址之间的一种映射关系。查找的时间复杂度O(1)。

  • 同义词：不同关键字却指向同一个存储地址，称为同义词，冲突

  • 散列函数（hash）：直接定址法，除留余数法。。。

  • 处理冲突：

    1. 开放定址法
      1. 线性探测法
      2. 平方探测法
      3. 再散列
      4. 伪随机法
    2. 拉链法（顺序+链式存储结构）

散列表的查找效率取决于三个因素：

  1. 散列函数
  2. 冲突处理
  3. 装填因子（表示装满的程度）

----\(˙<>˙)/----赞赏一下吧～