1、山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列1第第 10 章章跳表和散列跳表和散列（Skip List and Hashing）山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列2本章内容本章内容n10.1 字典 dictionariesn10.2 线性表描述 Linear Listn10.3 跳表描述 Skip List n10.4 散列表描述 Hash tablen10.5 应用 Applications山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列为什么学这章？为什么学这章？n若一维排序数组，我们可以用折半检索在 O(logn)时间内找到表中的一个元素。
2、本章将研究如何构造排序的链表、如何维护（进行插入或删除操作后），以及能否也能在O(logn)时间内进行检索。山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列410.1 字典字典n字典（dictionary）是一些元素的集合。每个元素有一个称作key 的域，不同元素的key 各不相同。n有关字典的操作有：n插入（Insert）具有给定关键字值的元素。n在字典中寻找/搜索（Search）具有给定关键字值的元素。n删除（Delete）具有给定关键字值的元素 n例，班级的学生注册表，key=学号l有重复元素的字典 A dictionary with duplicatesMay be ther
3、e are more than one elements have a same key例，班级的学生考试报表，key=成绩山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列5AbstractDataType 抽象数据类型 Dictionary实例一组带有关键词（=关系）的元素集合操作操作empty()true when the dictionary is emptysize()return the number of elementsfind(k):搜索关键字为k的数对Insert(p):向字典中插入数对perase(k):删除关键字为k的数对山东大学计算机科学与技术学院 数据结构
4、第7章 跳表和散列6TemplateClass dictionary()Public:virtual dictionary()virtual bool empty()const=0;virtual int size()const=0;virtual pair*find(const K&)const=0;virtual void erase(const k&)=0;virtual void insert(const pair&)=0;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列710.2 线性表描述线性表描述n有序线性表:L=(e1,e2,e3,en),n关键字从左到右依次增大 n
5、在计算机存储器中的数据描述n公式化描述n链表描述山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列8链表描述的有序线性表（字典）链表描述的有序线性表（字典）采用链表描述的有序线性表有序链表n类 SortedChain山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列9类类 SortedChaintemplate struct pairNode typedef pair pairType;pairType element;pairNode*next;pairNode(const pairType&thePair):element(thePair)pairNode(const pa
6、irType&thePair,pairNode*theNext):element(thePair)next=theNext;firste1e20eneiei-1ei+1山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列10Class SortedChaintemplateclass sortedChain:public dictionary public:sortedChain()firstNode=NULL;dSize=0;sortedChain();bool empty()const return dSize=0;int size()const return dSize;pair*
7、find(const K&)const;void erase(const K&);void insert(const pair&);void output(ostream&out)const;protected:pairNode*firstNode;/pointer to first node in chain int dSize;/number of elements in dictionary;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列11操作操作 findtemplatepair*sortedChain:find(const K&theKey)const/搜索与k匹配的元
8、素，/如果没有匹配的元素，则返回NULL pairNode*currentNode=firstNode;while(currentNode!=NULL¤tNode-element.first next;if (currentNode!=NULL¤t-element.first=theKey)return¤t-element;/与theKey相匹配 return NULL;/不存在相匹配的元素山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列12操作操作 Insert firste1e20eneiei-1ei+1p：从表头开始第一个大于x的节点tpfi
9、rste1e20eneiei-1ei+1ptp=0eqeq山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列13templatevoid sortedChain:insert(const pair&thePair)/如果表中不存在关键值与e相同的元素，则插入e,否则替换 pairNode*p=firstNode,*tp=NULL;/p指向节点的前驱 while(p!=NULL&p-element.first next;if(p!=NULL&p-element.first=thePair)p-element.second=thePair.second;/替换旧值 return；/若没有出
10、现重复关键值,则产生一个关键值为e的新节点 pairNode*newNode=new pairNode(thePair,p);if(tp=NULL)firstNode=newNode;/新节点插入表头 else tp-next=newNode;dSize+;return;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列14操作操作 erasefirste1e20eneiei-1ei+1ptpfirste1e20eneiei-1ei+1ptp=0tp-link=p-linkfirst=p-link山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列15templatevoid s
11、ortedChain:erase(const K&theKey)/删除与theKey相匹配的元素，pairNode*p=firstNode,tp=NULL；/p 指向匹配的节点，tp 指向p 前面的节点。while(p!=NULL&p-element.first next;/搜索与k相匹配的元素 /验证是否与k匹配 if(p!=NULL)&p-element.first=theKey)/找到一个相匹配的元素 if（tp=NULL）firstNode=p-next;else tp-next=p-next;是链首节点 delete p;dSize-;山东大学计算机科学与技术学院 数据结构 第7章
12、跳表和散列n作业 p 239 5山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列1710.4 Skip Listn10.4.1 理想情况n10.4.2 插入和删除n10.4.3 级的分配n10.4.4 类SkipNoden10.4.5 类SkipListn10.4.6 复杂性山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列187.3.1 ideal case20243040607580Search:最坏情况下的比较次数 f(n)=n Search:f(n)=n/2+1 if we keep a pointer in the middle.202430406075802024
13、3040607580210山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列1910.3 理想状态的节点分布理想状态的节点分布n0 级链上元素数:n n1 级链上元素数:n n2 级链上元素数：n nni 级链上元素数:n/2i n我们称元素 a 是第i 层元素，若它也是0i-1层的元素，但a不是第i+1层元素。nE.g.40 是层 2 元素,而 24 和75 是层1元素。山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列20n跳表(skip list):n在跳表结构中，每个节点有一维数组表示层次的链。n0级链是包含所有元素的有序链表，1级链是0级链的一个子集。i级链所包含的元
14、素是i-1级链所有元素的子集.山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列插入和删除插入和删除n和sortedChain一样，插入和删除要保持表仍然是排序的，同时要给链表组赋值，而新增节点的层次要动态确定。山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列227.3.2 插入和删除插入和删除ni 级链上元素数:n/2ini-1级元素属于i级链的概率是：1/2 n一个元素属于i级链概率是：1/2i=(1/2)i n链的级数：log2n +121020243040607580山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列23insert an element wi
15、th value 77山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列元素插入元素插入n1)发现插入位置n2)对新元素赋予层数值i;n3)对新元素和其他在层数 0 i 的节点指针可能要更改。n元素删除n1)从最高层逐次向下搜索该元素 i,n2)删除该元素并对原来想邻接的节点的指针进行修改。山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列新增节点的新增节点的level确定确定n我们假定每个节点在level 0 的概率为1，其他是独立按概率p增加的，n1层 pn2层 p*pnnd 层 pd n如何实现？用系统的随机函数rand(),每次产生随机数在 0 RAND_MAX.山东大
16、学计算机科学与技术学院 数据结构 第7章 跳表和散列267.3.3 level assignmentnThen the probability that the next random number is CutOff=p*RAND_MAX is p。lIf next random number is Cutoff,then the new element should be in level 1,and check the next random numberlGenerally,the final level assigned to the new element is int lev=0
17、while(rand()=CutOff)lev+;0 cutoff RAND_MAX =p*RAND_MAX 山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列277.3.3 级的分配级的分配n缺点1：可能为某些元素分配特别大的级，从而导致一些元素的级远远超过loglog1/p1/pN N（N为字典中预期的最大数目,因此，n在有N个元素的跳表中，级的最大值 MaxLevel=loglog1/p1/pN N-1-1，以此值作为上限。n缺点2：可能存在下面的情况，如在插入一个新元素前有三条链，而在插入之后就有了10条链。这时，新插入元素的为9级，。n我们可以把新元素的级调整为3。即把新元素
18、的级调整为最大级数+1。山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列结构结构 SkipNoden头节点需要最大层数的指针;n尾节点不需要指针;n每个节点包含element 部分、指针部分（比它 level多1）山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列29 7.3.4 类类SkipNodetemplatestruct SkipNode typedef pair pairType;pairType element;skipNode*next;/一维指针数组 skipNode(const pairType&thePair,int size):element(thePa
19、ir)next=new skipNode*size;0 1 2 size-1next20243040607580山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列30#ifndef skipList_#define skipList_#include#include#include#include#include dictionary.h#include skipNode.h#include myExceptions.husing namespace std;templateclass skipList:public dictionary public:skipList(K,int m
20、axPairs=10000,float prob=0.5);skipList();山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列31 bool empty()const return dSize=0;int size()const return dSize;pair*find(const K&)const;void erase(const K&);void insert(const pair&);void output(ostream&out)const;protected:float cutOff;/used to decide level number int level()c
21、onst;/generate a random level number int levels;/max current nonempty chain int dSize;/number of pairs in dictionary int maxLevel;/max permissible chain level K tailKey;/a large key skipNode*search(const K&)const;/search saving last nodes seen skipNode*headerNode;/header node pointer skipNode*tailNo
22、de;/tail node pointer skipNode*last;/lasti=last node seen on level i;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列32templateskipList:skipList(K largeKey,int maxPairs,float prob)/Constructor for skip lists with keys smaller than largeKey and/size at most maxPairs.0 prob 1.cutOff=prob*RAND_MAX;maxLevel=(int)ceil(logf
23、(float)maxPairs)/logf(1/prob)-1;levels=0;/initial number of levels dSize=0;tailKey=largeKey;/create header&tail nodes and last array pair tailPair;/申请变量 tailPair.first=tailKey;/赋值 headerNode=new skipNode(tailPair,maxLevel+1);tailNode=new skipNode(tailPair,0);/建立尾结点 last=new skipNode*maxLevel+1;/用于记录
24、指针的数组 /header points to tail at all levels as lists are empty for(int i=0;i nexti=tailNode;/建立首尾两个节点的链接山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列33templateskipList:skipList()/Delete all nodes and array last.skipNode*nextNode;/delete all nodes by following level 0 chain while(headerNode!=tailNode)nextNode=headerN
25、ode-next0;/沿着0层删除 delete headerNode;headerNode=nextNode;delete tailNode;delete last;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列34templatepair*skipList:find(const K&theKey)const/fa/Return NULL if no matching pair.if(theKey=tailKey)return NULL;/超出合理关键词的取值范围了 /position beforeNode just before possible node with theKe
26、y skipNode*beforeNode=headerNode;/要找的节点前驱节点 for(int i=levels;i=0;i-)/从上到下逐层寻找 /follow level i pointers while(beforeNode-nexti-element.first nexti;/check if next node has theKey if(beforeNode-next0-element.first=theKey)return&beforeNode-next0-element;return NULL;/no matching pair山东大学计算机科学与技术学院 数据结构 第
27、7章 跳表和散列35templateint skipList:level()const/Return a random level number=maxLevel.int lev=0;while(rand()=cutOff)lev+;return(lev=maxLevel)?lev:maxLevel;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列36templateskipNode*skipList:search(const K&theKey)const/Search 作为一个辅助函数，找到含有theKey的节点，并且/为记录level 的数组last赋值 skipNode*bef
28、oreNode=headerNode;for(int i=levels;i=0;i-)while(beforeNode-nexti-element.first nexti;lasti=beforeNode;/last 记录了该插入或删除节点每层的前驱节点 return beforeNode-next0;/返回指向要找节点的指针山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列37templatevoid skipList:insert(const pair&thePair)/基于search的查找，插入新节点，或修改已有节点if(thePair.first=tailKey)/key t
29、oo large ostringstream s;s Key=thePair.first Must be tailKey;throw illegalParameterValue(s.str();/see if pair with theKey already present skipNode*theNode=search(thePair.first);if(theNode-element.first=thePair.first)/已经存在只改值 /update theNode-element.second theNode-element.second=thePair.second;return
30、;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列38/增加新节点，首先计算该节点指针数组大大小，及所在层次 int theLevel=level();/level of new node /fix theLevel to be levels)theLevel=+levels;lasttheLevel=headerNode;/因为新增加了一层，必须从头开始 /get and insert new node just after theNode skipNode*newNode=new skipNode(thePair,theLevel+1);for(int i=0;i nexti=l
31、asti-nexti;lasti-nexti=newNode;dSize+;return;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列39emplatevoid skipList:erase(const K&theKey)/Delete the pair,if any,whose key equals theKey.if(theKey=tailKey)/too large return;/see if matching pair present skipNode*theNode=search(theKey);if(theNode-element.first!=theKey)/no
32、t present return;/delete node from skip list for(int i=0;i nexti=theNode;i+)lasti-nexti=theNode-nexti;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列40/update levels while(levels 0&headerNode-nextlevels=tailNode)levels-;delete theNode;dSize-;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列41templatevoid skipList:output(ostream&out)cons
33、t/Insert the dictionary pairs into the stream out./follow level 0 chain for(skipNode*currentNode=headerNode-next0;currentNode!=tailNode;currentNode=currentNode-next0)out element.first element.second ;/overload template ostream&operator(ostream&out,const skipList&x)x.output(out);return out;山东大学计算机科学与
34、技术学院 数据结构 第7章 跳表和散列4210.3.5 类类SkipList20243040607580HeadTail山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列43 操作操作 Search20243040607580HeadTailpk山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列44操作操作 InsertlastLevel 0 1 2 20243040607580HeadTail20243040607580HeadTail77p210210山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列457.3.6 复杂性复杂性n时间复杂性:n最坏情况:n可能只有一
35、个MaxLevel级元素，且余下的所有元素均在0级链上.n搜索(Search),插入(Insert),删除(Delete):O(MaxLevel+n)n平均复杂性:O(log2n)山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列n作业:p246 8山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列4710.5 散列表散列表hash tablen10.1 理想哈希n10.2 基于一维数组的哈希表n10.3 基于链式结构的哈希表n一般假定可以把字符串转换为整数山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列4810.13 把字符串转换为整数int stringToLon
36、g(string s)int length=(int)a.length;/假定3 long answer=s.at(0);answer=(answer 8)+s.at(1)return(answer 8)+s.at(2);山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列49hash(C+STLTemplateclass hash public:size_t operator()(const string theKey)const/把关键词theKey转换为非负的整数 unsisgned long hashValue=0;int length=(int)theKey.length();
37、for(int i=0;ilength;i+)hashValue=5*hashValue+theKey.at(i);return size_t(hashValue);山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列5010.4.1 Ideal hashing 元素个数不多，可以建立一个1-1函数，把每个key 映射到Hash表的一个位置。如元素e,k 是其关键词，我们查找时可以计算f(k),若hash表的f(k)位置不空，返回其值，否则说元素不在表中。E.g,学生的 ID 在 951000 952000,f(k)=k-951000山东大学计算机科学与技术学院 数据结构 第7章 跳表和
38、散列51Operations n散列表操作:n搜索（搜索（Search）:计算出f(k)，然后看表中f(k)处是否有元素。n插入（插入（Insert）:计算出f(k)，把元素放在f(k)位置n删除（删除（Delete）:计算出f(k)，把表中f(k)位置置为空n在理想情况下,散列表操作时间复杂性：(1)ninitialization:initialize an empty dictionary with b position,O(b)山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列52更一般的情况更一般的情况元素集合要远远大于哈希表，函数f是多对一。关键词为 k1,k2,km,但f(
39、k1)=f(k2)=f(km).山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列53Hashing functionsn若key是正整数，nf(K)=k%D （%为求模操作符）nD:是散列表的大小(即位置数)n散列表中的位置号:0D-1n每一个位置称为桶(bucket)n f(K)存储关键字为k的元素的起始桶（home bucket）。n若不是正整数，但可以通过转换，转为正整数，也可以用这种方法。山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列54n元素:22,33,3,72,85n散列表：ht0:7n散列函数:f(key)=key%80 1 2 3 4 5 6 7 72
40、33 3 85 220 1 2 3 4 5 6 7例例山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列55n 25 放入什么地方?n f(25)=1n25 的起始桶已经被另一个数占用 这种情况被称为是碰撞碰撞（collision）n具有相同hash 函数值的不同关键词被称为是同义同义词词(synonyms)n25 和 33 是同义词同义词 0 1 2 3 4 5 6 7 72 33 3 85 22碰撞和同义词山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列56n存储桶中若没有空间时就发生溢出溢出（overflow）n当每个桶只能存储一个元素时，碰撞和溢出会同时发生.n解决溢
41、出的方法：n线性开型寻址(Linear open addressing)n链表散列/链地址散列（Chaining）0 1 2 3 4 5 6 7 72 33 3 85 22溢出（溢出（overflow）山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列577.4.2 线性开型寻址散列线性开型寻址散列n当溢出发生时，将元素插入下一个可用桶中。在寻找下一个可用桶时，表被视为环形的。n例n散列表的大小b=11nf(k)=k%bn在插入 80,40,和65之后山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列58线性开型寻址散列线性开型寻址散列n在插入 58和24之后n f(58)=3
42、 (碰撞);f(24)=2在插入 35之后f(35)=2 (碰撞)山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列59线性开型寻址散列线性开型寻址散列在插入 98之后nf(98)=10 (碰撞)98(d)山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列60线性开型寻址散列线性开型寻址散列nSearch 操作n首先搜索关键字为K的起始桶f(k)n接着对表中后继桶进行搜索，直到下面其中之一情况发生：(1)存有关键字为K 的桶已找到，即找到了要搜索的元素。(2)到达一个空桶；(3)又回到起始桶f(k)。n若发生情况(2)和(3),，则说明表中没有关键字为k的元素。山东大学计算机科
43、学与技术学院 数据结构 第7章 跳表和散列61线性开型寻址散列线性开型寻址散列nDelete 操作n执行搜索操作，找到关键字为K 的桶.n在完成一次删除操作后，必须能保证上述的搜索过程仍能够正常进行。不能仅仅把表中相应位置置为空。f(24)=f(35)=2,f(80)=f(58)=3,Delete:58;然后 search:35 （f(35)=2）24800 1 2 3 4 5 6 7 8 9 10354065山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列hash table 删除删除n方法 1 当一个桶的元素被删除后，其后面的桶的元素要前移。n Method 2:采用标记 Nev
44、erUsed，对每个桶设为，对每个桶设为初始值初始值=true。当有元素放入，改为 false.山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列63templateclass hashTable public:hashTable(int theDivisor=11);hashTable()delete table;bool empty()const return dSize=0;int size()const return dSize;pair*find(const K&)const;void insert(const pair&);void output(ostream&out)c
45、onst;protected:int search(const K&)const;pair*table;/hash table hash hash;/maps K to integer int dSize;/number of pairs in dictionary int divisor;/hash function divisor;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列64templatehashTable:hashTable(int theDivisor)divisor=theDivisor;dSize=0;/allocate and initialize hash
46、table array table=new pair*divisor;for(int i=0;i divisor;i+)tablei=NULL;山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列65templateint hashTable:search(const K&theKey)const/theKey 是要检索的元素关键词，其实与theKey的哈希映射位置，遍历整个表，若找到该元素或空置单元，则返回位置下标 int i=(int)hash(theKey)%divisor;/home bucket int j=i;/start at home bucket do if(table
47、j=NULL|tablej-first=theKey)return j;j=(j+1)%divisor;/next bucket while(j!=i);/returned to home bucket?return j;/table full山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列66templatepair*hashTable:find(const K&theKey)const/查找是否含有theKey的元素在表中？在返回全部信息，否则/null int b=search(theKey);/see if a match was found at tableb if(tab
48、leb=NULL|tableb-first!=theKey)return NULL;/no match return tableb;/matching pair山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列67templatevoid hashTable:insert(const pair&thePair)/插入对（K,E），若已经存在，在把第二部分修改int b=search(thePair.first);/check if matching pair found if(tableb=NULL)/no matching pair and table not full tableb
49、=new pair(thePair);dSize+;else 山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列68/check if duplicate or table full if(tableb-first=thePair.first)/duplicate,change tableb-second tableb-second=thePair.second;else/table is full throw hashTableFull();山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列697.4.3 链表散列链表散列n在发生溢出时，采用链表链表（chaining）来进行
50、解决。每个桶仅含有一个节点指针，所有的元素都存储在该指针所指向的链表中。n保持一个链表上的元素是具有同样起始桶的元素。山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列707.4.3 链表散列链表散列（直接利用（直接利用Sorted Chain 实现）实现）n搜索（Search）:n计算起始桶号为 f(k)=k%D;然后搜索该桶所对应的链表.n插入（Insert）:n计算 f(k);搜索;插入.由于每次插入都要首先进行一次搜索，因此把链表按照升序排列比无序排列会更有效。n删除（Delete）:n计算 f(k);搜索;删除.山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列71t
