007跳表和散列2.ppt

* 一种改进的方法 ∞ 0 ∞ 0 ∞ 0 ∞ 0 ∞ 0 * 与线性开型寻址散列比较 空间: 线性开型寻址散列 :b(s+2) (数组 empty: 2b) 链表散列 : 2b+2n+ns 当bbs/(s+2) , 链表方法所占用的空间要比开型寻址少. 在实现线性开型寻址散列时采用一种节约空间的方法，二者间的比较结果可能会发生变化。 压缩数组empty 使用一个不可能用到的整数( –1或INT_MAX )作为空桶的关键字。 * 与线性开型寻址散列比较 时间复杂性: 线性开型寻址散列 : 最坏情况: ?(n) 平均性能: Sn ~ ? (1 + 1/(1- α )) Un ~ ? (1+1/(1- α)2) 链表散列 : 最坏情况: O(n) 平均性能: Sn ~ 1+ α/2 Un ~ （1+ α）/2 α =1 Un = α α 1 * 与线性开型寻址散列比较 一次不成功有哪些信誉好的足球投注网站所要有哪些信誉好的足球投注网站的节点数为 : i=1 0 i=0 0 …… i 平均性能Un : 链表的平均长度为: n/b= α Un~ (α + 1)/2 α =1 Un= α ? α 1 * 与线性开型寻址散列比较 假定 :各元素是按升序插入的。 当插入第i 个元素时 0 …… 1次 2次 3次 i次 ki 0 …… (i-1)/b 平均性能Sn : * 与线性开型寻址散列比较 Search ki: (i-1)/b+1 使用链表时的平均性能要优于使用线性开型寻址。 ki 0 …… (i-1)/b * 与跳表比较 跳表和散列均使用了随机过程来提高字典操作的性能 时间复杂性: 最坏情况: 跳表: ?(n+MaxLevel) 链表散列: ?(n) 平均性能: 跳表: O(logn) 链表散列: O(1) 空间 （指针所占用的空间 ）: 跳表: 平均: MaxLevel+n/(1-p) 最坏情况: n*MaxLevel+1 链表散列: D+n * 与跳表比较 跳表比散列表更灵活. 在线性时间内按升序输出所有的元素.而采用链表散列时，需要(D+n) 时间去收集n 个元素，并且需要O(nlogn)时间进行排序，之后才能输出 。 查找或删除最大或最小元素，散列可能要花费更多的时间（仅考虑平均复杂性）。 * 练习 1.设有一组关键字：{19，14，23，01，68，20，84，27，55，11，10，79}，采用哈希函数： H（key）=key mod 13，采用线性开型寻址方法解决溢出。 要求：在0∽12的散列地址空间中对该关键字序列构造哈希表。有哪些信誉好的足球投注网站元素27，55所花的比较次数各是多少？ 2.有关键字集合：{19，14，23，01，68，20，84，27，55，11，10，79}，哈希函数：H（key）=key mod 13，采用链地址散列方法解决溢出。要求： 构造哈希表；有哪些信誉好的足球投注网站元素27，55所花的比较次数各是多少？ * * * 第 7 章 跳表和散列 (Skip List and Hashing） * 本章内容 7.1 字典 7.2 线性表描述 7.3 跳表描述 7.4 散列表描述 7.5 应用 * * 散列表Hash Table 散列是计算机科学的一个伟大发明，它是由数组、表和一些数学方法相结合，构造起来的一种能够有效支持动态数据的存储和提取的结构。 典型应用是符号表，在一些值（数据）与动态的字符串（关键码）集合的成员间建立一种关联。 * * 散列的思想 散列表的思想是把关键码送给一个散列函数，产生一个散列值，这种值平均分布在一个适当的整数区间中。 散列值被用作存储信息的表的下标。 散列函数关键码————地址(固定，连续空间) * 7.4.1 理想散列 散列(Hashing) :字典的另一种描述方法就是散列 散列方法, 是用一个散列函数(hash function)把关键字映射到散列表/哈希表(hash table)中的特定位置。 理想情况 :如果散列函数为f 元素e 的关键字为k f 是散列函数 e 在散列表中的位置为f(k) 散列表操作: 有哪些信誉好的足球投注网站（Search）:计算出f (k)，然后看表中f (k)处是否有元