chap11 散列表

直接寻址表 散列表 散列函数 开放寻址 算法导论

内容

散列函数

1. $h(k) = k$ -->直接寻址表：简单讲，就是直接用元素的key作为需要存放的数组下标。因而他要求，所有的key都不相同，且|K|与|U|相当，否则会造成空间的浪费
2. $h(k) = k modm$-->除法散列表
3. $h(k) =\lfloor m( kA mod1) \rfloor$-->乘法散列表

全域散列法

开放寻址法

1. 所有的元素都在散列表中
2. 好处在于不需要指针，节省了空间，反过来增加了槽的数量，潜在地减少了冲突，提高了检索速度
3. 散列函数： $h:U \times {0,1,...m-1} \rightarrow {0,1,...m-1}$

4. 探查序列的产生方法

   线性探查
   二次探查
   双散列
   

5. 检索和插入操作

--

Hash-Insert(T,k)
i = 0
while i <= m
    j = h(k,i)
    if T[j] == nil
        T[j] = k
        return j
    else 
        i = i + 1
error "hash table overflow"


Hasj-Search(T,k)
i = 0
do
    j = h(k,i)
    if T[j] == k
        return j
    i = i + 1 
while T[j] != NIL and i <= m
return NIL

注意，检索的while的第一个条件，它来自于插入操作的if条件，显然如果有一个位置是空的，那么它之后的slot必然都是空的。这一性质也影响了删除操作，因为简单的将slot指向NIL会影响对该slot后面元素的检索操作。因而该散列方法不适用于必须删除关键字的应用。

to be comtinued