数据结构第八章hash新版课件.ppt

散列（Hashing)存贮 p353;这种存贮线性表F的方法，称为散列存贮。称函数h(x)为散列函数（HASH函数)。 称存放结点的数组T(m)为散列表(Hash表). 设F是含有六个结点的线性表，其中K0=(9,e) ,k1=(12,b), k2=(20,e), K3=(26,a), k4=(34,d), k5=(48,f). 若取散列函数h(x)=x mod 10，并使用能存放十个结点的数组T[10]作为Hash表，则下图表示了F的散列存贮的状况。;0 1 2 3 4 5 6 7 8 9;;静态散列方法; ; 采用的散列函数是 hash(x) = x % 73 + 13420 其中，“%”是除法取余操作。 则有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。就是说, 对不同的关键码, 通过散列函数的计算, 得到了同一散列地址。我们称这些产生冲突的散列地址相同的不同关键码为同义词。 由于关键码集合比地址集合大得多, 冲突很难避免。所以对于散列方法, 需要讨论以下两个问题： ;构造散列函数时的几点要求： 散列函数应是简单的，能在较短的时间内计 算出结果。 散列函数的定义域必须包括需要存储的全部 关键码, 如果散列表允许有 m 个地址时, 其 值域必须在 0 到 m-1 之间。 ;一、开式寻址法解决冲突;1.建立Hash表的插入运算。 为了把键值k存入Hash表，先计算出h(k)=i. 如果t[i] 是一个空位置（即t[i]=0),那么把k存入t[i],插入过程结束； 如果t[i]不是空位置（即t[i]≠0),那么再判断t[i]是否等于k， 若t[i]=k,则键值k已在Hash表中，插入过程结束； 否则，t[i]已被另一个键值所占用（发生冲突），此时必须为k找另一个空位置，最简单的办法是进行线性探测，我们可使用下面的循环探测地址序列：;; ;;;;;; ; ; ;; ;;Collision resolution by chaining We can take the hash table itself as an array of pointers to the record,that is,as an array of linked lists. It is traditional to refer to the linked lists from hash as chains and call this method collision resolution by chaining. 把来自hash表中的一些链表叫做链，称该方法为拉链法。;1.Advantage of chaining The first,is that considerable space may be saved. Since the hash table is a continuous array, enough space must be set aside at compilation time to avoid overflow. If the hash table contains only pointers to the records,pointers that require only one word each,the size of the hash table may be reduced by a large factor and will become small relative to the space available for the record,or for other uses. ;The second advantage of keeping only pointers in the hash table is that it allows simple and efficient collision handing. We need only add a link field to each record, and organize all the records with a single hash address as linked list. Finally, deletion becomes a quick and easy task in chained hush table. 2. Disadvantage of chaining All the links require space. ;二、用拉链法解决冲突