[关闭]
@zqbinggong 2018-03-11T09:02:33.000000Z 字数 628 阅读 337

chap11 散列表

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

内容


散列函数

  1. -->直接寻址表:简单讲,就是直接用元素的key作为需要存放的数组下标。因而他要求,所有的key都不相同,且|K|与|U|相当,否则会造成空间的浪费
  2. -->除法散列表
  3. -->乘法散列表

全域散列法


开放寻址法

  1. 所有的元素都在散列表中
  2. 好处在于不需要指针,节省了空间,反过来增加了槽的数量,潜在地减少了冲突,提高了检索速度
  3. 散列函数:
  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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注