赫序

静态赫序(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)

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

数字抽取函数(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)

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

目录

无目录