数据结构教程第6章集合与字典.ppt

n n 集合及其表示集合及其表示 n n 并查集与等价类并查集与等价类 n n 字典字典 n n 跳表跳表 n n 散列散列 集合基本概念集合基本概念 6.1.1 6.1.1 集合及其表示集合及其表示 n n 集合是成员集合是成员( (对象或元素对象或元素) )的一个群集。的一个群集。 集合中的成员可以是原子集合中的成员可以是原子( (单元素单元素) )，也，也 可以是集合。可以是集合。 n n 集合的成员必须互不相同。集合的成员必须互不相同。 n n 在算法与数据结构中所遇到的集合，其在算法与数据结构中所遇到的集合，其 单元素通常是整数、字符、字符串或指单元素通常是整数、字符、字符串或指 针，且同一集合中所有成员具有相同的针，且同一集合中所有成员具有相同的 数据类型。数据类型。 colourcolour = = red, orange, yellow, green, black, red, orange, yellow, green, black, blue, purple, white blue, purple, white namename = = An, An, CaoCao, Liu, Ma, , Liu, Ma, PengPeng, Wang, , Wang, zhangzhang n n 集合中的成员一般是集合中的成员一般是无序无序的，但在表示它时，的，但在表示它时， 常设定常设定集合中的单元素集合中的单元素具有线性有序关系具有线性有序关系，此，此 关系可记作关系可记作“ class Set public: virtual Set ( ) =0; virtual MakeEmpty ( )=0; virtual bool AddMember (const T x)=0; virtual bool DelMember ( const T x)=0; AB 或 A+B AB 或 AB A-B AAABBB virtual Set unionWith const Set virtual Set intersectWith (const Set virtual Set differenceFrom (const Set virtual bool Contains (const T x)=0; virtual bool subSet (const Set virtual bool operator= (const Set 6.1.2 6.1.2 用位向量实现集合抽象数据类型用位向量实现集合抽象数据类型 n n 当集合是全集合当集合是全集合 0, 1, 2, , 0, 1, 2, , n n 的一个子的一个子 集，且集，且 n n是不大的整数时，可用位是不大的整数时，可用位(0, 1)(0, 1)向量向量 来实现集合。来实现集合。 n n 当全集合是由有限的可枚举的成员组成的当全集合是由有限的可枚举的成员组成的 集合时，可建立全集合成员与整数集合时，可建立全集合成员与整数 0, 1, 2, 0, 1, 2, 的一一对应关系，用位向量来表示该集合的一一对应关系，用位向量来表示该集合 的子集。的子集。 集合的位向量集合的位向量( (bit Vector)bit Vector)类的定义类的定义 #include const int DefaultSize = 50; class bitSet private: unsigned short * bitVector; int setSize, vectorSize; public: bitSet ( int sz = DefaultSize ); bitSet ( ) delete bitVector; void makeEmpty ( ) for (int i = 0; i bitSet operator + (const bitSet bitSet operator * (const bitSet bitSet operator - (const bitSet bool Contains ( const T x ); bool subSet (bitSet/判this是否R的子集 bool operator = (bitSet friend istream friend istream ; 使用示例使用示例 bitSet s1, s2, s3, s4, s5; int index, equal; for ( int k = 0; k struct SetNode T data; SetNode * link; SetNode (const T ; 集合的有序链表类的定义集合的有序链表类的定义 template class LinkedSet private: SetNode *first, *last; /有序链表的表头指针, 表尾指针 public: LinkedSet( ) first = last = new SetNode; /构造函数 LinkedSet( ) MakeEmpty( ); delete first; void MakeEmpty ( ); /置空集合 bool AddMember ( const T bool DelMember ( const T LinkedSet /复制集合R到this LinkedSet /求集合this与集合R的并 LinkedSet /求集合this与集合R的交 LinkedSet /求集合this与集合R的差 bool Contains ( const T /判x是否集合的成员 集合的有序链表类的定义集合的有序链表类的定义 bool operator = (LinkedSet /判this是否与R相等 bool Min(T /返回集合中最小元素值 bool Max(T /返回集合中最大元素值 bool subSet(LinkedSet /判this是否R的子集 集合的有序链表类的定义集合的有序链表类的定义 6.2.1 6.2.1 并查集并查集 ( (Union-Find Sets)Union-Find Sets) n n 并查集支持以下三种操作：并查集支持以下三种操作： uu UnionUnion ( (RootRoot1, 1, RootRoot2)2) / /并操作并操作 uu Find Find ( (x x) ) / /搜索操作搜索操作 uu UFSetsUFSets ( (s s) ) / /构造函数构造函数 n n 对于并查集来说，每个集合用一棵树表示。对于并查集来说，每个集合用一棵树表示。 n n 为此，采用为此，采用树的双亲表示树的双亲表示作为集合存储表示作为集合存储表示 。集合元素的编号。集合元素的编号从从0 0到到 n n- -1 1。其中其中 n n 是最是最 大元素个数。大元素个数。 n n 在在双亲表示双亲表示中，中，第第 i i 个数组元素代表包含集合元个数组元素代表包含集合元 素素 i i 的树结点的树结点。根结点的双亲为。根结点的双亲为- -1 1，表示集合中，表示集合中 的元素个数。的元素个数。 n n 在同一棵树上所有结点所代表的集合元素在同一在同一棵树上所有结点所代表的集合元素在同一 个子集合中。个子集合中。 n n 初始时初始时, , 用构造函数用构造函数 UFSetsUFSets(s) (s) 构造一个森林构造一个森林, , 每每 棵树只有一个结点棵树只有一个结点, , 表示集合中各元素自成一个表示集合中各元素自成一个 子集合。子集合。 n n 用用 Find(i) Find(i) 寻找集合元素寻找集合元素 i i 的根。如果有两个集的根。如果有两个集 合元素合元素 i i 和和 j j, , Find(i) Find(i) = = Find(j)Find(j), , 表明这两个元素表明这两个元素 在同一个集合中。在同一个集合中。 n n 如果两个集合元素如果两个集合元素 i i 和和 j j 不在同一个集合中不在同一个集合中, ,可用可用 Union(i, j)Union(i, j) 将它们合并到一个集合中。将它们合并到一个集合中。 S S1 1 S S 2 2 的可能的表示方法的可能的表示方法 下标下标 parent 集合 S S1 1 , , S S2 2 和 S S3 3 的双亲表示 -1 4 -1 2 -1 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 7684 19 4 190 876 const int DefaultSize=10; class UFSets public: UFSets(int sz=DefaultSize); UFSets( )delete parent; void Union(int Root1, int Root2); int Find(int x); void WeightedUnion(int Root1, int Root2); private: int * parent; int size; ; 并查集类的定义并查集类的定义 UFSets:UFSets(int sz) size=sz; parent=new intsize; for(int i=0;i对的集合。 n字典的操作： n确定一个指定的名字是否在字典中； n搜索出该名字的属性； n修改该名字的的属性； n插入一个新的名字及其属性； n删除一个名字及其属性。 字典的抽象数据类型字典的抽象数据类型 const int DefaultSize = 26; template class Dictionary public: Dictionary(int size=DefaultSize); bool Member(Name name); Attribute* Search(Name name); void Insert(Name name, Attribute attr); void Remove(Name name); n n 在字典的所有操作中，最基本的只有在字典的所有操作中，最基本的只有 3 3 种：种：SearchSearch( (搜搜 索索) )、InsertInsert ( (插入插入) )、RemoveRemove ( (删除删除) )。 n n 在选择字典的表示时，必须确保这几个操作的实现。在选择字典的表示时，必须确保这几个操作的实现。 考虑到搜索效率考虑到搜索效率, , 可以用顺序表方式、二叉搜索可以用顺序表方式、二叉搜索 树或多路搜索树方式组织字典。本章介绍树或多路搜索树方式组织字典。本章介绍3 3种种 字典的组织方式：字典的组织方式：线性表、跳表和散列表线性表、跳表和散列表。 字典的线性表描述 线性表描述：线性表描述： 字典可以保存在线性序列字典可以保存在线性序列( (e e 1 1,e ,e2 2 ,),)中，其中中，其中 e e i i 是字典中的元素，其关键码从左到右依次增大。是字典中的元素，其关键码从左到右依次增大。 对于这种描述方式，有有序顺序表和有序链对于这种描述方式，有有序顺序表和有序链 表。表。 有序链表的类定义有序链表的类定义 template struct ChainNode E data; ChainNode* link; ChainNode( ):link(NULL) ; ChainNode(E template class SortedChain public: SortedChain( ) first= new ChainNode; assert(first!=NULL); SortedChain( ); 有序链表的类定义有序链表的类定义 ChainNode* Search(const K k1)const; void Insert(const K k1, E bool Remove(const K k1, E ChainNode* Begin( )return first-link; ChainNode* Next(ChainNode* current) const if(current!=NULL) return current-link; else return NULL; private: ChainNode* first; 在有在有n n个结点的有序链表中，搜索、插入、删除操作的个结点的有序链表中，搜索、插入、删除操作的 时间复杂性均为时间复杂性均为O(n)O(n)。 6.4 6.4 跳表跳表( (Skip List)Skip List) n在链表的中部结点增加一个指针，以减少 搜索时的比较次数。 10203040506070 10203040506070 10203040506070 6.5 6.5 散列散列 ( (Hashing)Hashing) 散列表是表示集合和字典的另一种有效方散列表是表示集合和字典的另一种有效方 法，它提供了一种完全不同的存储和搜索方式法，它提供了一种完全不同的存储和搜索方式 ，通过将关键码映射到表中某个位置上来存储，通过将关键码映射到表中某个位置上来存储 元素，然后根据关键码用用样的方式直接访问元素，然后根据关键码用用样的方式直接访问 。 散列方法散列方法 n n 散列方法在散列方法在元素存储位置元素存储位置与与其关键码其关键码之间建之间建 立一个立一个确定的对应函数关系确定的对应函数关系HashHash( ( ) )，使每个使每个 关键码与结构中一个唯一存储位置相对应：关键码与结构中一个唯一存储位置相对应： AddressAddress HashHash ( (key key ) ) n n 在搜索时在搜索时, , 先对元素的关键码进行函数计算先对元素的关键码进行函数计算, , 把函数值当做元素的存储位置把函数值当做元素的存储位置, , 在结构中按在结构中按 此位置取元素比较。若关键码相等此位置取元素比较。若关键码相等, , 则搜索则搜索 成功。在存放元素时成功。在存放元素时, , 依相同函数计算存储依相同函数计算存储 位置位置, , 并按此位置存放。这种方法就是散列并按此位置存放。这种方法就是散列 方法。方法。 n n 在散列方法中使用的转换函数叫做在散列方法中使用的转换函数叫做散列函数散列函数 。按此方法构造出来的表或结构就叫做。按此方法构造出来的表或结构就叫做散列散列 表表。 n n 使用散列方法进行搜索不必进行多次关键码使用散列方法进行搜索不必进行多次关键码 的比较的比较, , 搜索速度比较快搜索速度比较快, , 可以直接到达或逼可以直接到达或逼 近具有此关键码的元素的实际存放地址。近具有此关键码的元素的实际存放地址。 n n 散列函数是一个压缩映象函数散列函数是一个压缩映象函数。关键码集合。关键码集合 比散列表地址集合大得多。因此有可能经过比散列表地址集合大得多。因此有可能经过 散列函数的计算，把不同的关键码映射到同散列函数的计算，把不同的关键码映射到同 一个散列地址上，这就产生了一个散列地址上，这就产生了冲突冲突。 n n 示例：有一组元素，其关键码分别是示例：有一组元素，其关键码分别是 12361, 07251, 03309, 30976 12361, 07251, 03309, 30976 采用的散列函数是采用的散列函数是 hashhash( (x x) = ) = x x % 73 % 73 其中，其中，“ “%”%”是除法取余操作。是除法取余操作。 则有则有：hashhash(12361) = (12361) = hashhash(07251) = (07251) = hashhash(03309) =(03309) = hashhash(30976) = 24(30976) = 24。就是说就是说, , 对不同的关键对不同的关键码码, , 通过散通过散 列函数的计算列函数的计算, , 得到了同一散列地址。得到了同一散列地址。 我们称这些产生冲突的散列地址相同的不同关键码为我们称这些产生冲突的散列地址相同的不同关键码为 同义词同义词。 由于关键码集合比地址集合大得多由于关键码集合比地址集合大得多, , 冲突很难避免。冲突很难避免。 所以对于散列方法所以对于散列方法, , 需要讨论以下两个问题：需要讨论以下两个问题： uu对于给定的一个关键码集合对于给定的一个关键码集合, , 选择一个计算简单且地址分选择一个计算简单且地址分 布比较均匀的散列函数布比较均匀的散列函数, , 避免或尽量减少冲突；避免或尽量减少冲突； uu 拟订解决冲突的方案。拟订解决冲突的方案。 构造散列函数时的几点要求：构造散列函数时的几点要求： n n 散列函数的定义域必须包括需要存储的全部散列函数的定义域必须包括需要存储的全部 关键码关键码, , 如果散列表允许有如果散列表允许有 m m 个地址时个地址时, , 其其 值域必须在值域必须在 0 0 到到 mm- -1 1 之间；之间； n n 散列函数计算出来的地址应能均匀分布在整散列函数计算出来的地址应能均匀分布在整 个地址空间中；个地址空间中； n n 散列函数应是简单的，能在较短的时间内计散列函数应是简单的，能在较短的时间内计 算出结果。算出结果。 散列函数散列函数 除留余数法除留余数法 n n 设散列表中允许地址数为设散列表中允许地址数为 mm, , 取一个不大于取一个不大于 mm, , 但最接近但最接近 于或等于于或等于 m m 的质数的质数 p p 作为除数作为除数, , 利用以下函数把关键码利用以下函数把关键码 转换成散列地址：转换成散列地址： hashhash ( ( keykey ) = ) = keykey % % p p p p m m n n 其中其中, “%”, “%”是整数除法取余的运算，要求这时的质数是整数除法取余的运算，要求这时的质数 p p 不是接近不是接近2 2的幂。的幂。 n n 示例示例: : 有一个关键码有一个关键码 keykey = 962148, = 962148, 散列表大小散列表大小 mm = 25, = 25, 即即 HTHT2525。取质数取质数 p p= 23= 23。散列函数散列函数 hash hash ( ( key key ) =) = key key % % p p。则散列地址为则散列地址为hashhash ( 962148 ) = 962148 % 23 = 12 ( 962148 ) = 962148 % 23 = 12 。 n n 可以按计算出的地址存放记录。需要注意的是可以按计算出的地址存放记录。需要注意的是, , 使用上使用上 面的散列函数计算出来的地址范围是面的散列函数计算出来的地址范围是 0 0到到 22 22, , 因此因此, , 从从2323 到到2424这几个散列地址实际上在一开始是不可能用散列函这几个散列地址实际上在一开始是不可能用散列函 数计算出来的数计算出来的, , 只可能在处理溢出时达到这些地址。只可能在处理溢出时达到这些地址。 散列函数散列函数 数字分析法数字分析法 n n 设有设有 n n 个个 d d 位数位数, , 每一位可能有每一位可能有 r r 种不同的符号。种不同的符号。这这 r r 种不同的符号在各位上出现的频率不一定相同。种不同的符号在各位上出现的频率不一定相同。 可根可根 据散列表的大小据散列表的大小, , 选取其中各种符号分布均匀的若干位选取其中各种符号分布均匀的若干位 作为散列地址。作为散列地址。 n n 计算各位数字中符号分布均匀度计算各位数字中符号分布均匀度 k k 的公式的公式： n n 其中，其中， 表示第表示第 i i 个符号在第个符号在第 k k 位上出现的次数，位上出现的次数，n n/ /r r 表示各种符号在表示各种符号在 n n 个数中均匀出现的期望值。计算出的个数中均匀出现的期望值。计算出的 k k 值越小，表明在该位值越小，表明在该位 ( (第第 k k 位位) ) 各种符号分布得越均各种符号分布得越均 匀。匀。 n n 数字分析法仅适用于事先明确知道表中所有关键码每一数字分析法仅适用于事先明确知道表中所有关键码每一 位数值的分布情况，它完全依赖于关键码集合。如果换位数值的分布情况，它完全依赖于关键码集合。如果换 一个关键码集合，选择哪几位要重新决定。一个关键码集合，选择哪几位要重新决定。 散列函数散列函数 9 4 2 1 4 89 4 2 1 4 8位，位， 1 1 = 57.60 = 57.60 9 4 1 2 6 9 9 4 1 2 6 9位，位， 2 2 = 57.60 = 57.60 9 4 0 5 2 7 9 4 0 5 2 7位，位， 3 3 = 17.60 = 17.60 9 4 1 6 3 0 9 4 1 6 3 0位，位， 4 4 = 5.60 = 5.60 9 4 1 8 0 5 9 4 1 8 0 5位，位， 5 5 = 5.60 = 5.60 9 4 1 5 5 8 9 4 1 5 5 8位，位， 6 6 = 5.60 = 5.60 9 4 2 0 4 7 9 4 2 0 4 7 9 4 0 0 0 1 9 4 0 0 0 1 若散列表地址范围有若散列表地址范围有 3 3 位数字位数字, , 取各关键码取各关键码 的的 位做为记录的散列地址。也可以把位做为记录的散列地址。也可以把 第第，, , 和第和第位相加位相加, , 舍去进位位舍去进位位, , 变成变成 一位数一位数, , 与第与第, , 位合起来作为散列地址。位合起来作为散列地址。 平方取中法平方取中法 n n 此方法在字典处理中使用十分广泛。此方法在字典处理中使用十分广泛。 n n 它先计算构成关键码的标识符的内码的平方它先计算构成关键码的标识符的内码的平方, , 然然 后按照散列表的大小取中间的若干位作为散列地后按照散列表的大小取中间的若干位作为散列地 址。址。 n n 设标识符可以用一个计算机字长的内码表示。因设标识符可以用一个计算机字长的内码表示。因 为内码为内码平方数的中间几位平方数的中间几位一般是由标识符所有字一般是由标识符所有字 符决定符决定, , 所以对不同的标识符计算出的散列地址所以对不同的标识符计算出的散列地址 大多不相同大多不相同, , 即使其中有些字符相同。即使其中有些字符相同。 n n 在平方取中法中在平方取中法中, , 一般取散列地址为一般取散列地址为 2 2 的某次幂的某次幂 。例如。例如, , 若散列地址总数取为若散列地址总数取为 mm = = 2 2 r r ，则对内码则对内码 的平方数取中间的的平方数取中间的 r r 位。如果位。如果 r r = = 3 3，所取得的散所取得的散 列地址参看图的最右一列。列地址参看图的最右一列。 散列函数散列函数 标识符标识符 内码内码 内码的平方内码的平方 散列地址散列地址 A A 0101 0101 001 001 A A1 1 01340134 2 20420420 0 042 042 A A9 9 01440144 2 23423420 0 342 342 B B 0202 4 4 004 004 DMAXDMAX 0415013004150130 2152621526443443617100617100 443 443 DMAXDMAX1 1 04150130340415013034 52644752644735235221514202151420 352 352 AMAX AMAX 0115013001150130 135413542362361710017100 236 236 AMAXAMAX1 1 01150130340115013034 34542434542465265221514202151420 652 652 标识符的八进制内码表示及其平方值 折叠法折叠法 n n 此方法把关键码自左到右分成此方法把关键码自左到右分成位数相等位数相等的几部分的几部分, , 每一每一 部分的位数应与散列表地址位数相同部分的位数应与散列表地址位数相同, , 只有最后一部分只有最后一部分 的位数可以短一些。的位数可以短一些。 n n 把这些部分的数据叠加起来把这些部分的数据叠加起来, , 就可以得到具有该关键码就可以得到具有该关键码 的记录的散列地址。的记录的散列地址。 n n 有两种叠加方法：有两种叠加方法： n n 移位法移位法 把各部分的最后一位对齐相加；把各部分的最后一位对齐相加； n n 分界法分界法 各部分不折断各部分不折断, , 沿各部分的分界来回折叠沿各部分的分界来回折叠, , 然后对齐相加然后对齐相加, , 将相加的结果当做散列地址。将相加的结果当做散列地址。 n n 示例示例: : 设给定的关键码为设给定的关键码为 keykey = 23938587841 = 23938587841, , 若若 存储空间限定存储空间限定 3 3 位位, , 则划分结果为每段则划分结果为每段 3 3 位位. . 上述上述 关键码可划分为关键码可划分为 4 4段：段： 239239 385385 878878 4141 散列函数散列函数 n n 把超出地址位数的最高位删去把超出地址位数的最高位删去, , 仅保留最低仅保留最低的的3 3位，位， 做为可用的散列地址。做为可用的散列地址。 n n 一般当关键码的位数很多，而且关键码每一位上数一般当关键码的位数很多，而且关键码每一位上数 字的分布大致比较均匀时，可用这种方法得到散列字的分布大致比较均匀时，可用这种方法得到散列 地址。地址。 移移 位位 法法 分分 界界 法法 n n 以上介绍了几种常用的散列函数。在实际以上介绍了几种常用的散列函数。在实际 工作中应根据关键码的特点，选用适当的工作中应根据关键码的特点，选用适当的 方法。有人曾用方法。有人曾用“ “轮盘赌轮盘赌” ”的统计分析方法的统计分析方法 对它们进行了模拟分析，结论是平方取中对它们进行了模拟分析，结论是平方取中 法最接近于法最接近于“ “随机化随机化” ”。 散列函数散列函数 处理冲突的闭散列方法处理冲突的闭散列方法 因为任一种散列函数也不能避免产生冲突，因此选因为任一种散列函数也不能避免产生冲突，因此选 择好的解决冲突的方法十分重要。择好的解决冲突的方法十分重要。 为了减少冲突，对散列表加以改造。若设散列表为了减少冲突，对散列表加以改造。若设散列表 HT HT 有有 m m 个地址个地址, , 将其改为将其改为 m m 个桶个桶。其桶号与散列地。其桶号与散列地 址一一对应址一一对应, , 第第 i i (0 (0 i i mm) ) 个桶的桶号即为第个桶的桶号即为第 i i 个散个散 列地址。列地址。 每个桶可存放每个桶可存放 s s 个表项个表项, , 这些表项的关键码互为同这些表项的关键码互为同 义词。如果对两个不同表项的关键码用散列函数计算义词。如果对两个不同表项的关键码用散列函数计算 得到同一个散列地址，就产生了冲突，它们可以放在得到同一个散列地址，就产生了冲突，它们可以放在 同一个桶内的不同位置。同一个桶内的不同位置。 n n 只有当桶内所有只有当桶内所有 s s 个表项位置都放满元素后再加个表项位置都放满元素后再加 入表项才会产生入表项才会产生溢出溢出。 n n 通常桶的大小通常桶的大小 s s 取的比较小取的比较小, , 因此在桶内大多采用因此在桶内大多采用 顺序搜索顺序搜索。 n n 闭散列也叫做闭散列也叫做开地址法开地址法。在闭散列情形。在闭散列情形, , 所有的桶所有的桶 都直接放在散列表数组中。因此每个桶只有一个元都直接放在散列表数组中。因此每个桶只有一个元 素素 ( ( s s = 1 ) = 1 )。 n n 若设散列表中各桶的编址为若设散列表中各桶的编址为 0 0 到到 mm- -1, 1, 当要加入一当要加入一 个表项个表项 R R 2 2 时时, , 用它的关键码用它的关键码 R R 2 2 . .keykey, , 通过散列函数通过散列函数 hash hash ( ( R R 2 2 . .key key ) ) 的计算，得到它的存放桶号的计算，得到它的存放桶号 j j。 n n 但在存放时发现此桶已被另一个表项但在存放时发现此桶已被另一个表项 R R 1 1 占据占据, , 发生发生 了冲突了冲突, , 必须处理冲突。为此必须处理冲突。为此, , 需把需把 R R 2 2 存放到表中存放到表中“ “ 下一个下一个” ”空桶中。空桶中。 如果表未被装满如果表未被装满, , 则在允许的范则在允许的范 围内必定还有空桶。围内必定还有空桶。 处理冲突的闭散列方法处理冲突的闭散列方法 线性探查法线性探查法 ( (Linear Probing)Linear Probing) 假设给出一组元素，它们的关键码为假设给出一组元素，它们的关键码为 3737，2525，1414，3636 ，4949，6868，5757，1111，散列表散列表HT12HT12，表的大小表的大小m=12m=12，采采 用的散列函数是：用的散列函数是： HashHash ( (x x) = ) = x%11 x%11 /11是小于等于m，又最接近m的质数 则上述关键码在散列表中散列位置如下图所示：则上述关键码在散列表中散列位置如下图所示： 找下一个空桶找下一个空桶HH i i 的公式：的公式： HH i i (H (Hi-1 i-1 1)%m 1)%m 或或 HH i i = ( H = ( H 0 0 + i ) % m + i ) % m 处理冲突的闭散列方法处理冲突的闭散列方法 11 68 25 37 14 36 49 57 0 1 2 3 4 5 6 7 8 9 10 n n 当发生冲突时当发生冲突时, , 探查下一个桶。当循环探查下一个桶。当循环 mm- -1 1 次后就会回到开始探查时的位置次后就会回到开始探查时的位置, , 说明待查说明待查 关键码不在表内关键码不在表内, , 而且表已而且表已满满, , 不能再插入不能再插入 新关键码。新关键码。 n n 用用平均搜索长度平均搜索长度ASL ASL ( (AveragyAveragy Search Search LengthLength) ) 衡量散列方法的搜索性能。衡量散列方法的搜索性能。 n n 根据搜索成功与否，它又有根据搜索成功与否，它又有搜索成功的平均搜索成功的平均 搜索长度搜索长度ASLsuccASLsucc和和搜索不成功的平均搜索搜索不成功的平均搜索 长度长度ASLunsuccASLunsucc之分。之分。 n n 搜索成功的平均搜索长度搜索成功的平均搜索长度 ASLsuccASLsucc 是指是指搜索搜索 到表中已有元素的平均探查次数到表中已有元素的平均探查次数。它是找到。它是找到 表中各个已有元素的探查次数的平均值。表中各个已有元素的探查次数的平均值。 n n 搜索不成功的平均搜索长度搜索不成功的平均搜索长度 ASLunsuccASLunsucc 是指是指 在表中搜索不到待查的元素，但找到插入位置在表中搜索不到待查的元素，但找到插入位置 的平均探查次数的平均探查次数。它是表中所有可能散列到的。它是表中所有可能散列到的 位置上要插入新元素时为找到空桶的探查次数位置上要插入新元素时为找到空桶的探查次数 的平均值。的平均值。 n n 在使用线性探查法对示例进行搜索时，在使用线性探查法对示例进行搜索时，搜索成搜索成 功的平均搜索长度为：功的平均搜索长度为： n n 搜索不成功的平均搜索长度为搜索不成功的平均搜索长度为： n n 在闭散列的情形下不能随便物理删除表中已有的元素在闭散列的情形下不能随便物理删除表中已有的元素 。因为若删除元素会影响其他元素的搜索。因为若删除元素会影响其他元素的搜索。 n n 若想删除一个表项若想删除一个表项, , 只能给它做一个删除标记只能给它做一个删除标记deleteddeleted进进 行逻辑删除行逻辑删除, , 不能把它真正删去。不能把它真正删去。 n n 逻辑删除的副作用逻辑删除的副作用是：在执行多次删除后是：在执行多次删除后, , 表面上看起表面上看起 来散列表很满来散列表很满, , 实际上有许多位置没有利用。实际上有许多位置没有利用。 n n 线性探查方法容易产生线性探查方法容易产生“ “堆积堆积”, ”, 不同探查序列的关键码不同探查序列的关键码 占据可用的空桶占据可用的空桶, , 为寻找某一关键码需要经历不同的探为寻找某一关键码需要经历不同的探 查序列查序列, , 导致搜索时间增加。如寻找导致搜索时间增加。如寻找5757比较了比较了7 7次。次。 注意：注意： 算法分析算法分析 n n 设散列表的设散列表的装填因子装填因子为为 = = n n / / ( (s s* *mm) )，其中其中 n n 是表中已有的元素个数是表中已有的元素个数，s s 是每个桶中最是每个桶中最 多可容纳元素个数多可容纳元素个数，m m 是表中的桶数是表中的桶数。 n n 可用可用 表明散列表的装满程度表明散列表的装满程度。 越大越大, , 表表 中元素数越多中元素数越多, , 表装得越满表装得越满, , 发生冲突可能性发生冲突可能性 越大。越大。 n n 通过对线性探查法的分析可知通过对线性探查法的分析可知, , 为搜索一个为搜索一个 关键码所需进行的探查次数的期望值关键码所需进行的探查次数的期望值 P P 大约大约 是是 (2-(2- )/(2-2)/(2-2 ) )。虽然平均探查次数较小。虽然平均探查次数较小, , 但但 在最坏情况下的探查次数会相当大。在最坏情况下的探查次数会相当大。 二次探查法二次探查法 ( (quadratic probing)quadratic probing) n n 为改善为改善“ “堆积堆积” ”问题问题, , 减少为完成搜索所需的平均探减少为完成搜索所需的平均探 查次数查次数, , 可使用二次探查法。可使用二次探查法。 n n 通过某一个散列函数对表项的关键码通过某一个散列函数对表项的关键码 x x 进行计算进行计算, , 得到桶号得到桶号, , 它是一个非负整数。它是一个非负整数。 HH 0 0 = = hashhash( (x x) ) n n 二次探查法在表中寻找二次探查法在表中寻找“ “下一个下一个” ”空桶的公式：空桶的公式： HH i i = (= (HH 0 0 + + i i 2 2 ) % ) % mm, , H H i i = (= (HH 0 0 - - i i 2 2 ) % ) % mm, , i i = 1, 2, , ( = 1, 2, , (mm- -1)/21)/2 n n 式中的式中的 m m 是表的大小，它应是一个值为是表的大小，它应是一个值为 4 4k k+3+3 的质的质 数，其中数，其中 k k 是一个整数。是一个整数。如如 3, 7, 11, 19, 23, 31, 43, 3, 7, 11, 19, 23, 31, 43, 59, 127, 251, 503, 59, 127, 251, 503, 。 处理冲突的闭散列方法处理冲突的闭散列方法 n n 探查序列如探查序列如 HH 0 0 , , HH 0 0 +1, +1, HH 0 0 - -1, 1, HH 0 0 +4, +4, HH 0 0- - 4, 4, 。 n n 在做在做 ( (H H 0 0 - - i i2 2 ) ) % % m m 的运算的运算时时, , 当当 H H 0 0 - - i i2 2 0 0 时时, , 运算结果运算结果 也是负数。实际算式可改为也是负数。实际算式可改为 j = (H0 - i2 ) % m, if ( j 0 ) j += m n n 示例：给出一组关键码示例：给出一组关键码 37,25,14,36,49,68,57,11 37,25,14,36,49,68,57,11。 散列函数为散列函数为：HashHash ( (x x) )x%19x%19 n n 用它计算可得用它计算可得 Hash Hash (37) = 18 (37) = 18 HashHash (25) = 6 (25) = 6 Hash Hash (14) = 14 (14) = 14 HashHash (36) = 17 (36) = 17 Hash Hash (49) = 11 (49) = 11 HashHash (68) = 11 (68) = 11 Hash Hash (57) = 0 (57) = 0 HashHash (11) = 11 (11) = 11 57 25 11 49 68 14 36 37 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 n n 使用使用二次探查法二次探查法处理冲突时的处理冲突时的搜索成功的平搜索成功的平 均搜索长度均搜索长度为：为： n n 搜索不成功的平均搜索长度搜索不成功的平均搜索长度为：为： 设散列表桶数为设散列表桶数为 mm, , 待查关键码为待查关键码为 x x, , 第一次第一次 通过散列函数计算出的桶号为通过散列函数计算出的桶号为 HH 0 0 = =hashhash( (x x) )。当当 发生冲突时，第发生冲突时，第 i i- -1 1 次和第次和第 i i 次计算出来的次计算出来的“ “下下 一个一个” ”桶号分别为：桶号分别为： 相减，可以得到：相减，可以得到： 从而从而 n n 只要知道上一次的桶号只要知道上一次的桶号 和和 , ,当当 i i 增加增加 1 1 时可以从时可以从 和和 简单地导出简单地导出 和和 ，不需要每次计算不需要每次计算 i i 的平的平 方方。 n n 在冲突处理算法在冲突处理算法 FindFind 中中, ,首先求出首先求出 HH 0 0 作为当前桶号作为当前桶号 CurrentPosCurrentPos, , 当发生冲突时求当发生冲突时求“ “下一个下一个” ”桶号，桶号，i i = 1 = 1。 n n 此时用一个标志此时用一个标志 odd odd 控制是加控制是加 i i 2 2 还是减还是减 i i 2 2 。 n n 若若 odd =odd = 0 0 加加 i i 2 2 ，并置并置 oddodd = 1 = 1； n n 若若 odd =odd = 1 1 减减 i i 2 2 ，并置并置 oddodd = 0 = 0。 n n 下次下次 i i 进一后，又可由进一后，又可由 odd odd 控制先加后减。控制先加后减。 n n 可以证明可以证明, , 当当表的长度表的长度TableSizeTableSize为质数为质数且且表的装填因表的装填因 子子 不超过不超过 0.50.5 时时, , 新的表项新的表项 e e 一定能够插入一定能够插入, , 且任何且任何 一个位置不会被探查两次。因此，只要表中至少有一一个位置不会被探查两次。因此，只要表中至少有一 半空，就不会有表满问题。半空，就不会有表满问题。 n n 删除也只能进行逻辑删除。删除也只能进行逻辑删除。 双散列法双散列法 n n 使用双散列方法时使用双散列方法时, , 需要两个散列函数。第一个散列函需要两个散列函数。第一个散列函 数数 HashHash( ( ) ) 按按元素的关键码元素的关键码 keykey 计算元素所在的桶号计算元素所在的桶号 HH 0 0 = = HashHash( (keykey) )。一旦发生冲突，利用第二个散列函数一旦发生冲突，利用第二个散列函数 ReHashReHash( ( ) )计算计算“ “下一个下一个” ”桶的移位量。它的取值应当是桶的移位量。它的取值应当是 小于地址空间大小小于地址空间大小TableSizeTableSize，且且与与TableSizeTableSize互质的正互质的正 整数整数。 n n 寻找寻找“ “下一个下一个” ”桶的公式为：桶的公式为： j j = = HH 0 0 = = HashHash( (keykey) ) p p = = ReHashReHash( (keykey) ) j j = ( = ( j j + + p p ) % ) % mm 或或 HH i i = (= (HH 0 0 + + i i * * ReHashReHash( (keykey) ) % ) ) % mm 处理冲突的闭散列方法处理冲突的闭散列方法 n n 示例：给出一组元素关键码示例：给出一组元素关键码 22, 41, 53, 46, 30, 13, 01, 67 22, 41, 53, 46, 30, 13, 01, 67 。散列函数为：。散列函数为： HashHash( (x x) )(3(3x x) % 11) % 11。 n n 散列表为散