《数据结构教程第6章集合与字典》由会员分享，可在线阅读，更多相关《数据结构教程第6章集合与字典（62页珍藏版）》请在金锄头文库上搜索。
1、n n集合及其表示n n并查集与等价类n n字典n n跳表n n散列数据结构教程第6章集合与字典集合基本概念6.1.1 集合及其表示n n集合是成员( (对象或元素) )的一个群集。集合中的成员可以是原子( (单元素) )，也可以是集合。n n集合的成员必须互不相同。n n在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。数据结构教程第6章集合与字典 colour = red, orange, yellow, green, black, colour = red, orange, yellow, green, black, blue
2、, purple, white blue, purple, white name = An, Cao, Liu, Ma, Peng, Wang, name = An, Cao, Liu, Ma, Peng, Wang, zhang zhang n n集合中的成员一般是集合中的成员一般是无序无序的，但在表示它时，的，但在表示它时，常设定常设定集合中的单元素集合中的单元素具有线性有序关系具有线性有序关系，此，此关系可记作关系可记作“ “”，表示，表示“ “优先于优先于” ” ；整数、字符；整数、字符和字符串都有一个自然线性顺序。指针也可依和字符串都有一个自然线性顺序。指针也可依据其在序列中安排的位
3、置给予一个线性顺序。据其在序列中安排的位置给予一个线性顺序。n n某些集合保存的是实际数值，某些集合保存的某些集合保存的是实际数值，某些集合保存的是表示元素是否在集合中的指示信息。是表示元素是否在集合中的指示信息。n n要求每个元素在集合中只出现一次，但要求每个元素在集合中只出现一次，但多种集多种集合合允许元素重复出现。允许元素重复出现。数据结构教程第6章集合与字典集合(Set)的抽象数据类型template class Set public: virtual Set ( ) =0; virtual MakeEmpty ( )=0; virtual bool AddMember (const
4、T x)=0; virtual bool DelMember ( const T x)=0;A B 或 A+B A B 或 A B A- -BAAABBB数据结构教程第6章集合与字典virtual Set unionWith const Set & R)=0; virtual Set intersectWith (const Set & R)=0;virtual Set differenceFrom (const Set & R)=0;virtual bool Contains (const T x)=0;virtual bool subSet (const Set& R)=0; virtua
5、l bool operator= (const Set& R)=0;数据结构教程第6章集合与字典6.1.2 用位向量实现集合抽象数据类型n n 当集合是全集合 0, 1, 2, , n 的一个子集，且 n是不大的整数时，可用位(0, 1)向量来实现集合。n n 当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数 0, 1, 2, 的一一对应关系，用位向量来表示该集合的子集。数据结构教程第6章集合与字典集合的位向量(bit Vector)类的定义#include const int DefaultSize = 50;class bitSet private: unsigned s
6、hort * bitVector; int setSize, vectorSize;public: bitSet ( int sz = DefaultSize ); bitSet ( ) delete bitVector; 数据结构教程第6章集合与字典 void makeEmpty ( ) for (int i = 0; i vectorSize; i+) bitVectori = 0; int getMember (const T x); void putMember(const T x, int v); bool addMember (const T x); bool delMember
7、( const T x ); bitSet& operator = (const bitSet& R); bitSet operator + (const bitSet& R); bitSet operator * (const bitSet& R); bitSet operator - (const bitSet& R);数据结构教程第6章集合与字典 bool Contains ( const T x ); bool subSet (bitSet& R);/判thisthis是否R R的子集 bool operator = (bitSet& R); friend istream& opera
8、tor(istream& in, bitSet& R); friend istream& operator(istream& out, bitSet& R);使用示例bitSet s1, s2, s3, s4, s5; int index, equal; for ( int k = 0; k 10; k+ ) /集合赋值 s1.AddMember( k ); s2.AddMember( k +7 ); / s1 : 0, 1, 2, , 9 , s2 : 7, 8, 9, , 16 数据结构教程第6章集合与字典6.1.3 用有序链表实现集合的抽象数据类型用带表头结点的有序链表表示集合 firs
9、tfirst081723354972 n n用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。n n各结点所表示的成员 e0, e1, , en 在链表中按升序排列，即 e0 e1 en。n n集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。数据结构教程第6章集合与字典template struct SetNode T data; SetNode * link; SetNode (const T& x, SetNode*next=NULL) : data (x), link (next) ; 集合的有序链表类的定义template class LinkedSet pr
10、ivate: SetNode *first, *last; /有序链表的表头指针, 表尾指针数据结构教程第6章集合与字典public: LinkedSet( ) first = last = new SetNode; /构造函数 LinkedSet( ) MakeEmpty( ); delete first; void MakeEmpty ( ); /置空集合 bool AddMember ( const T& x ); bool DelMember ( const T& x ); LinkedSet & operator = (LinkedSet &R); /复制集合R到this Linke
11、dSet & operator + (LinkedSet &R); /求集合this与集合R的并 LinkedSet & operator * (LinkedSet &R); /求集合this与集合R的交 LinkedSet & operator - (LinkedSet &R); /求集合this与集合R的差 bool Contains ( const T& x ); /判x是否集合的成员集合的有序链表类的定义数据结构教程第6章集合与字典 bool operator = (LinkedSet & R);/判this是否与R相等 bool Min(T& x ); /返回集合中最小元素值 boo
12、l Max(T& x); /返回集合中最大元素值 bool subSet(LinkedSet& R); /判this是否R的子集集合的有序链表类的定义数据结构教程第6章集合与字典6.2.1 并查集 (Union-Find Sets)n n并查集支持以下三种操作：uu Union (Root1, Root2) /并操作uu Find (x) /搜索操作uu UFSets (s) /构造函数n n对于并查集来说，每个集合用一棵树表示。n n为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到 n- -1。其中 n 是最大元素个数。数据结构教程第6章集合与字典n n在在双亲表示双亲表示中，中
13、，第第 i i 个数组元素代表包含集合元个数组元素代表包含集合元素素 i i 的树结点的树结点。根结点的双亲为。根结点的双亲为- - - -1 1，表示集合中，表示集合中的元素个数。的元素个数。n n在同一棵树上所有结点所代表的集合元素在同一在同一棵树上所有结点所代表的集合元素在同一个子集合中。个子集合中。n n初初始始时时, , 用用构构造造函函数数 UFSets(s) UFSets(s) 构构造造一一个个森森林林, , 每每棵棵树树只只有有一一个个结结点点, , 表表示示集集合合中中各各元元素素自自成成一一个个子集合。子集合。n n用用 Find(i) Find(i) 寻寻找找集集合合元元
14、素素 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) 将它们合并到一个集合中。将它们合并到一个集合中。数据结构教程第6章集合与字典S1 S2的可能的表示方法下标下标parent集合 S S1 1, , S S2 2 和 S S3 3 的双亲表示- -1 4 - -1 2
15、- -1 2 0 0 0 40 1 2 3 4 5 6 7 8 907684194190876数据结构教程第6章集合与字典const int DefaultSize=10;class UFSetspublic: 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; 并查集类的定义数据结构教程第6章集
16、合与字典UFSets:UFSets(int sz) size=sz; parent=new intsize; for(int i=0;isize;i+) parenti=-1; void UFSets : Union ( int Root1, int Root2 ) /求两个不相交集合Root1与Root2的并 parentRoot1+= parentRoot2; parentRoot2=Root1; /将Root2连接到Root1下面成员函数的实现数据结构教程第6章集合与字典 -5 0 1 2 35 0 1 2 3parentParent4 =3 Parent3 =2Parent2 =1Pa
17、rent1 =0Parent0 =-50 1 2 3 4int UFSets : Find ( int x ) if ( parent x 0 ) return x; else return Find (parent x); 数据结构教程第6章集合与字典6.3 字典(Dictionary)n n以集合为基础，支持Member、Insert、Remove三种运算的抽象数据类型叫做字典。n n字典的概念：n字典是一些元素的集合，每个元素有一个称作关键码的域。n在讨论字典抽象数据类型时，把字典定义为对的集合。n字典的操作：n确定一个指定的名字是否在字典中；n搜索出该名字的属性；n修改该名字的的属性；
18、n插入一个新的名字及其属性；n删除一个名字及其属性。数据结构教程第6章集合与字典字典的抽象数据类型const int DefaultSize = 26;templateclass 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
19、种：种：SearchSearch( (搜搜索索) )、InsertInsert ( (插入插入) )、RemoveRemove ( (删除删除) )。n n在选择字典的表示时，必须确保这几个操作的实现。在选择字典的表示时，必须确保这几个操作的实现。数据结构教程第6章集合与字典 考虑到搜索效率, 可以用顺序表方式、二叉搜索树或多路搜索树方式组织字典。本章介绍3种字典的组织方式：线性表、跳表和散列表。字典的线性表描述线性表描述： 字典可以保存在线性序列(e1,e2,)中，其中ei是字典中的元素，其关键码从左到右依次增大。 对于这种描述方式，有有序顺序表和有序链表。数据结构教程第6章集合与字典有序链
20、表的类定义templatestruct ChainNode E data; ChainNode* link; ChainNode( ):link(NULL) ; ChainNode(E& e1, ChainNode* next=NULL): data(e1), link(next) ;templateclass SortedChainpublic: SortedChain( ) first= new ChainNode; assert(first!=NULL); SortedChain( );数据结构教程第6章集合与字典有序链表的类定义 ChainNode* Search(const K k1
21、)const; void Insert(const K k1, E& e1); bool Remove(const K k1, E& e1); 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(
22、n)O(n)。数据结构教程第6章集合与字典6.4 跳表(Skip List)n在链表的中部结点增加一个指针，以减少搜索时的比较次数。101020203030404050506060707010102020303040405050606070701010202030304040505060607070数据结构教程第6章集合与字典6.5 散列 (Hashing) 散列表是表示集合和字典的另一种有效方法，它提供了一种完全不同的存储和搜索方式，通过将关键码映射到表中某个位置上来存储元素，然后根据关键码用用样的方式直接访问。数据结构教程第6章集合与字典散列方法n n散列方法在元素存储位置与其关键码之间建
23、立一个确定的对应函数关系Hash( )，使每个关键码与结构中一个唯一存储位置相对应： Address Hash (key )n n在搜索时, 先对元素的关键码进行函数计算,把函数值当做元素的存储位置, 在结构中按此位置取元素比较。若关键码相等, 则搜索成功。在存放元素时, 依相同函数计算存储位置, 并按此位置存放。这种方法就是散列方法。数据结构教程第6章集合与字典 n n在散列方法中使用的转换函数叫做散列函数。按此方法构造出来的表或结构就叫做散列表。n n使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或逼近具有此关键码的元素的实际存放地址。n n散列函数是一个压
24、缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突。数据结构教程第6章集合与字典n n示例：有一组元素，其关键码分别是示例：有一组元素，其关键码分别是 12361, 07251, 03309, 3097612361, 07251, 03309, 30976 采用的散列函数是采用的散列函数是 hashhash( (x x) = ) = x x % 73 % 73 其中，其中，“ “%”%”是除法取余操作。是除法取余操作。 则有：则有：hashhash(12361) = (12361) = hashhash(07251)
25、 = (07251) = hashhash(03309) =(03309) = hashhash(30976) = 24(30976) = 24。就是说就是说, , 对不同的关键码对不同的关键码, , 通过散通过散列函数的计算列函数的计算, , 得到了同一散列地址。得到了同一散列地址。我们称这些产生冲突的散列地址相同的不同关键码为我们称这些产生冲突的散列地址相同的不同关键码为同义词同义词。 由于关键码集合比地址集合大得多由于关键码集合比地址集合大得多, , 冲突很难避免。冲突很难避免。所以对于散列方法所以对于散列方法, , 需要讨论以下两个问题：需要讨论以下两个问题：uu对于给定的一个关键码集
26、合对于给定的一个关键码集合, , 选择一个计算简单且地址分选择一个计算简单且地址分布比较均匀的散列函数布比较均匀的散列函数, , 避免或尽量减少冲突；避免或尽量减少冲突；uu 拟订解决冲突的方案。拟订解决冲突的方案。 数据结构教程第6章集合与字典构造散列函数时的几点要求：n n散列函数的定义域必须包括需要存储的全部 关键码, 如果散列表允许有 m 个地址时, 其 值域必须在 0 到 m- -1 之间；n n散列函数计算出来的地址应能均匀分布在整个地址空间中；n n散列函数应是简单的，能在较短的时间内计 算出结果。散列函数数据结构教程第6章集合与字典除留余数法除留余数法n n设散列表中允许地址数
27、为设散列表中允许地址数为 mm, , 取一个不大于取一个不大于 mm, , 但最接近但最接近于或等于于或等于 m m 的质数的质数 p p 作为除数作为除数, , 利用以下函数把关键码利用以下函数把关键码转换成散列地址：转换成散列地址： hashhash ( ( keykey ) = ) = keykey % % p p p p m mn n其中其中, “%”, “%”是整数除法取余的运算，要求这时的质数是整数除法取余的运算，要求这时的质数 p p 不是接近不是接近2 2的幂。的幂。n n示例示例: : 有一个关键码有一个关键码 keykey = 962148, = 962148, 散列表大小
28、散列表大小 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到到 2222, , 因此因此, , 从从
29、2323到到2424这几个散列地址实际上在一开始是不可能用散列函这几个散列地址实际上在一开始是不可能用散列函数计算出来的数计算出来的, , 只可能在处理溢出时达到这些地址。只可能在处理溢出时达到这些地址。散列函数数据结构教程第6章集合与字典数字分析法数字分析法 n n设有设有 n n 个个 d d 位数位数, , 每一位可能有每一位可能有 r r 种不同的符号。这种不同的符号。这 r r 种不同的符号在各位上出现的频率不一定相同。种不同的符号在各位上出现的频率不一定相同。 可根可根据散列表的大小据散列表的大小, , 选取其中各种符号分布均匀的若干位选取其中各种符号分布均匀的若干位作为散列地址。
30、作为散列地址。n n计算各位数字中符号分布均匀度计算各位数字中符号分布均匀度 k k 的公式：的公式：n n其中，其中， 表示第表示第 i i 个符号在第个符号在第 k k 位上出现的次数，位上出现的次数，n n/ /r r 表表示各种符号在示各种符号在 n n 个数中均匀出现的期望值。计算出的个数中均匀出现的期望值。计算出的 k k 值越小，表明在该位值越小，表明在该位 ( (第第 k k 位位) ) 各种符号分布得越均匀。各种符号分布得越均匀。n n数字分析法仅适用于事先明确知道表中所有关键码每一数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果
31、换位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。一个关键码集合，选择哪几位要重新决定。 散列函数数据结构教程第6章集合与字典 9 4 2 1 4 8位， 1 = 57.60 9 4 1 2 6 9位， 2 = 57.60 9 4 0 5 2 7位， 3 = 17.60 9 4 1 6 3 0位， 4 = 5.60 9 4 1 8 0 5位， 5 = 5.60 9 4 1 5 5 8位， 6 = 5.60 9 4 2 0 4 7 9 4 0 0 0 1 若散列表地址范围有 3 位数字, 取各关键码的 位做为记录的散列地址。也可以把第，, 和第位相加, 舍去
32、进位位, 变成一位数, 与第, 位合起来作为散列地址。数据结构教程第6章集合与字典平方取中法n n此方法在字典处理中使用十分广泛。n n它先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址。n n设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定, 所以对不同的标识符计算出的散列地址大多不相同, 即使其中有些字符相同。n n在平方取中法中, 一般取散列地址为 2 的某次幂。例如, 若散列地址总数取为 m = 2r，则对内码的平方数取中间的 r 位。如果 r = 3，所取得的散列地址参看图的最右一列。散列函数数据结构教程
33、第6章集合与字典 标识符 内码 内码的平方 散列地址A 01 01 001A1 0134 20420 042A9 0144 23420 342 B 02 4 004 DMAX 21526443617100 443DMAX1 0415013034 526447352 352 AMAX 135423617100 236AMAX1 0115013034 345424652 652标识符的八进制内码表示及其平方值数据结构教程第6章集合与字典折叠法n n此方法把关键码自左到右分成此方法把关键码自左到右分成位数相等位数相等的几部分的几部分, , 每一每一部分的位数应与散列表地址位数相同部分的位数应与散列表
34、地址位数相同, , 只有最后一部分只有最后一部分的位数可以短一些。的位数可以短一些。n n把这些部分的数据叠加起来把这些部分的数据叠加起来, , 就可以得到具有该关键码就可以得到具有该关键码的记录的散列地址。的记录的散列地址。n n有两种叠加方法：有两种叠加方法：n n移位法移位法 把各部分的最后一位对齐相加；把各部分的最后一位对齐相加；n n分界法分界法 各部分不折断各部分不折断, , 沿各部分的分界来回折叠沿各部分的分界来回折叠, , 然后对齐相加然后对齐相加, , 将相加的结果当做散列地址。将相加的结果当做散列地址。n n示例: 设给定的关键码为 key = 23938587841, 若
35、存储空间限定 3 位, 则划分结果为每段 3 位. 上述关键码可划分为 4段： 239 385 878 41散列函数数据结构教程第6章集合与字典n n把超出地址位数的最高位删去把超出地址位数的最高位删去, , 仅保留最低的仅保留最低的3 3位，位，做为可用的散列地址。做为可用的散列地址。n n一一般般当当关关键键码码的的位位数数很很多多，而而且且关关键键码码每每一一位位上上数数字字的的分分布布大大致致比比较较均均匀匀时时，可可用用这这种种方方法法得得到到散散列列地址。地址。 移位法 分界法数据结构教程第6章集合与字典n n以上介绍了几种常用的散列函数。在实际工作中应根据关键码的特点，选用适当的
36、方法。有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”。散列函数数据结构教程第6章集合与字典 处理冲突的闭散列方法 因为任一种散列函数也不能避免产生冲突，因此选因为任一种散列函数也不能避免产生冲突，因此选择好的解决冲突的方法十分重要。择好的解决冲突的方法十分重要。 为了减少冲突，对散列表加以改造。若设散列表为了减少冲突，对散列表加以改造。若设散列表 HT HT 有有 m m 个地址个地址, , 将其改为将其改为 m m 个桶。其桶号与散列地个桶。其桶号与散列地址一一对应址一一对应, , 第第 i i (0 (0 i i mm) ) 个桶的桶号即为第个桶的
37、桶号即为第 i i 个散个散列地址。列地址。 每个桶可存放每个桶可存放 s s 个表项个表项, , 这些表项的关键码互为同这些表项的关键码互为同义词。如果对两个不同表项的关键码用散列函数计算义词。如果对两个不同表项的关键码用散列函数计算得到同一个散列地址，就产生了冲突，它们可以放在得到同一个散列地址，就产生了冲突，它们可以放在同一个桶内的不同位置。同一个桶内的不同位置。数据结构教程第6章集合与字典n n只有当桶内所有只有当桶内所有 s s 个表项位置都放满元素后再加个表项位置都放满元素后再加入表项才会产生入表项才会产生溢出溢出。n n通常桶的大小通常桶的大小 s s 取的比较小取的比较小, ,
38、 因此在桶内大多采用因此在桶内大多采用顺序搜索顺序搜索。n n闭散列也叫做闭散列也叫做开地址法开地址法。在闭散列情形。在闭散列情形, , 所有的桶所有的桶都直接放在散列表数组中。因此每个桶只有一个元都直接放在散列表数组中。因此每个桶只有一个元素素 ( ( s s = 1 ) = 1 )。n n若设散列表中各桶的编址为若设散列表中各桶的编址为 0 0 到到 mm- - - -1, 1, 当要加入一当要加入一个表项个表项 R R2 2时时, , 用它的关键码用它的关键码 R R2 2. .keykey, , 通过散列函数通过散列函数 hash hash ( ( R R2 2. .key key )
39、 ) 的计算，得到它的存放桶号的计算，得到它的存放桶号 j j。n n但在存放时发现此桶已被另一个表项但在存放时发现此桶已被另一个表项 R R1 1 占据占据, , 发生发生了冲突了冲突, , 必须处理冲突。为此必须处理冲突。为此, , 需把需把 R R2 2 存放到表中存放到表中“ “下一个下一个” ”空桶中。空桶中。 如果表未被装满如果表未被装满, , 则在允许的范则在允许的范围内必定还有空桶。围内必定还有空桶。 处理冲突的闭散列方法数据结构教程第6章集合与字典线性探查法线性探查法 (Linear Probing)(Linear Probing) 假设给出一组元素，它们的关键码为假设给出一
40、组元素，它们的关键码为 3737，2525，1414，3636，4949，6868，5757，1111，散列表，散列表HT12HT12，表的大小，表的大小m=12m=12，采，采用的散列函数是：用的散列函数是： HashHash ( (x x) = ) = x%11 x%11 /11/11是小于等于m m，又最接近m m的质数则上述关键码在散列表中散列位置如下图所示：则上述关键码在散列表中散列位置如下图所示：找下一个空桶找下一个空桶HHi i的公式：的公式：HHi i (H(Hi-1i-1 1)%m 1)%m 或或 HHi i = ( H = ( H0 0 + i ) % m + i ) %
41、m 处理冲突的闭散列方法1 11 68 25 3737 14 36 49 57 0 1 2 3 4 5 6 7 8 9 10数据结构教程第6章集合与字典n n当发生冲突时, 探查下一个桶。当循环 m- -1次后就会回到开始探查时的位置, 说明待查关键码不在表内, 而且表已满, 不能再插入新关键码。n n用平均搜索长度ASL (Averagy Search Length) 衡量散列方法的搜索性能。n n根据搜索成功与否，它又有搜索成功的平均搜索长度ASLsucc和搜索不成功的平均搜索长度ASLunsucc之分。n n搜索成功的平均搜索长度 ASLsucc 是指搜索到表中已有元素的平均探查次数。它
42、是找到表中各个已有元素的探查次数的平均值。数据结构教程第6章集合与字典n n搜索不成功的平均搜索长度 ASLunsucc 是指在表中搜索不到待查的元素，但找到插入位置的平均探查次数。它是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。n n在使用线性探查法对示例进行搜索时，搜索成功的平均搜索长度为：n n搜索不成功的平均搜索长度为：数据结构教程第6章集合与字典n n在闭散列的情形下不能随便物理删除表中已有的元素。在闭散列的情形下不能随便物理删除表中已有的元素。因为若删除元素会影响其他元素的搜索。因为若删除元素会影响其他元素的搜索。n n若想删除一个表项若想删除一个表项,
43、, 只能给它做一个删除标记只能给它做一个删除标记deleteddeleted进进行逻辑删除行逻辑删除, , 不能把它真正删去。不能把它真正删去。n n逻辑删除的副作用逻辑删除的副作用是：在执行多次删除后是：在执行多次删除后, , 表面上看起表面上看起来散列表很满来散列表很满, , 实际上有许多位置没有利用。实际上有许多位置没有利用。n n线性探查方法容易产生线性探查方法容易产生“ “堆积堆积” ”, , 不同探查序列的关键码不同探查序列的关键码占据可用的空桶占据可用的空桶, , 为寻找某一关键码需要经历不同的探为寻找某一关键码需要经历不同的探查序列查序列, , 导致搜索时间增加。如寻找导致搜索
44、时间增加。如寻找5757比较了比较了7 7次。次。注意：数据结构教程第6章集合与字典算法分析n n设散列表的装填因子为 = n / (s*m)，其中 n 是表中已有的元素个数，s 是每个桶中最多可容纳元素个数，m 是表中的桶数。n n可用 表明散列表的装满程度。 越大, 表中元素数越多, 表装得越满, 发生冲突可能性越大。n n通过对线性探查法的分析可知, 为搜索一个关键码所需进行的探查次数的期望值 P 大约是 (2- )/(2-2 )。虽然平均探查次数较小, 但在最坏情况下的探查次数会相当大。数据结构教程第6章集合与字典二次探查法二次探查法 (quadratic probing)(quadr
45、atic probing)n n为改善为改善“ “堆积堆积” ”问题问题, , 减少为完成搜索所需的平均探减少为完成搜索所需的平均探查次数查次数, , 可使用二次探查法。可使用二次探查法。n n通过某一个散列函数对表项的关键码通过某一个散列函数对表项的关键码 x x 进行计算进行计算, , 得到桶号得到桶号, , 它是一个非负整数。它是一个非负整数。 HH0 0 = = hashhash( (x x) )n n二次探查法在表中寻找二次探查法在表中寻找“ “下一个下一个” ”空桶的公式：空桶的公式： HHi i = (= (HH0 0 + + i i 2 2 ) % ) % mm, , H Hi
46、 i = (= (HH0 0 - - - - i i 2 2 ) % ) % mm, , i i = 1, 2, , ( = 1, 2, , (mm- - - -1)/21)/2n n式中的式中的 m m 是表的大小，它应是一个值为是表的大小，它应是一个值为 4 4k k+3+3 的的质数，其中质数，其中 k k 是一个整数。是一个整数。如如 3, 7, 11, 19, 23, 31, 3, 7, 11, 19, 23, 31, 43, 59, 127, 251, 503, 43, 59, 127, 251, 503, 。 处理冲突的闭散列方法数据结构教程第6章集合与字典n n探查序列如探查序
47、列如 HH0 0, , HH0 0+1, +1, HH0 0- - - -1, 1, HH0 0+4, +4, HH0 0- - - -4, 4, 。n n在在做做 ( (H H0 0 - - i i2 2 ) ) % % m m 的的运运算算时时, , 当当 H H0 0 - - i i2 2 0 0 时时, , 运运算算结结果果也是负数。实际算式可改为也是负数。实际算式可改为 j = (H0 - i2 ) % m, if ( j 0 ) j += mn n示例：给出一组关键码示例：给出一组关键码 37,25,14,36,49,68,57,11 37,25,14,36,49,68,57,11
48、。 散列函数为：散列函数为：HashHash ( (x x) )x%19x%19n 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) = 115757 25 11 49
49、 68 14 36 37 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18数据结构教程第6章集合与字典n n使用二次探查法处理冲突时的搜索成功的平均搜索长度为：n n搜索不成功的平均搜索长度为： 设散列表桶数为 m, 待查关键码为 x, 第一次通过散列函数计算出的桶号为 H0=hash(x)。当发生冲突时，第 i- -1 次和第 i 次计算出来的“下 一个”桶号分别为：数据结构教程第6章集合与字典相减，可以得到：从而数据结构教程第6章集合与字典n n只只要要知知道道上上一一次次的的桶桶号号 和和 , ,当当 i i 增增加加 1 1 时时可可以以从从
50、 和和 简简单单地地导导出出 和和 ，不不需需要要每每次次计计算算 i i 的的平平方方。n n在在冲冲突突处处理理算算法法 FindFind 中中, ,首首先先求求出出 HH0 0 作作为为当当前前桶桶号号CurrentPosCurrentPos, , 当发生冲突时求当发生冲突时求“ “下一个下一个” ”桶号，桶号，i i = 1 = 1。n n此时用一个标志此时用一个标志 odd odd 控制是加控制是加 i i2 2 还是减还是减 i i2 2 。n n若若 odd =odd = 0 0 加加 i i 2 2，并置，并置 oddodd = 1 = 1；n n若若 odd =odd = 1
51、 1 减减 i i 2 2，并置，并置 oddodd = 0 = 0。n n下次下次 i i 进一后，又可由进一后，又可由 odd odd 控制先加后减。控制先加后减。n n可可以以证证明明, , 当当表表的的长长度度TableSizeTableSize为为质质数数且且表表的的装装填填因因子子 不不超超过过 0.50.5 时时, , 新新的的表表项项 e e 一一定定能能够够插插入入, , 且且任任何何一一个个位位置置不不会会被被探探查查两两次次。因因此此，只只要要表表中中至至少少有有一一半半空，就不会有表满问题。空，就不会有表满问题。n n删除也只能进行逻辑删除。删除也只能进行逻辑删除。数据
52、结构教程第6章集合与字典双散列法双散列法n n使使用用双双散散列列方方法法时时, , 需需要要两两个个散散列列函函数数。第第一一个个散散列列函函数数 HashHash( ( ) ) 按按元元素素的的关关键键码码 key key 计计算算元元素素所所在在的的桶桶号号 HH0 0 = = HashHash( (keykey) )。一一旦旦发发生生冲冲突突，利利用用第第二二个个散散列列函函数数ReHashReHash( ( ) )计计算算“ “下下一一个个” ”桶桶的的移移位位量量。它它的的取取值值应应当当是是小小于于地地址址空间大小空间大小TableSizeTableSize，且与，且与Table
53、SizeTableSize互质的正整数。互质的正整数。n n寻找寻找“ “下一个下一个” ”桶的公式为：桶的公式为： j j = = HH0 0 = = HashHash( (keykey) ) p p = = ReHashReHash( (keykey) ) j j = ( = ( j j + + p p ) % ) % mm或或 HHi i = (= (HH0 0 + + i i * * ReHashReHash( (keykey) ) % ) ) % mm 处理冲突的闭散列方法数据结构教程第6章集合与字典n n示例：给出一组元素关键码示例：给出一组元素关键码 22, 41, 53, 46
54、, 30, 13, 01, 67 22, 41, 53, 46, 30, 13, 01, 67 。散列函数为：。散列函数为： HashHash( (x x) )(3(3x x) % 11) % 11。n n散列表为散列表为 HTHT1111，mm = 11 = 11。因此，再散列函数为。因此，再散列函数为 ReHashReHash( (x x) = (7) = (7x x) % 10 +1) % 10 +1。 HH0 0(22) = 0 (22) = 0 HH0 0(41) = 2(41) = 2 H H0 0(53) = 5 (53) = 5 HH0 0(46) = 6 (46) = 6 H
55、 H0 0(30) = 2 (30) = 2 冲突冲突 HH1 1 = (2+1) = 3 = (2+1) = 3 HH0 0(13) = 6 (13) = 6 冲突冲突 HH1 1 = (6+2) = 8 = (6+2) = 8 H H0 0(01) = 3 (01) = 3 冲突冲突 HH1 1 = (3+8) = 0 = (3+8) = 0 冲突冲突 HH2 2 =(0+8) = 8 =(0+8) = 8 冲突冲突 HH3 3 = (8+8) = 5 = (8+8) = 5 冲突冲突 HH4 4 = (5+8) = 2 = (5+8) = 2 冲突冲突 HH5 5 = (2+8) = 1
56、0 = (2+8) = 10 H H0 0(67) = 3 (67) = 3 冲突冲突 HH1 1 = (3+10) = 2 = (3+10) = 2 冲突冲突 HH2 2 = (2+10) = 1 = (2+10) = 1 22 67 41 30 53 46 13 01 0 1 2 3 4 5 6 7 8 9 10数据结构教程第6章集合与字典n n搜索成功的平均搜索长度搜索成功的平均搜索长度n n搜索不成功的平均搜索长度搜索不成功的平均搜索长度n n每一散列位置的移位量有每一散列位置的移位量有1010种：种：1, 2, 1, 2, , 10, 10。先。先计算每一散列位置各种移位量情形下找到
57、下一个计算每一散列位置各种移位量情形下找到下一个空位的比较次数空位的比较次数, , 求出平均值；求出平均值；n n再计算各个位置的平均比较次数的总平均值。再计算各个位置的平均比较次数的总平均值。n nRehashRehash( )( )的取法很多。例如的取法很多。例如, , 当当mm是质数时是质数时, , 可定义可定义uu ReHashReHash( (keykey) = ) = key key % (% (mm- - - -2) +12) +1uu ReHash ReHash( (keykey) = ) = keykey / / mm % ( % (mm- - - -2)+12)+1n n当
58、当 m m 是是 2 2 的方幂时，的方幂时，ReHashReHash( (keykey) ) 可取从可取从 0 0 到到 mm- - - -1 1 中的任意一个奇数。中的任意一个奇数。数据结构教程第6章集合与字典处理冲突的开散列方法 链地址法n n开开散散列列方方法法首首先先对对关关键键码码集集合合用用某某一一个个散散列列函函数数计算它们的存放位置计算它们的存放位置。n n若若设设散散列列表表地地址址空空间间的的所所有有位位置置是是从从 0 0 到到 mm-1, -1, 则则关关键键码码集集合合中中的的所所有有关关键键码码被被划划分分为为mm个个子子集集, , 具具有有相相同同地地址址的的关
59、关键键码码归归于于同同一一子子集集。我我们们称称同同一一子子集集中中的的关关键键码码互互为为同同义义词词。每每一一个个子子集集称称为为一一个桶。个桶。n n通通常常各各个个桶桶中中的的元元素素通通过过一一个个单单链链表表链链接接起起来来，称称之之为为同同义义词词子子表表。所所有有桶桶号号相相同同的的元元素素都都链链接接在在同同一一个个同同义义词词子子表表中中，各各链链表表的的表表头头结结点点组组成成一个向量。一个向量。n n向量的元素个数与桶数一致。桶号为向量的元素个数与桶数一致。桶号为 i i 的同义词子的同义词子表的表头结点是向量中的第表的表头结点是向量中的第 i i 个元素。个元素。数据
60、结构教程第6章集合与字典n n示例：给出一组表项关键码示例：给出一组表项关键码 37,25,14,36,49,68,57,1137,25,14,36,49,68,57,11。散列函数为：散列函数为：HashHash ( (x x) )x%11x%11，m=12m=12 。n n用它计算可得：用它计算可得： Hash Hash (37) = 4 (37) = 4 HashHash (25) = 3 (25) = 3 Hash Hash (14) = 3 (14) = 3 HashHash (36) = 3 (36) = 3 HashHash (49) = 5 (49) = 5 HashHash
61、(68) = 2 (68) = 2 Hash Hash (57) = 2 (57) = 2 HashHash (11) = 0 (11) = 011 68 2537 49 0 01 12 23 34 45 56 6111157 1436 数据结构教程第6章集合与字典 n n通通常常，每每个个桶桶中中的的同同义义词词子子表表都都很很短短，设设有有n n 个个关关键键码码通通过过某某一一个个散散列列函函数数，存存放放到到散散列列表表中中的的 m m 个个桶桶中中。那那么么每每一一个个桶桶中中的的同同义义词词子子表表的的平平均均长长度度为为 n n / / mm。以以搜搜索索平平均均长长度度为为 n
62、 n / / m m 的的同同义义词词子子表表代代替替了搜索长度为了搜索长度为 n n 的顺序表，搜索速度快得多。的顺序表，搜索速度快得多。n n应应用用开开散散列列法法处处理理冲冲突突, , 需需要要增增设设链链接接指指针针, , 似似乎乎增增加加了了存存储储开开销销。事事实实上上, , 由由于于闭闭散散列列 法法必必须须保保持持大大量量的的空空闲闲空空间间以以确确保保搜搜索索效效率率，如如二二次次探探查查法法要要求求装装填填因因子子 0.50.5，而而表表项项所所占占空空间间又又比比指指针针大大得得多多，所以使用开散列法反而比闭散列法节省存储空间所以使用开散列法反而比闭散列法节省存储空间。
63、数据结构教程第6章集合与字典散列表分析n n散散列列表表是是一一种种直直接接计计算算记记录录存存放放地地址址的的方方法法，它它在在关关键码与存储位置之间直接建立了映象。键码与存储位置之间直接建立了映象。n n当选择的散列函数能够得到均匀的地址分布时当选择的散列函数能够得到均匀的地址分布时, , 在搜在搜索过程中可以不做多次探查。索过程中可以不做多次探查。n n由于很难避免冲突由于很难避免冲突, , 增加了搜索时间。冲突的出现增加了搜索时间。冲突的出现, , 与散列函数的选取与散列函数的选取 ( (地址分布是否均匀地址分布是否均匀), ), 处理冲突的处理冲突的方法方法 ( (是否产生堆积是否产
64、生堆积) ) 有关。有关。n n在实际应用中使用关键码进行散列时在实际应用中使用关键码进行散列时, , 如在用作关键如在用作关键码的许多标识符具有相同的前缀或后缀，或者是相同码的许多标识符具有相同的前缀或后缀，或者是相同字符的不同排列的场合，不同的散列函数往往导致散字符的不同排列的场合，不同的散列函数往往导致散列表具有不同的搜索性能。列表具有不同的搜索性能。n n下图给出一些实验结果。下图给出一些实验结果。数据结构教程第6章集合与字典搜索关键码时所需对桶的平均访问次数 从图中可以看出，开散列法优于闭散列法；在散列函数中，用除留余数法作散列函数优于其它类型的散列函数，最差的是折叠法。数据结构教程
65、第6章集合与字典n n当装填因子 较高时, 选择的散列函数不同, 散列表的搜索性能差别很大。在一般情况下多选用除留余数法, 其中的除数在实用上应选择不含有20以下的质因数的质数。n n对散列表技术进行的实验评估表明, 它具有很好的平均性能, 优于一些传统的技术, 如平衡树。但散列表在最坏情况下性能很不好。如果对一 个有 n 个关键码的散列表执行一次搜索或插入操作，最坏情况下需要 O(n) 的时间。n nKnuth对不同的冲突处理方法进行了概率分析。数据结构教程第6章集合与字典n n若设 是散列表的装填因子：n n用地址分布均匀的散列函数Hash( )计算桶号。 n nSn 是搜索一个随机选择的
66、关键码 xi (1 i n) 所需的关键码比较次数的期望值n nUn 是在长度为 m 的散列表中 n 个桶已装入表项的情况下，装入第 n+1 项所需执行的关键码比较次数期望值。n n前者称为在 = n / m 时的搜索成功的平均搜索长度，后者称为在 = n / m时的搜索不成功的平均搜索长度。数据结构教程第6章集合与字典n n用不同的方法溢出处理冲突时散列表的平均搜索长度如图所示。数据结构教程第6章集合与字典n n散列表的装填因子 表明了表中的装满程度。越大, 说明表越满, 再插入新元素时发生冲突的可能性就越大。n n散列表的搜索性能, 即平均搜索长度依赖于散列表的装填因子, 不直接依赖于 n 或 m。n n不论表的长度有多大, 我们总能选择一个合适的装填因子, 以把平均搜索长度限制在一定范围内。数据结构教程第6章集合与字典
