散列表

#散列表（哈希表，Hash）

  • 特点：可以根据数据元素的关键字计算出它在散列表中的存储地址

    • #散列函数

  • Addr=H(key) 建立“关键字->存储地址”的映射关系，详情见散列函数
  • Pasted image 20260606202541.png

    • #冲突

  • 即多个数据元素经过散列函数转换后的地址相同导致插入数据时该位置已经被占用

    • #解决冲突

  • #拉链法：遇到冲突就将关键字挂到该位置的关键字的下面
  • Pasted image 20260606203303.png
  • 很简单粗暴的解决方法，虽然并不是主流
  • #开放定址法：将新元素插入到其余空闲位置
  • 详情见解决冲突