赫序

静态赫序(static hashing)

静态赫序组件

• 赫序表(Hash table，ht):将识别字或键值存进固定大小的表格

    赫序表被存於记忆体的连续位置-桶子(buckets)中，每个位置有s个槽(slots) 
  

• 赫序函式(Hashing function) f:决定识别字在赫序表的位置

• 键值密度:(key density):n/T

    n:所有键值的数量
    T:所有可能键值的总数量
  

• 承载密度(loading density) α :n=(sb)

    b:桶子数
    s:桶子槽数
  

• 同义字(synonyms):两个键值i1,i2具有f(i1)=f(i2)特性

溢位和碰撞

• 溢位(overflow):当新的键值进入到已满的桶子

• 碰撞(collision):两个不同的识别字进入到同一个桶子

    当桶子大小为1时，溢位和碰撞是同时发生的
  

赫序函数的作法

• 直接函数(Direct)

• 减去函数(Subtraction)

• 模数函数(Modulo-Division)

  地址=键值取表格大小的余数

    121267/307=395  …. 2
    =>Hash(121267)=2
  

• 中间平方函数((Mid-square))

  平方後取中间值

    9452*9452=89340304 
    =>Hash(9452)=340
  

• 摺叠函数(Folding)

  取出每一段相加求出求出赫序地址，除了最後一段外，其余长度全部相等

  • 移位摺叠(Shift folding)
    
  • 边界摺叠(Folding at the boundaries)
    

• 数字抽取函数(Pseudo Random)

    ex:选择第 1, 3 及 4 个数字
    379452 =>394
    121267 =>112
    378845 =>388
    160252 =>102
  

• 虚拟乱数函数(Pseudo Random)

  将键值设为乱数产生器的种子

    y=(ax+c) mod b   
    y: 地址
    x: 键值
    b: 赫序表格大小
    a、c、b 都是质数
  

• 旋转函数(Rotation)

  通常不是单独使用

  

• 字串键值转整数函式

  int transform(char *key){
    /* 将任意长度的字串键值转成一个非负自然数 */  
    int number=0;
    while (*key)       number += *key++;
    return number;
    }
  

溢位处理(Overflow Handling)

开放定值法法 (open addressing)

• 线性探测(Linear probing)

  寻找最接近并未使用的桶子，较容易发生群集
  线性探测的平均次数大约是(2-α)/(2-2α) (α是承载密度)

  

• 二次探测(quadratic probing)

  二次探测可降低寻找次数

    顺序:h(k)、(h(k)+i2)%b、 (h(k)-i2)%b，1≦ i ≦(b-1)/2
  

• 再赫序(rehashing)

• 随机探测(rehashing)

    检查顺序:h(k)、(h(k)+s(i))%b、 1≦ i ≦(b-1)。
    s(i)是一个虚拟乱数，其值介於1到b-1
  

链结法(Chaining)

• 寻找次数大约在(1+α/2) (α是承载密度)

• 除法赫序函数搭配链结法可以产生最佳的效能

• 最差情况还是O(n)

• 同义字放入二元搜寻数中，最差情况的比较次数可减至O(log n)。

动态赫序(dynamic hashing)

静态赫序会有太小空间不足，太大空间浪费问题，动态赫序可容许动态改变档案大小

目录

无目录