数据结构数据结构20132013年秋季年秋季年秋季年秋季第六章第六章 集合与字典集合与字典本章教学内容本章教学内容v集合集合集合集合v字典字典字典字典v搜索（搜索（搜索（搜索（SearchSearch）概述）概述）概述）概述v散列方法散列方法散列方法散列方法散列函数构造方法散列函数构造方法散列函数构造方法散列函数构造方法冲突解决方法冲突解决方法冲突解决方法冲突解决方法v散列应用散列应用散列应用散列应用集合及其表示集合及其表示v集合是成员集合是成员( (元素元素) )的一个群集。集合中的成员可以的一个群集。集合中的成员可以是原子是原子( (单元素单元素) )，也可以是集合。，也可以是集合。v集合的成员必须互不相同。集合的成员必须互不相同。v在算法与数据结构中所遇到的集合，其单元素通常在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。成员具有相同的数据类型。v例：例：colour = red, orange, yellow, green, black, blue, purple, white 集合基本概念集合基本概念v集合中的成员一般是无序的，但在表示它时，常写集合中的成员一般是无序的，但在表示它时，常写在一个序列里。在一个序列里。v常设定集合中的单元素具有线性有序关系，此关系常设定集合中的单元素具有线性有序关系，此关系可记作可记作“”，表示，表示“优先于优先于”。v整数、字符和串都有一个自然线性顺序。指针也可整数、字符和串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。依据其在序列中安排的位置给予一个线性顺序。v在某些集合中保存实际数据值，某些集合中保存标在某些集合中保存实际数据值，某些集合中保存标示元素是否在集合中的指示信息。如学校开设的所示元素是否在集合中的指示信息。如学校开设的所有课程的编码属于前者，一个学期开设的课程构成有课程的编码属于前者，一个学期开设的课程构成的集合属于后者。的集合属于后者。template class Set public: virtual Set() = 0; /构造函数 virtual makeEmpty() = 0; /置空集合 virtual bool addMember (const T x) = 0; virtual bool delMember (const T x) = 0; virtual Set intersectWith (Set& R) = 0;/集合的交运算 virtual Set unionWith (Set& R) = 0; /集合的并运算 virtual Set differenceFrom (Set& R) = 0; /集合的差运算 virtual bool Contains (T x) = 0; virtual bool subSet (Set& R) = 0; virtual bool operator = (Set& R) = 0; /判集合是否相等;集合（集合（Set）的抽象数据类型）的抽象数据类型用位向量实现集合抽象数据类型用位向量实现集合抽象数据类型v当集合是全集合当集合是全集合 0, 1, 2, , n 的一个子集，且的一个子集，且 n 是是不大的整数时，可用位不大的整数时，可用位(0, 1)向量来实现集合。向量来实现集合。v当全集合是由有限个可枚举的成员组成时，可建立全当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数集合成员与整数 0, 1, 2, 的一一对应关系，用位向量的一一对应关系，用位向量来表示该集合的子集。来表示该集合的子集。v一个二进位两个取值一个二进位两个取值1或或0，分别表示在集合与不在集，分别表示在集合与不在集合。如果采用合。如果采用16位无符号短整数数组位无符号短整数数组bitVector 作为作为集合的存储，就要考虑如何求出元素集合的存储，就要考虑如何求出元素 i 在在bitVector数数组中的相应位置。组中的相应位置。集合的位向量集合的位向量(bit Vector)类的定义类的定义#include #include const int DefaultSize = 50;class bitSet /用位向量来存储集合元素, 集合元素的范围在0到/setSize-1之间。数组采用16位无符号短整数实现public: bitSet (int sz = DefaultSize);/构造函数 bitSet (const bitSet& R);/复制构造函数 bitSet () delete bitVector; /析构函数 int getMember (const T x);/取集合元素x void putMember (const T x, int v); /改集合元素x void makeEmpty () /置空集合 for (int i = 0; i vectorSize; i+) bitVectori = 0; bool addMember (const T x);/加入新成员x bool delMember (const T x);/删除老成员x bitSet& operator = (const bitSet& R); bitSet operator + (const bitSet& R); bitSet operator * (const bitSet& R); bitSet operator - (const bitSet& R); bool Contains (const T x); /判x是否集合this的成员 bool subSet (bitSet& R); /判this是否R的子集 bool operator = (bitSet& R); /判集合this与R相等 friend istream& operator (istream& in, bitSet& R); /输入 friend ostream& operator (ostream& out, bitSet& R); /输出private: int setSize;/集合大小 int vecterSize;/位数组大小 unsigned short *bitVector; /存储集合元素的位数组;使用示例使用示例Set 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 s3 = s1+s2; /求s1与s2的并 0, 1, , 16 s4 = s1*s2; /求s1与s2的交 7, 8, 9 s5 = s1-s2; /求s1与s2的差 0, 1, , 6/s1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 index = s1.SubSet (s4); /判断s1是否为s4子集 cout index endl; /结果，index = 0 /s1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 /s4: 7, 8, 9 equal = s1 = s2; /集合s1与s2比较相等 cout equal endl; /为0, 两集合不等构造函数的实现构造函数的实现template bitSet:bitSet (int sz) : setSize (sz) /构造函数 assert (setSize 0); /检查参数的合理性 vectorSize = (setSize+15) 4;/存储数组大小 bitVector = new int vectorSize; /分配空间 assert (bitVector != NULL);/检查存储分配是否成功 for (int i = 0; i vectorSize; i+) bitVectori = 0;/初始化;template bitSet:bitSet (const bitSet& R) /复制构造函数 setSize = R.setSize; /集合元素个数 vectorSize = R.vectorSize; /存储数组大小 bitVector = new int vectorSize; /分配空间 assert (bitVector != NULL); /检查存储分配是否成功 for (int i = 0; i vectorSize; i+) /初始化 bitVectori = R.bitVectori;映射函数的实现映射函数的实现template int bitSet:getMember (const T x) /读取集合元素x int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 return int (elem (16-id) % 1);/取第id位的值;template void bitSet:putMember (const T x, int v) /将值v送入集合元素x int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 int temp = elem (16-id); /右移,该位移至末尾 if (temp%2 = 0 & v = 1) elem = elem+1; /根据v的值,修改该位 else if (temp%2 = 1 & v = 0) elem = elem-1; bitVectorad = elem (16-id);/送回;template bool bitSet:addMember (const T x) assert (x = 0 & x setSize); if (getMember(x) = 0) putMember(x, 1); return true; return false; template bool bitSet:delMember (const T x) assert (x = 0 & x setSize); if (getMember(x) = 1) putMember(x, 0); return true; return false;templatebitSet bitSet: /求集合this与R的并operator + (const bitSet& R) assert (vectorSize = R.vectorSize); set temp (vectorSize); for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori | R.bitVectori; return temp; /按位求或, 由第三个集合返回;template bitSet bitSet: /求集合this与R的交operator * (const bitSet& R) assert (vectorSize = R.vectorSize); set temp (vectorSize); for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori & R.bitVectori; return temp; /按位求“与”, 由第三个集合返回;template bitSet bitSet:/求集合this与R的差operator - (const bitSet& R) assert (vectorSize = R.vectorSize); set temp (vectorSize); for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori & !R.bitVectori; return temp;/由第三个集合返回;thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 1 1 0 1 0 1 1 1 0thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 1 0 0 0 0 0 0 1 0thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 0 1 0 0 0 0 1 0 0集合的并集合的并集合的交集合的交集合的差集合的差template bool bitSet:subSet (bitSet& R) /判this是否R的子集 assert (setSize = R.setSize); for (int i = 0; i vectorSize; i+) /按位判断 if (bitVectori & !R.bitVectori) return false;return true;thisR0 0 1 1 1 0 1 0 1 1 00 0 1 1 1 0 0 1 0 1 01 1 0 0 0 1 1 0 1 0 1 thisR0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 0itemplate bool bitSet:operator = (bitSet& R) /判集合this与R相等 if (vectorSize != R.vectorSize) return false; for (int i = 0; i vectorSize; i+) if (bitVectori != R.bitVectori) return false; return true;/对应位全部相等;用带表头结点的有序链表表示集合用带表头结点的有序链表表示集合firstfirst081723354972用有序链表实现集合抽象数据类型用有序链表实现集合抽象数据类型v用有序链表来表示集合时，链表中的每个结点表示用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。集合的一个成员。v各结点所表示的成员各结点所表示的成员 e0, e1, , en 在链表中按升序排在链表中按升序排列，即列，即 e0 e1 en。v集合成员可以无限增加。因此，用有序链表可以表集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。示无穷全集合的子集。集合的有序链表类的定义集合的有序链表类的定义template struct SetNode /集合的结点类定义 T data;/每个成员的数据 SetNode *link;/链接指针 SetNode() : link (NULL);/构造函数 SetNode (const T& x, SetNode *next = NULL) : data (x), link (next);/构造函数;template class LinkedSet /集合的类定义private: SetNode *first, *last; /有序链表表头指针, 表尾指针public: LinkedSet () first = last = new SetNode; LinkedSet (LinkedSet& R); /复制构造函数 LinkedSet () makeEmpty(); delete first; void makeEmpty();/置空集合 bool addMember (const T& x); bool delMember (const T& x); LinkedSet& operator = (LinkedSet& R); LinkedSet operator + (LinkedSet& R); LinkedSet operator * (LinkedSet& R); LinkedSet operator - (LinkedSet& R); bool Contains (const T x);/判x是否集合的成员 bool operator = (LinkedSet& R);/判集合this与R相等 bool Min (T& x); /返回集合最小元素的值 bool Max (T& x); /返回集合最大元素的值 bool subSet (bitSet& R); /判this是否R的子集;集合的加入和删除操作集合的加入和删除操作template bool LinkedSet:addMember (const T& x) /把新元素x加入到集合之中 SetNode *p = first-link, *pre = first; while (p != NULL & p-data link; if (p != NULL & p-data = x) return false; /集合中已有此元素, 不加入 SetNode *s = new SetNode(x); /创建结点 s-link = p; pre-link = s; /链入 if (p = NULL) last = s;/链到链尾时改链尾指针 return true;template bool LinkedSet:delMember (const T& x) /把集合中成员x删去 SetNode *p = first-link, *pre = first; while (p != NULL & p-data link; if (p != NULL & p-data = x) /找到,可删 pre-link = p-link; /重新链接 if (p = last) last = pre;/删链尾时改尾指针 delete p; /删除含x结点 return true; else return false;/集合中无此元素;template LinkedSet LinkedSet:operator + (LinkedSet& R) /求集合this与集合R的并 SetNode *pb = R.first-link; /R扫描指针 SetNode *pa = first-link;/this扫描指针 LinkedSet temp;/创建空链表 SetNode *p, *pc = temp.first;/结果存放指针 while (pa != NULL & pb != NULL) if (pa-data = pb-data) /两集合共有 pc-link = new SetNode(pa-data); pa = pa-link; pb = pb-link; else if (pa-data data) /this元素值小 pc-link = new SetNode(pa-data); pa = pa-link;表示集合的几个重载函数表示集合的几个重载函数 else /R集合元素值小 pc-link = new SetNode(pb-data); pb = pb-link; pc = pc-link; if (pa != NULL) p = pa;/this集合未扫完 else p = pb;/或R集合未扫完 while (p != NULL) /向结果链逐个复制 pc-link = new SetNode(p-data); pc = pc-link; p = p-link; pc-link = NULL; temp.last = pc; /链表收尾 return temp;； firstR.first08172349temp.first231735papbpc0817233549bool LinkedSet:operator = (LinkedSet& R) SetNode *pb = R.first-link; SetNode *pa = first-link; while (pa != NULL & pb != NULL) if (pa-data = pb-data) pa = pa-link; pb = pb-link; else return false; /扫描途中不等时退出 if (pa != NULL | pb != NULL) return false; /链不等长时, 返回0 return true;字典（字典（Dictionary）v字典是一种特殊的集合，其元素是字典是一种特殊的集合，其元素是字典是一种特殊的集合，其元素是字典是一种特殊的集合，其元素是（关键字，属（关键字，属（关键字，属（关键字，属性值）二元组性值）二元组性值）二元组性值）二元组；v关键字必须是互不相同的（在一个字典之内）；关键字必须是互不相同的（在一个字典之内）；关键字必须是互不相同的（在一个字典之内）；关键字必须是互不相同的（在一个字典之内）；v字典的主要操作是依据关键字来存储和析取值，字典的主要操作是依据关键字来存储和析取值，字典的主要操作是依据关键字来存储和析取值，字典的主要操作是依据关键字来存储和析取值，可用于组织简单的数据库，提供存储、查找和删可用于组织简单的数据库，提供存储、查找和删可用于组织简单的数据库，提供存储、查找和删可用于组织简单的数据库，提供存储、查找和删除记录的功能；除记录的功能；除记录的功能；除记录的功能；v字典的实现方式很多，如有序线性表、跳表、字字典的实现方式很多，如有序线性表、跳表、字字典的实现方式很多，如有序线性表、跳表、字字典的实现方式很多，如有序线性表、跳表、字符树等；符树等；符树等；符树等；v用散列方法实现的字典具有非常高效的检索性能。用散列方法实现的字典具有非常高效的检索性能。用散列方法实现的字典具有非常高效的检索性能。用散列方法实现的字典具有非常高效的检索性能。vv 字典是一些元素的集合。每个元素有一个称作字典是一些元素的集合。每个元素有一个称作字典是一些元素的集合。每个元素有一个称作字典是一些元素的集合。每个元素有一个称作keykey（关键字）（关键字）（关键字）（关键字）的域，的域，的域，的域，不同元素的不同元素的不同元素的不同元素的keykey各不相同各不相同各不相同各不相同。学号学号学号学号姓名姓名姓名姓名性别性别性别性别年龄年龄年龄年龄成成成成 绩绩绩绩高数高数高数高数英语英语英语英语物理物理物理物理体育体育体育体育9801198011张张张张 娟娟娟娟女女女女202080808686818190909801298012赵立军赵立军赵立军赵立军男男男男19198282727289898686字典的抽象数据类型字典的抽象数据类型 const int DefaultSize = 26;template class Dictionary /对象: 一组对, 其中, 名字是唯一的public: Dictionary (int size = DefaultSize); /构造函数 bool Member (Name name);/判name是否在字典中 Attribute *Search (Name name); /在字典中搜索关键码与name匹配的表项 void Insert (Name name, Attribute attr); /若name在字典中, 则修改相应对 /的attr项; 否则插入到字典中 void Remove (Name name); /若name在字典中, 则在字典中删除相应的 /对;v用文件记录（用文件记录（record）或表格的表项（）或表格的表项（entry）来表示）来表示单个元素时，用：单个元素时，用：（关键码（关键码key，记录或表项位置指针，记录或表项位置指针adr）v构成搜索某一指定记录或表项的索引项。构成搜索某一指定记录或表项的索引项。字典的线性表描述字典的线性表描述 v字典可以保存在线性序列字典可以保存在线性序列 (e1,e2,) 中，其中中，其中ei 是字是字典中的元素，其典中的元素，其关键码从左到右依次增大关键码从左到右依次增大。为了适。为了适应这种描述方式，可以定义有序顺序表和有序链表。应这种描述方式，可以定义有序顺序表和有序链表。v用有序链表来表示字典时，链表中的每个结点表示用有序链表来表示字典时，链表中的每个结点表示字典中的一个元素，字典中的一个元素，各个结点按照结点中保存的数各个结点按照结点中保存的数据值非递减链接据值非递减链接，即，即e1e2 。因此，在一个有序。因此，在一个有序链表中寻找一个指定元素时，一般不用搜索整个链链表中寻找一个指定元素时，一般不用搜索整个链表。表。#include #include “SeqList.h”const int defaultSize = 50;template class SortedList : public SeqList public: int Search (K k1) const; /搜索 void Insert (const K k1, E& e1); /插入 bool Remove (const K k1, E& e1); /删除;有序顺序表的类定义有序顺序表的类定义基于有序顺序表的顺序搜索算法基于有序顺序表的顺序搜索算法template int SortedList:Search (K k1) const /顺序搜索关键码为x的数据对象 for (int i = 1; i k1) break; return 0; /顺序搜索失败, 返回失败信息;v算法中的算法中的“=”和和“”都是重载函数，在定义都是重载函数，在定义E时定时定义它们的实现。义它们的实现。有序顺序表顺序搜索的时间代价有序顺序表顺序搜索的时间代价v衡量一个搜索算法的时间效率的标准是：在搜索过衡量一个搜索算法的时间效率的标准是：在搜索过程中关键码平均比较次数，也称为平均搜索长度程中关键码平均比较次数，也称为平均搜索长度ASL (Average Search Length)，通常它是字典中元，通常它是字典中元素总数素总数 n 的函数。的函数。v设搜索第设搜索第 i 个元素的概率为个元素的概率为 pi, 搜索到第搜索到第 i 个元素所个元素所需比较次数为需比较次数为 ci, 则搜索成功的平均搜索长度则搜索成功的平均搜索长度:v在顺序搜索情形，搜索第在顺序搜索情形，搜索第 i (1in) 个元素需要比较个元素需要比较 i 次，假定按等概率搜索各元素：次，假定按等概率搜索各元素：v这与一般顺序表情形相同。但搜索不成功时不需一这与一般顺序表情形相同。但搜索不成功时不需一直比较到表尾，只要发现下一个元素的值比给定值直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。大，就可断定搜索不成功。v设一个有设一个有 n 个表项的表，查找失败的位置有个表项的表，查找失败的位置有n+1个，个，可以用判定树加以描述。可以用判定树加以描述。搜索成功时停在内结点，搜索成功时停在内结点，搜索失败时停在外结点。搜索失败时停在外结点。v例如，有序顺序表例如，有序顺序表 (10, 20, 30, 40, 50, 60)的顺序的顺序搜索的分析（使用判定树）搜索的分析（使用判定树）105060= = = = = = =203040v判定树是一种扩充二叉树。内结点代表顺序表中已判定树是一种扩充二叉树。内结点代表顺序表中已有的元素，外结点代表失败结点，它表示在两个相有的元素，外结点代表失败结点，它表示在两个相邻已有元素值之间的值。邻已有元素值之间的值。v假定表中所有失败位置的搜索概率相同，则搜索不假定表中所有失败位置的搜索概率相同，则搜索不成功的平均搜索长度：成功的平均搜索长度：v时间代价为时间代价为O(n)。为了加速搜索，在有序顺序表的。为了加速搜索，在有序顺序表的情形，可以采用情形，可以采用折半搜索折半搜索，它也称，它也称二分搜索二分搜索，时间，时间代价可减到代价可减到O(log2n)。基于有序顺序表的折半搜索基于有序顺序表的折半搜索v设设 n 个元素存放在一个有序顺序表中。个元素存放在一个有序顺序表中。v折折半半搜搜索索时时, 先先求求位位于于搜搜索索区区间间正正中中的的元元素素的的下下标标mid，用其关键码与给定值，用其关键码与给定值 x 比较比较:u datamid.key = x，搜索成功；，搜索成功；u datamid.key x，把把搜搜索索区区间间缩缩小小到到表表的的前半部分前半部分，继续折半搜索；，继续折半搜索；u datamid.key x，把把搜搜索索区区间间缩缩小小到到表表的的后半部分后半部分，继续折半搜索。，继续折半搜索。v如如果果搜搜索索区区间间已已缩缩小小到到一一个个对对象象，仍仍未未找找到到想想要要搜搜索的对象，则搜索失败。索的对象，则搜索失败。搜索成功的例子搜索成功的例子- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6搜索失败的例子搜索失败的例子- -1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high5templateint SortedList:BinarySearch (K k1, const int low, const int high ) const /折半搜索的递归算法，用到E的重载操作“” int mid = 0; /元素序号从1开始 if (low = high) mid = (low + high) / 2; if (datamid-1 k1) mid = BinarySearch (k1, low, mid -1); return mid;template int SortedList :BinarySearch (K k1) const /折半搜索的迭代算法，用到E的重载操作“” int high = n, low = 1, mid; /元素序号从1开始 while (low = high) mid = (low + high) / 2; if (datamid-1 k1) high = mid-1; /左缩搜索区间 else return mid; /搜索成功 return 0; /搜索失败v分析有序顺序表分析有序顺序表 ( 10, 20, 30, 40, 50, 60 ) 的折半搜索的折半搜索算法性能的判定树：算法性能的判定树： 1050= = = = = = =30204060ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 有序链表的类定义有序链表的类定义 #include template struct ChainNode /链表结点类定义 E data; ChainNode *link; ChainNode() : link (NULL) ; /构造函数 ChainNode (E& e1, /构造函数 ChainNode *next = NULL) : data (e1), link (next) ;template class SortedChain /有序链表类定义public: SortedChain () /构造函数 first = new ChainNode; assert (first != NULL); ; SortedChain ();/析构函数 ChainNode *Search (K k1); /搜索 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; /链表的头指针;搜索、插入与删除算法搜索、插入与删除算法template ChainNode *SortedChain:Search (const K k1) const ChainNode *p = first-link; while (p != NULL & p-data link; /重载：元素判小于 if ( p != NULL & p-data = k1) return p; /重载：元素判等于 else return NULL;template void SortedChain:Insert (const K k1, E& e1) ChainNode *p = first-link, *pre = first； ChainNode *newNode; while (p != NULL & p-data link; /寻找插入位置 if (p != NULL & p-data = k1) p-data = e1; else newNode = new ChainNode(e1); if (newNode = NULL) cerr “存储分配失败！” link = p; pre-link = newNode; ; template bool SortedChain:Remove (const K k1, E& e1) ChainNode *p = first-link, *pre = first； while (p != NULL & p-data link; /寻找删除位置 if (p != NULL & p-data = k1) /重载：元素关键码判等于 pre-link = p-link; e1 = p-data; delete p; return true; else return false; /未找到删除结点; 散列表（散列表（Hash Table）v理想的搜索方法是可以不经过比较，一次直接从字典理想的搜索方法是可以不经过比较，一次直接从字典中得到要搜索的元素。中得到要搜索的元素。v如果在元素存储位置与其关键码之间建立一个确定的如果在元素存储位置与其关键码之间建立一个确定的对应函数关系对应函数关系Hash()， 使得每个关键码与结构中一个使得每个关键码与结构中一个唯一的存储位置相对应：唯一的存储位置相对应： Address Hash(key)v在插入时依此函数计算存储位置并按此位置存放。在在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算，把求得的函搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，数值当做元素存储位置， 在结构中按此位置搜索。在结构中按此位置搜索。这就是散列方法。这就是散列方法。 v在散列方法中所用转换函数叫做散列函数。按此方在散列方法中所用转换函数叫做散列函数。按此方法构造出来的表叫做散列表。法构造出来的表叫做散列表。v使用散列方法进行搜索不必进行多次关键码的比较使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快搜索速度比较快, 可以直接到达或逼近具有此关键码可以直接到达或逼近具有此关键码的表项的实际存放地址。的表项的实际存放地址。v散列函数是一个压缩映象函数。关键码集合比散列散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这算，把不同的关键码映射到同一个散列地址上，这就产生了冲突。就产生了冲突。v示例：有一组表项，其关键码分别是示例：有一组表项，其关键码分别是 12361, 07251, 03309, 30976v采用的散列函数是采用的散列函数是 hash(x) = x % 73 + 13420则有则有 hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。v对不同的关键码，通过散列函数的计算，得到了同一散对不同的关键码，通过散列函数的计算，得到了同一散列地址。称这些产生冲突的散列地址相同的不同关键码列地址。称这些产生冲突的散列地址相同的不同关键码为同义词。为同义词。v由于关键码集合比地址集合大得多由于关键码集合比地址集合大得多, 冲突很难避免。所以冲突很难避免。所以对于散列方法对于散列方法, 需要讨论以下两个问题：需要讨论以下两个问题：1) 对于给定的对于给定的一个关键码集合，选择一个计算一个关键码集合，选择一个计算 简单且地址分布比较均简单且地址分布比较均匀的散列函数，避免或尽量减少冲突；匀的散列函数，避免或尽量减少冲突；2)拟订解决冲突拟订解决冲突的方案。的方案。 构造散列函数时的几点要求：构造散列函数时的几点要求：散列函数应是简单的，能在较短的时间内散列函数应是简单的，能在较短的时间内 计算出结果。计算出结果。散列函数的定义域必须包括需要存储的全散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有部关键码，如果散列表允许有 m 个地址时，个地址时，其值域必须在其值域必须在 0 到到 m-1 之间。之间。散列函数计算出来的地址应能均匀分布在散列函数计算出来的地址应能均匀分布在整个地址空间中整个地址空间中 : 若若 key 是从关键码集合是从关键码集合中随机抽取的一个关键码中随机抽取的一个关键码, 散列函数应能散列函数应能以同等概率取以同等概率取0 到到 m-1 中的每一个值。中的每一个值。散列函数散列函数此类函数取关键码的某个线性函数值作为散列地址：此类函数取关键码的某个线性函数值作为散列地址： Hash(key) = a*key+b a, b为常数为常数 这类散列函数是一对一的映射，一般不会产生冲突。但这类散列函数是一对一的映射，一般不会产生冲突。但它要求散列地址空间的大小与关键码集合的大小相同。它要求散列地址空间的大小与关键码集合的大小相同。示例：示例：有一组关键码如下：有一组关键码如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 。散列函数为散列函数为 Hash(key) = key-940000 Hash (942148) = 2148 Hash (941269) = 1269Hash (940527) = 527 Hash (941630) = 1630Hash (941805) = 1805 Hash (941558) = 1558Hash (942047) = 2047 Hash (940001) = 1可以按计算出的地址存放记录。可以按计算出的地址存放记录。直接定址法直接定址法数字分析法（自学）数字分析法（自学） 设有设有 n 个个 d 位数位数, 每一位可能有每一位可能有 r 种不同的符号。种不同的符号。这这 r 种不同符号在各位上出现的频率不一定相同。种不同符号在各位上出现的频率不一定相同。根据散列表的大小根据散列表的大小, 选取其中各种符号分布均匀的选取其中各种符号分布均匀的若干位作为散列地址若干位作为散列地址。v计算各位数字中符号分布均匀度计算各位数字中符号分布均匀度 k的公式：的公式：v其中，其中， 表示表示第第 i 个符号在第个符号在第 k 位上出现的次数位上出现的次数，n/r 表示各种符号在表示各种符号在 n 个数中均匀出现的期望值。个数中均匀出现的期望值。 v计算计算出的出的 k 值越小，表明在该位值越小，表明在该位 (第第 k 位位) 各种符各种符号分布得越号分布得越均匀。均匀。 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 v若散列表地址范围有若散列表地址范围有 3 位数字位数字, 取各关键码的取各关键码的 位做为记录的散列地址。位做为记录的散列地址。v数字分析法仅适用于事先明确知道表中所有关键码每数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。果换一个关键码集合，选择哪几位要重新决定。 设散列表中允许地址数为设散列表中允许地址数为m，取一个不大于，取一个不大于 m，但最接近于或，但最接近于或等于等于 m 的质数的质数 p 作为除数，用以下函数把关键码转换成散列地作为除数，用以下函数把关键码转换成散列地址：址： hash (key) = key % p p m其中，其中，“%”是整数除法取余的运算，要求这时的质数是整数除法取余的运算，要求这时的质数 p 不是接近不是接近 2 的幂。的幂。v示例示例: 有一个关键码有一个关键码 key = 962148，散列表大小，散列表大小 m = 25，即，即 HT25。取质数。取质数 p = 23。散列函数。散列函数 hash(key) = key % p。则散。则散列地址为列地址为 hash(962148) = 962148 % 23 = 12。v可按计算出的地址存放记录。注意可按计算出的地址存放记录。注意, 使用散列函数计算出的地使用散列函数计算出的地址范围是址范围是 0 到到 22，而，而 23、24 这几个地址实际上不能用散列函这几个地址实际上不能用散列函数计算出来，只能在处理冲突时达到这些地址。数计算出来，只能在处理冲突时达到这些地址。 除留余数法除留余数法首首先先计计算算构构成成关关键键码码的的标标识识符符的的内内码码的的平平方方, 然然后后按照散列表的大小取中间的若干位作为散列地址。按照散列表的大小取中间的若干位作为散列地址。v设设标标识识符符可可以以用用一一个个计计算算机机字字长长的的内内码码表表示示。因因为为内内码码平平方方数数的的中中间间几几位位一一般般是是由由标标识识符符所所有有字字符符决决定定, 所所以以对对不不同同的的标标识识符符计计算算出出的的散散列列地地址址大大多多不不相同。相同。v在在平平方方取取中中法法中中, 一一般般取取散散列列地地址址为为2的的某某次次幂幂。例例如如, 若若散散列列地地址址总总数数取取为为 m = 8r，则则对对内内码码的的平平方方数取中间的数取中间的 r 位位。平方取中法平方取中法 标识符标识符内码内码内码平方内码平方散列地址散列地址A0101001A1013420420042A9014423420342B0204004DMAX21526443617100443DMAX10415013034526447352352AMAX135423617100236AMAX10115013034345424652652标识符的八进制内码表示及其平方值和散列地址标识符的八进制内码表示及其平方值和散列地址把关键码自左到右分成位数相等的几部分把关键码自左到右分成位数相等的几部分, 每一部每一部分的位数应与散列表地址位数相同分的位数应与散列表地址位数相同, 只有最后一部只有最后一部分的位数可以短一些。分的位数可以短一些。把这些部分的数据叠加起来把这些部分的数据叠加起来, 就可以得到具有该关就可以得到具有该关键码的记录的散列地址。键码的记录的散列地址。v有两种叠加方法：有两种叠加方法：v 移位法：把各部分最后一位对齐相加；移位法：把各部分最后一位对齐相加；v 分界法：各部分不折断，沿各部分的分界分界法：各部分不折断，沿各部分的分界来回折叠来回折叠, 然后对齐相加。然后对齐相加。 折叠法折叠法v一一般般当当关关键键码码的的位位数数很很多多，而而且且关关键键码码每每一一位位上上数数字字的的分分布布大大致致比比较较均均匀匀时时，可可用用这这种种方方法法得得到到散散列列地址。地址。v假假设设地地址址空空间间为为HT400，利利用用以以上上函函数数计计算算，取取其其中中3位位，取取值值范范围围在在0999，可可能能超超出出地地址址空空间间范范围围，为为此此必必须须将将0999压压缩缩到到0399。可可将将计计算算出出的的地地址址乘乘以以一一个个压压缩缩因因子子0.4，把把计计算算出出的的地地址址压压缩到允许范围缩到允许范围。处理冲突的闭散列方法（开地址法）处理冲突的闭散列方法（开地址法）v因为任一种散列函数也不能避免产生冲突，因此选因为任一种散列函数也不能避免产生冲突，因此选择好的解决冲突的方法十分重要。择好的解决冲突的方法十分重要。v为了减少冲突，对散列表加以改造。若设散列表为了减少冲突，对散列表加以改造。若设散列表HT有有 m 个地址个地址, 将其改为将其改为 m 个桶。其桶号与散列地址个桶。其桶号与散列地址一一对应一一对应, 第第 i (0i m) 个桶的桶号即为第个桶的桶号即为第 i 个散列个散列地址地址。v每个桶可存放每个桶可存放 s 个表项个表项, 这些表项的关键码互为同这些表项的关键码互为同义词。如果对两个不同表项的关键码用散列函数计义词。如果对两个不同表项的关键码用散列函数计算得到同一个散列地址，就产生了冲突，它们可放算得到同一个散列地址，就产生了冲突，它们可放在同一个桶内。在同一个桶内。v只有当桶内所有只有当桶内所有 s 个表项位置都放满表项后再加入表个表项位置都放满表项后再加入表项才会产生溢出。项才会产生溢出。v通常桶的大小通常桶的大小 s 取的比较小，因此在桶内大多采用顺取的比较小，因此在桶内大多采用顺序搜索。序搜索。v闭散列也叫做开地址法。在闭散列情形，所有的桶都闭散列也叫做开地址法。在闭散列情形，所有的桶都直接放在散列表数组中。因此每个桶只有一个表项直接放在散列表数组中。因此每个桶只有一个表项 ( s = 1 )。v若设散列表中各桶的编址为若设散列表中各桶的编址为 0 到到 m-1, 当要加入一个当要加入一个表项表项 R2 时时, 用它的关键码用它的关键码 R2.key, 通过散列函数通过散列函数 hash (R2.key) 的计算，得到它的存放桶号的计算，得到它的存放桶号 j。v但在存放时发现此桶已被另一个表项但在存放时发现此桶已被另一个表项 R1 占据，发生占据，发生了冲突了冲突, 必须处理冲突。为此必须处理冲突。为此, 需把需把 R2 存放到表中存放到表中“下一个下一个”空桶中。如果表未被装满空桶中。如果表未被装满, 则在允许的范围则在允许的范围内必定还有空桶。内必定还有空桶。 假设给出一组表项，它们的关键码为假设给出一组表项，它们的关键码为 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly。采用的散。采用的散列函数是：取其第一个字母在字母表中的位置。列函数是：取其第一个字母在字母表中的位置。 HashHash ( (x x) = ) = ord ord ( (x x) )- -ord ord ( (A A) ) / /ordord() () 求内码函数求内码函数求内码函数求内码函数可得可得 Hash (Burke) = 1 Hash (Ekers) = 4 Hash (Broad) = 1 Hash (Blum) = 1 Hash (Attlee) = 0 Hash (Hecht) = 7 Hash (Alton) = 0 Hash (Ederly) = 4线性探查法线性探查法 (Linear Probing) v设散列表设散列表 HT26, m = 26。采用线性探查法处理冲突。采用线性探查法处理冲突, 则散列结果如图所示。则散列结果如图所示。0 1 2 3 4Attlee Burke Broad Blum Ekers(1) (1) (2) (3) (1)(1) (1) (2) (3) (1)Alton Ederly Hecht 5 6 7 8 9 (6) (3) (1)(6) (3) (1)v需要搜索或加入一个表项时，首先使用散列函数需要搜索或加入一个表项时，首先使用散列函数计算桶号作为初始地址：计算桶号作为初始地址： H0 = hash (key)v一旦发生冲突，在表中顺次向后寻找一旦发生冲突，在表中顺次向后寻找“下一下一 个个”空桶空桶 Hi 的递推公式为：的递推公式为： Hi = (Hi-1+1) % m， i =1, 2, , m-1 即用以下的线性探查序列在表中寻找即用以下的线性探查序列在表中寻找“下一下一 个个”空桶的桶号：空桶的桶号： H0+1, H0 +2, , m-1, 0, 1, 2, , H0-1亦可写成如下的通项公式：亦可写成如下的通项公式： Hi = (H0 + i) % m， i =1, 2, , m-1v当发生冲突时探查下一个桶。当循环当发生冲突时探查下一个桶。当循环 m-1次后就会回次后就会回到开始探查时的位置，说明待查关键码不在表内且表到开始探查时的位置，说明待查关键码不在表内且表已满，不能再插入新关键码。已满，不能再插入新关键码。v用平均搜索长度用平均搜索长度ASL (Averagy Search Length) 衡量散衡量散列方法的搜索性能。包括搜索成功的平均搜索长度列方法的搜索性能。包括搜索成功的平均搜索长度ASLsucc和搜索不成功的平均搜索长度和搜索不成功的平均搜索长度ASLunsucc。v搜索成功的平均搜索长度搜索成功的平均搜索长度 ASLsucc 是指找到表中已有表是指找到表中已有表项的平均探查次数，是找到表中各个已有表项的探查项的平均探查次数，是找到表中各个已有表项的探查次数的平均值。次数的平均值。v搜索不成功的平均搜索不成功的平均搜索长度搜索长度 ASLunsucc 是指在表中搜索是指在表中搜索不到待查表项，但找到插入位置的平均探查次数。它不到待查表项，但找到插入位置的平均探查次数。它是表中所有可能散列到的位置上要插入新元素时为找是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。到空桶的探查次数的平均值。v在使用线性探查法对示例进行搜索时，搜索成功的平在使用线性探查法对示例进行搜索时，搜索成功的平均搜索长度为：均搜索长度为：v搜索不成功的平均搜索长度为搜索不成功的平均搜索长度为：用线性探查法组织的散列表的类定义用线性探查法组织的散列表的类定义 const int DefaultSize = 100;enum KindOfStatus Active, Empty, Deleted; /元素分类 (活动/空/删)template class HashTable /散列表类定义public: HashTable (const int d, int sz = DefaultSize); /构造函数 HashTable() delete ht; delete info; /析构函数 HashTable& operator = (const HashTable& ht2); /表赋值 bool Search (K k1, E& e1) const; /搜索k1 bool Insert (const E& e1); /插入e1 bool Remove (const E& e1); /删除e1 void makeEmpty (); /置表空private: int divitor;/散列函数的除数 int n, TableSize;/当前桶数及最大桶数 E *ht;/散列表存储数组 KindOfStatus *info;/状态数组 int FindPos (K k1) const; /散列函数 int operator = (E& e1) return *this = e1; /重载函数：元素判等 int operator != (E& e1) return *this != e1; /重载函数：元素判不等; template/构造函数HashTable:HashTable (int d, int sz) divitor = d;/除数 TableSize = sz; n = 0;/表长 ht = new ETableSize;/表存储空间 info = new KindOfstatusTableSize; for (int i = 0; i TableSize; i+) infoi = empty;bool HashTable:Search (K k1, E& e1) /使用线性探查法在散列表ht(每个桶容纳一个元素)中搜索k1 int i = FindPos (k1)； /搜索 if (infoi != Active | hti != k1) return false; e1 = hti; return true; ;template int HashTable:FindPos (K k1) const /搜索在一个散列表中关键码与k1匹配的元素，/搜索成功，则函数返回该元素的位置，否则返回/插入点（如果有足够的空间） int i = k1 % divitor; /计算初始桶号 int j = i; /j是检测下一空桶下标 do if (infoj = Empty | infoj = Active & htj = k1) return j; /找到初始桶号 j = (j+1) % TableSize;/找下一个空桶 while (j != i); return j; /转一圈回到开始点, 表已满, 失败;使用线性探查法的搜索算法使用线性探查法的搜索算法 v在在闭散列情形下不能真正删除表中已有表项。删闭散列情形下不能真正删除表中已有表项。删除表项会影响其他表项的搜索。除表项会影响其他表项的搜索。v例如，若把关键码为例如，若把关键码为 Broad 的表项真正删除，把的表项真正删除，把它所在位置的它所在位置的info域置为域置为Empty，以后在搜索关键，以后在搜索关键码为码为 Blum 和和 Alton 的表项时就查不下去，会错的表项时就查不下去，会错误地判断表中没有关键码为误地判断表中没有关键码为Blum 和和 Alton 的表项。的表项。v若想删除一个表项若想删除一个表项, 只能给它做一个删除标记只能给它做一个删除标记deleted进行逻辑删除进行逻辑删除, 不能把它真正删去。不能把它真正删去。v逻辑删除的副作用是：在执行多次删除后逻辑删除的副作用是：在执行多次删除后, 表面上表面上看起来散列表很满看起来散列表很满, 实际上有许多位置没有利用。实际上有许多位置没有利用。template bool HashTable:Insert (K k1, const E& e1) /在ht表中搜索k1。若找到则不再插入, 若未找到, /但找到位置的标志是Empty或Deleted, x插入 int i = FindPos (k1); /用散列函数计算桶号 if (infoi != Active) /该桶空,存放新元素 hti = e1; infoi = Active; n+; return true; if (infoi = Active & hti = e1) cout “表中已有此元素，不能插入！表中已有此元素，不能插入！n”; else cout “表已满，不能插入！表已满，不能插入！n”; return false;使用线性探查法的其他操作使用线性探查法的其他操作 template bool HashTable:Remove (K k1, E& e1) /在ht表中删除元素key, 并在引用参数e1中得到它 int i = FindPos (k1); if (infoi = Active) /找到要删元素, 且是活动元素 infoi = Deleted; n-; /做逻辑删除标志, 并不真正物理删除 return true; else return false;v线性探查方法容易产生线性探查方法容易产生“堆积堆积”, 不同探查序列的关不同探查序列的关键码占据可用的空桶键码占据可用的空桶, 为寻找某一关键码需要经历不为寻找某一关键码需要经历不同的探查序列同的探查序列, 导致搜索时间增加。导致搜索时间增加。v二次探查法首先通过某一个散列函数对表项的关键码二次探查法首先通过某一个散列函数对表项的关键码 key 进行计算，得到桶号，它是一个非负整数。进行计算，得到桶号，它是一个非负整数。 H0 = hash(key)v然后使用二次探查法在表中寻找然后使用二次探查法在表中寻找“下一个下一个”空桶，其公式空桶，其公式为：为：Hi = (H0+i2) % m, Hi = (H0-i2)% m, i = 1, 2, 3, , (m-1)/2vm 是表的大小，它应是一个值为是表的大小，它应是一个值为 4k+3 的质数，其中的质数，其中 k 是一是一个整数。这样的质数如个整数。这样的质数如3, 7, 11, 19, 23, 31, 43, 59, 127, 251, 503, 。v二次探查法的探查序列形如二次探查法的探查序列形如 H0, H0+1, H0-1, H0+4, H0-4, 。在做。在做 (H0-i2) % m 的运算时，当的运算时，当H0-i20时，运算结果也时，运算结果也是负数。算式可改为是负数。算式可改为if ( j = (H0-i2)% m)0 j += m。二次探查法二次探查法 (quadratic probing)v示示例例：给给出出一一组组关关键键码码 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly 。 散列函数为：散列函数为：Hash (x)ord (x)ord (A)v用它计算可得用它计算可得 Hash (Burke) = 1 Hash (Ekers) = 4 Hash (Broad) = 1 Hash (Blum) = 1 Hash (Attlee) = 0 Hash (Hecht) = 7 Hash (Alton) = 0 Hash (Ederly) = 4v因因为为可可能能桶桶号号是是025, 取取满满足足4k+3的的质质数数，表表的的长长度度为为TableSize = 31。v利用二次探查法得到的散列结果如图所示。利用二次探查法得到的散列结果如图所示。0 1 2 3 4 5 Blum Burke Broad Ekers Ederly Hecht 6 7 8 9 10 11 Alton Attlee (3) (1) (2) (1) (2)(1)25 26 27 28 29 30 (5) (3)利用二次探查法处理溢出利用二次探查法处理溢出v使使用用二二次次探探查查法法处处理理冲冲突突时时的的搜搜索索成成功功的的平均搜索长度为：平均搜索长度为：v搜索不成功的平均搜索长度为搜索不成功的平均搜索长度为：v可可以以证证明明，当当表表的的长长度度TableSize为为质质数数且且表表的的装装载载因因子子 （表表明明表表的的装装满满程程度度）不不超超过过0.5 时时，新新的的表表项项e一一定定能能够够插插入入，而而且任何一个位置不会被探查两次。且任何一个位置不会被探查两次。v在在搜搜索索时时可可以以不不考考虑虑表表满满情情况况；但但在在插插入入时时必必须须确确保保表表的的装装填填因因子子 不不超超过过0.5。如如果果超超出出必必须将表长度扩充一倍，进行表的分裂。须将表长度扩充一倍，进行表的分裂。v在在删删除除一一个个表表项项时时，为为确确保保搜搜索索链链不不致致中中断断，也也只只能能做做表表项项的的逻逻辑辑删删除除，即即将将被被删删表表项项的的标标记记info改为改为Deleted。v使用双散列方法时使用双散列方法时, 需要两个散列函数。需要两个散列函数。v第第一一个个散散列列函函数数 Hash() 按按表表项项的的关关键键码码 key 计计算算表表项所在的桶号项所在的桶号 H0 = Hash(key)。v一一旦旦冲冲突突，利利用用第第二二个个散散列列函函数数 ReHash() 计计算算该该表表项项到到达达“下下一一个个”桶桶的的移移位位量量。它它的的取取值值与与 key 的的值值有有关关, 要要求求它它的的取取值值应应是是小小于于地地址址空空间间大大小小 TableSize, 且与且与 TableSize 互质的正整数。互质的正整数。v若若设设表表的的长长度度为为 m = TableSize，则则在在表表中中寻寻找找“下下一个一个”桶的公式为桶的公式为 H0 = Hash(key)， p = ReHash(key)； Hi = (Hi-1+ p) % m； p是小于是小于m且与且与m互质的整数互质的整数双散列法双散列法v利用双散列法利用双散列法, 按一定的距离按一定的距离, 跳跃式地寻找跳跃式地寻找“下一个下一个”桶桶, 减少了减少了“堆积堆积”的机会。的机会。v双散列法的探查序列也可写成：双散列法的探查序列也可写成： Hi = (Hi-1+ ReHash(key) % m， i =1, 2, , m-1v最多经过最多经过 m-1次探查次探查, 它会遍历表中所有位置它会遍历表中所有位置, 回到回到H0 位置。位置。v示例：给出一组表项关键码示例：给出一组表项关键码 22, 41, 53, 46, 30, 13, 01, 67 。散列函数为：。散列函数为： Hash(x)x % 11v散列表散列表HT0.10，ReHash(x) = x % 10 +1。 Hi = (Hi-1 + x % 10 +1) % 11, i = 1, 2, vH0(22) = 0 H0(41) = 8 H0(53) = 9 H0(46) = 2 H0(30) = 8 冲突冲突 p = 1 H1 = 8+1 = 9 冲突冲突 H2 = 9+1 = 10 H0(13) = 2 冲突冲突 p = 4 H1 = 2+4 = 6H0(01) = 1H0(67) = 1 冲突冲突 p = 8 H1 = 1+8 = 9 冲突冲突 H2 = 9+8 = 6 冲突冲突 H3 = 6+8 = 3 0 1 2 3 4 5 6 7 8 9 10 22(1)141(1)253(1)346(1)430(3)513(2)601(1)767(4)8v搜索成功的平均搜索长度搜索成功的平均搜索长度v搜索不成功的平均搜索长度搜索不成功的平均搜索长度u每一散列位置的移位量有每一散列位置的移位量有10种：种：1, 2, , 10。先计。先计算每一散列位置各种移位量情形下找到下一个空位的算每一散列位置各种移位量情形下找到下一个空位的比较次数比较次数, 求出平均值；求出平均值；u再计算各个位置的平均比较次数的总平均值。再计算各个位置的平均比较次数的总平均值。 0 1 2 3 4 5 6 7 8 9 10 22(1)41(1)53(1)46(1)30(3)13(2)01(1)67(4)vRehash()的取法很多。例如的取法很多。例如, 当当m是质数时是质数时, 可定义可定义u ReHash(key) = key % (m-2) +1u ReHash(key) = key / m % (m-2)+1v当当 m 是是 2 的方幂时，的方幂时，ReHash(key) 可取从可取从 0 到到 m-1 中中的任意一个奇数。的任意一个奇数。处理冲突的开散列方法（链地址法）处理冲突的开散列方法（链地址法）v开开散散列列方方法法首首先先对对关关键键码码集集合合用用某某一一个个散散列列函函数数计计算它们的存放位置。算它们的存放位置。v若若设设散散列列表表地地址址空空间间的的位位置置从从 0m-1, 则则关关键键码码集集合合中中的的所所有有关关键键码码被被划划分分为为 m 个个子子集集，具具有有相相同同地地址址的的关关键键码码归归于于同同一一子子集集。我我们们称称同同一一子子集集中中的关键码互为同义词。每一个子集称为一个桶。的关键码互为同义词。每一个子集称为一个桶。v通通常常各各个个桶桶中中的的表表项项通通过过一一个个单单链链表表链链接接起起来来，称称之为同义词子表。之为同义词子表。v所所有有桶桶号号相相同同的的表表项项都都链链接接在在同同一一个个同同义义词词子子表表中中，各链表的表头结点组成一个向量。各链表的表头结点组成一个向量。v向向量量的的元元素素个个数数与与桶桶数数一一致致。桶桶号号为为i的的同同义义词词子子表表的表头结点是向量中第的表头结点是向量中第 i 个元素。个元素。v示例：给出一组表项关键码示例：给出一组表项关键码 Burke, Ekers,Broad, Blum, Attlee, Alton, Hecht, Ederly 。散散列列函函数为：数为：Hash (x)ord (x)ord (A)。v用它计算可得：用它计算可得： Hash (Burke) = 1 Hash (Ekers) = 4 Hash (Broad) = 1 Hash (Blum) = 1 Hash (Attlee) = 0 Hash (Hecht) = 7 Hash (Alton) = 0 Hash (Ederly) = 4v散列表为散列表为 HT0.25，m = 26。（看下页）（看下页）（看下页）（看下页）v通常，每个桶中的同义词子表都很短，设有通常，每个桶中的同义词子表都很短，设有n 个关键个关键码通过某一个散列函数，存放到散列表中的码通过某一个散列函数，存放到散列表中的 m 个桶中。个桶中。那么每一个桶中的同义词子表的平均长度为那么每一个桶中的同义词子表的平均长度为 n / m。以搜索平均长度为以搜索平均长度为 n / m 的同义词子表代替了搜索长的同义词子表代替了搜索长度为度为 n 的顺序表，搜索速度快得多。的顺序表，搜索速度快得多。 0 01 12 23 34 45 56 67 78 89 9AttleeAltonBurkeBroadBlumEkersEderlyHecht使用开散列法的散列表类定义使用开散列法的散列表类定义 #include const int defaultSize = 100;template struct ChainNode /各桶中同义词子表的链结点定义 E data; /元素 ChainNode *link; /链指针;template class HashTable /散列表(表头指针向量)定义public: HashTable (int d, int sz = defaultSize); /散列表的构造函数 HashTable() delete ht; /析构函数 bool Search (K k1, E& e1); /搜索 bool Insert (K k1, E& e1); /插入 bool Remove (K k1, E& e1); /删除private: int divisor; /除数（必须是质数） int TableSize; /容量(桶的个数) ChainNode *ht; /散列表定义 ChainNode *FindPos (K k1);/散列;用开散列法定义的散列表的操作用开散列法定义的散列表的操作template /构造函数HashTable:HashTable (int d, int sz) divisor = d; TableSize = sz; ht = new ChainNode*sz; /创建头结点 assert (ht != NULL); /判断存储分配成功否；template ChainNode *HashTable:FindPos (K k1) /在散列表ht中搜索关键码为k1的元素。函数返回/一个指向散列表中某位置的指针 int j = k1 % divisor; /计算散列地址 ChainNode *p = htj; /扫描第j链的同义词子表 while (p != NULL & p-data != k1) p = p-link; return p; /返回;v其他如插入、删除操作可参照单链表的插入、删除等其他如插入、删除操作可参照单链表的插入、删除等算法来实现。算法来实现。v应应用用开开散散列列法法处处理理冲冲突突, 需需要要增增设设链链接接指指针针，似似乎乎增增加加了了存存储储开开销销。事事实实上上, 由由于于闭闭散散列列法法必必须须保保持持大大量量的的空空闲闲空空间间以以确确保保搜搜索索效效率率，如如二二次次探探查查法法要要求求装装填填因因子子 0.5，而而表表项项所所占占空空间间又又比比指指针针大大得得多多，所所以以使用开散列法反而比闭散列法节省存储空间。使用开散列法反而比闭散列法节省存储空间。 v散列表直接出计算表项存放地址，在关键码与存储位散列表直接出计算表项存放地址，在关键码与存储位置之间直接建立了映象。置之间直接建立了映象。当选择的散列函数能够得当选择的散列函数能够得到均匀的地址分布时到均匀的地址分布时, 在搜索过程中可以不做多次探在搜索过程中可以不做多次探查。查。v由于很难避免冲突由于很难避免冲突, 增加了搜索时间。冲突的出现增加了搜索时间。冲突的出现, 与散列函数选取（地址分布是否均匀）与散列函数选取（地址分布是否均匀）, 处理冲突方处理冲突方法（是否产生堆积）有关。法（是否产生堆积）有关。v在实际应用中使用关键码进行散列时在实际应用中使用关键码进行散列时, 如在用作关键如在用作关键码的许多标识符具有相同的前缀或后缀，或者是相码的许多标识符具有相同的前缀或后缀，或者是相同字符的不同排列的场合，不同的散列函数往往导同字符的不同排列的场合，不同的散列函数往往导致散列表具有不同的搜索性能。致散列表具有不同的搜索性能。v见课本上见课本上294页实验结果。页实验结果。散列表分析散列表分析u 设散列表的表长设散列表的表长m14，散列函数，散列函数H（k）k mod 11，表中，表中已有四个数据元素，如果用二次探测再散列法处理冲突，试求关已有四个数据元素，如果用二次探测再散列法处理冲突，试求关键字为键字为49的数据元素的存储地址。的数据元素的存储地址。01234567891011121315386184解：解： Key=49 H(49)=49 mod 11=5（冲突）（冲突） （5+12） mod 11=6（冲突）（冲突） （5+（-12） mod 11=4（冲突）（冲突） （5+22） mod 11=9（不冲突）（不冲突）49课堂练习课堂练习作业作业vP295 6.9