散列查找

一、散列表🧀

• 普通查找 \(O(n)\) 复杂度
• 散列查找 \(O(1)\) 复杂度

graph LR
    K0[0] --> H
    K1[1] --> H
    K2[2] --> H
    K3[3] --> H
    K4[4] --> H
    K5[5] --> H

    H:::hash --> I0[0]
    H --> I1[1]
    H --> I2[2]
    H --> I3[3]
    H --> I4[4]
    H --> I5[5]

    class H hash

    subgraph "关键字（key）"
        direction TB
        K0
        K1
        K2
        K3
        K4
        K5
    end

    subgraph "下标（地址）"
        direction TB
        I0
        I1
        I2
        I3
        I4
        I5
    end

二、散列函数🧀

（1）恒等函数🧀

• 会造成空间浪费

（2）直接定址法🧀

• 关键字连续更好

• \[ H(key)=a\times key+b \]

（3）除留余数法🧀

• \(p\) 取小于表长的最大质数

• \[ H(key)=key \%p \]

• 同义词会产生冲突

• 装填因子 \(\alpha\)：表中元素数量/表长

  • 装填因子越大，越容易冲突
  • 装填因子越小，越不容易冲突

三、冲突处理 - 开放定址法🧀

（1）线性探测法🧀

• 冲突后一次探测下一个空闲位置
• 插值和插入时一样：先用除留余数法找到那个位置，如果不等依次向后比较，直到第一个空位置的就说明不存在