散列表的基本_散列表的伪随机数法

定义：

1. 散列查找法：关键字与其存储位置之间建立某种直接关系，在查找时按照这种关系便可快速找到对应关键字的查找
2. 散列函数：散列查找法中使用的转换函数
3. 冲突：不同的关键字对应到同一个散列地址【key1≠key2，H(key1)=H(key2)】【不可避免】
4. 同义词：对应到统一散列地址的不同关键字之间的互称
5. 装填因子α：表中填入的记录数/哈希表长度

构造关键：

1. 散列函数尽可能简单以提高转换速度，散列地址尽可能均匀分布以节省空间
2. 制定一个好的解决冲突的方案

构造方法

直接定址法 —— Hash(key)=akey+b(a、b为常数)

1. 优点——以关键码key的某个线性函数值为散列地址，不会产生冲突
2. 缺点——要占用连续地址空间，空间效率低

除留余数法 —— Hash(key)=key mod p(p是一个整数≤表长)

解决冲突

开放定址法

• 基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入
• 常用方法：线性探测法、二次探测法、伪随机探测法
  • 线性探测法 —— Hi = (Hash(key)+di) mod m (1 ≤ i＜m)       
    • m是散列表长度，d是增量序列1，2，.......，m-1，且di=i
    • 成功时ASL=(Σ(1+冲突移动次数))/元素个数
    • 失败时ASL=(Σ(到空的地址的比较次数))/地址个数
  • 二次探测法 —— Hi = (Hash(key)+di) mod m 
    • m是散列表长度，d是增量序列1²，-1²，2²，-2²，.......，q²
  • 伪随机数探测法 ——  Hi = (Hash(key)+di) mod m 
    • m是散列表长度，d是伪随机数

链地址法 

• 基本思想：相同散列地址的记录链成一个单链表【m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来】
• 建立散列表步骤：

1. 取数据元素的关键字key，计算散列地址。若该地址对应链表为NULL，则将该元素插入此链表；否则进行步骤2
2. 根据选择的冲突处理方法，计算关键字key的下一个存储地址，若该地址对应链表不为空，则利用前插(后插)法将该元素插入此链表

• 优点：非同义词不会冲突，无“聚集”现象；结点空点动态申请