跳表和Hash技术课件.ppt

1、学习内容v有序数组二分搜索，O(logn)v有序链表顺序搜索，O(n)v跳表*：在链表上实现二分搜索增加一些辅助指针，提高搜索、插入、删除性能，O(logn)vhash技术，插入、删除O(1)v应用文本压缩和解压缩7.1 字典v抽象数据类型描述抽象数据类型Dictionary实例具有不同关键字的元素集合操作Create()：创建一个空字典Search(k,x)：搜索关键字为k的元素，结果放入x；如果没找到，则返回false，否则返回trueInsert(x)：向字典中插入元素xDelete(k,x)：删除关键字为k的元素，并将其放入x字典操作v随机访问，random accessv顺序访问，s

2、equential accessBegin，Nextv重要的操作方式是“按关键字访问”v需注意的一个问题：重复关键字如何消除歧义字典例v一个班注册学习数据结构课程的学生新学生注册在字典中插入相关的元素(记录)放弃这门课程删除对应记录查询字典获取特定学生相关的记录或修改记录学生的姓名域可作为关键字字典例（续）v在编译器中定义用户标识符的符号表（symbol table）重复元素字典定义标识符建立一个记录并插入到符号表中同样的标识符名可以定义多次(在不同的程序块中)相同关键字的记录搜索结果最新插入的元素删除程序块的结尾（标识符作用域结束）7.2 字典的线性表描述v(e1,e2,.,)ei：字典元素

3、，关键字升序排列v公式化描述搜索操作：二分搜索，O(logn)插入、删除操作：需数据移动，O(n)v链表描述搜索、插入、删除均为O(n)SortedChain类templateclass SortedChain public:SortedChain()first=0;SortedChain();bool IsEmpty()const return first=0;int Length()const;bool Search(const K&k,E&e)const;SortedChain&Delete(const K&k,E&e);SortedChain&Insert(const E&e);Sor

4、tedChain&DistinctInsert(const E&e);void Output(ostream&out)const;private:SortedChainNode*first;/pointer to first node;搜索操作templatebool SortedChain:Search(const K&k,E&e)const/Put element that matches k in e./Return false if no match.SortedChainNode*p=first;/search for match with k while(p&p-data link

5、;/verify match if(p&p-data=k)/yes,found match e=p-data;return true;return false;/no match删除操作templateSortedChain&SortedChain :Delete(const K&k,E&e)/Delete element that matches k./Put deleted element in e./Throw BadInput exception if no match.SortedChainNode*p=first,*tp=0;/trail p /search for match w

6、ith k while(p&p-data link;删除操作（续）/verify match if(p&p-data=k)/found a match e=p-data;/save data /remove p from chain if(tp)tp-link=p-link;else first=p-link;/p is first node delete p;return*this;throw BadInput();/no match return*this;/Visual C+needs this line插入操作templateSortedChain&SortedChain:Insert

7、(const E&e)/Insert e,throw an exception if no space.SortedChainNode*p=first,*tp=0;/trail p /move tp so that e can be inserted after tp while(p&p-data link;/setup a new node*q for e SortedChainNode*q=new SortedChainNode;q-data=e;插入操作（续）/insert node just after tp q-link=p;if(tp)tp-link=q;else first=q;

8、return*this;不允许重复关键字的插入templateSortedChain&SortedChain :DistinctInsert(const E&e)/Insert e only if no element with same key/currently in list./Throw BadInput exception if duplicate.SortedChainNode*p=first,*tp=0;/trail p /move tp so that e can be inserted after tp while(p&p-data link;不允许重复关键字的插入(续)/c

9、heck if duplicate if(p&p-data=e)throw BadInput();/not duplicate,set up node for e SortedChainNode*q=new SortedChainNode;q-data=e;/insert node just after tp q-link=p;if(tp)tp-link=q;else first=q;return*this;7.3 跳表*7.3.1 理想情况v链表描述字典有很多优点，但搜索操作性能太差O(n)v能不能保持链表描述，保留这些优点，但把搜索性能提高到O(logn)？v链表上的二分搜索，添加指针来实

10、现添加指针以提高性能vn次比较n/2+1次比较，性能提高一倍跳表继续添加辅助指针v0级链，初始链，7（n）个元素v1级链，3（n/2）个元素：2、4、6v2级链，1（n/4）个元素：4一般跳表v2k个元素，k级链，每2i个元素有一个i级链指针v元素在0i级链，不在i+1级链i级链元素v40：2级链元素24、75：1级链元素20、30、60、80：0级链元素7.3.2 插入和删除操作v完美的跳表结构i级链有n/2i个元素，每个链接跳越2i个节点搜索操作完美的性能，最好、最坏、平均都是O(logn)但为保持这种完美结构，插入操作算法复杂v无需追求完美的搜索性能，平均情况为O(logn)即可随机插入

11、方法v（概率上）接近完美结构：从统计学角度，平均性能达到O(logn)v考虑二分跳表特性0级链元素占元素总数比例为1、1级为1/2，.，i级为1/2i，.因此，如果使新元素落入第i级链表的可能性为1/2i，则概率上可接近完美结构递推方式：i-1级元素属于i级的概率1/2一般跳表的情况v三分跳表、四分跳表、.新元素落入i级的可能性pi链的级数i-1级元素属于i级的概率p1log/1np插入元素77v为77分配级数随机产生v删除操作无法控制结构7.3.3 级的分配 int lev=0;while(rand()=CutOff)（CutOff=p*RAND_MAX）lev+;v循环每次继续运行的概率为

12、plev级元素属于lev+1级的概率为p新元素落入第i级链的概率piv循环停止元素的级数设定为lev优化考虑v避免级数过高MaxLevel=v避免插入前后级数相差过多去掉空级降低新元素的级数，最多为原最大级数+11log/1np级分配例v最多有1024个元素的字典设p=0.5，MaxLevel=log21024-1=9若RAND_MAX=232-1，CutOff=231-1初始：空字典，头节点10个指针，每个对应一条链表，且从头节点指向尾节点插入第一个元素，分配0到9之间的一个级若为9，则要修改九个指针由于没有0，1，.，8级元素，故可以把该元素的级改为0，这样只需修改一条指针即可另一种级分配

13、算法v随机数产生器的值分为几段v第一段对应1-1/p，第二段包括1/p-1/p2，.v产生的随机数不在第i段中，则为此元素分配i-1级7.3.4 SkipNode类templateclass SkipNode friend SkipList;private:SkipNode(int size)link=new SkipNode*size;SkipNode()delete link;E data;SkipNode*link;/多级链表指针;7.3.5 SkipList类templateclass SkipList public:SkipList(K Large,int MaxE=10000,fl

14、oat p=0.5);SkipList();bool Search(const K&k,E&e)const;SkipList&Insert(const E&e);SkipList&Delete(const K&k,E&e);void Output();SkipList类private:int Level();SkipNode*SaveSearch(const K&k);int MaxLevel;/max permissible chain level int Levels;/max current nonempty chain int CutOff;/used to decide level

15、number K TailKey;/a large key SkipNode*head;/head node pointer SkipNode*tail;/tail node pointer SkipNode*last;/插入操作时保存新元素在各级链表中的位置;构造函数templateSkipList:SkipList(K Large,int MaxE,float p)/Constructor.CutOff=p*RAND_MAX;MaxLevel=ceil(log(MaxE)/log(1/p)-1;TailKey=Large;Levels=0;/initial number of levels

16、构造函数 /create head&tail nodes and last array head=new SkipNode(MaxLevel+1);tail=new SkipNode(0);last=new SkipNode*MaxLevel+1;tail-data=Large;/head points to tail at all levels as empty for(int i=0;i linki=tail;析构函数templateSkipList:SkipList()/Delete all nodes and array last.SkipNode*next;/delete all n

17、odes by deleting level 0 while(head!=tail)next=head-link0;delete head;head=next;delete tail;delete last;类E（元素）如何实现比较操作class element friend void main(void);public:operator long()const return key;element&operator=(long y)key=y;return*this;private:int data;long key;vEK的转换函数v重载=运算符需两个版本搜索算法mk级链表，按什么顺序搜索

18、？m每级链表的搜索从什么位置开始？通过关键字进行搜索templatebool SkipList:Search(const K&k,E&e)const/Search for element that matches k./Put matching element in e./Return false if no match.if(k=TailKey)return false;通过关键字进行搜索 /position p just before possible node with k SkipNode*p=head;for(int i=Levels;i=0;i-)/go down levels w

19、hile(p-linki-data linki;/pointers /check if next node has key k e=p-link0-data;return(e=k);SavedSearch函数v插入、删除操作利用此函数vlast数组记录每级链表中位于k之前的节点templateSkipNode*SkipList:SaveSearch(const K&k)/Search for k and save last position/visited at each level./position p just before possible node with kSavedSearch

20、函数 SkipNode*p=head;for(int i=Levels;i=0;i-)while(p-linki-data linki;lasti=p;/last level i node seen return(p-link0);插入操作v分配级数的函数templateint SkipList:Level()/Generate a random level number=MaxLevel.int lev=0;while(rand()=CutOff)lev+;return(lev=MaxLevel)?lev:MaxLevel;插入操作（续）templateSkipList&SkipList:I

21、nsert(const E&e)/Insert e if not duplicate.K k=e;/extract key if(k=TailKey)throw BadInput();/too large /see if duplicate SkipNode*p=SaveSearch(k);if(p-data=e)throw BadInput();/duplicate 插入操作（续）/not duplicate,determine level for new node int lev=Level();/level of new node /fix lev to be Levels)lev=+L

22、evels;lastlev=head;插入操作（续）/get and insert new node just after p SkipNode*y=new SkipNode(lev+1);y-data=e;for(int i=0;i linki=lasti-linki;lasti-linki=y;return*this;插入操作例LastLastlev=177只插入0级、1级链删除操作templateSkipList&SkipList:Delete(const K&k,E&e)/Delete element that matches k.Put deleted/element in e.Th

23、row BadInput if no match.if(k=TailKey)throw BadInput();/too large /see if matching element present SkipNode*p=SaveSearch(k);if(p-data!=k)throw BadInput();/not present 删除操作（续）/delete node from skip list for(int i=0;i linki=p;i+)lasti-linki=p-linki;/update Levels while(Levels 0&head-linkLevels=tail)Le

24、vels-;e=p-data;delete p;return*this;将元素从其所在的所有级别的链表中摘除7.3.6 复杂性分析v时间复杂性搜索、插入、删除最坏情况O(n+MaxLevel)但平均情况为O(logn)复杂性分析v空间复杂性最坏情况：元素n*sizeof(element)，指针O(n*MaxLevel)平均情况：n*p个元素在1级链，n*p2个元素在2级链，.，n*pi在i级链，.pnpnMaxLevelii107.4 hash技术v关键字hash表位置v元素e的关键字为k，hash函数he在hash表中的位置为h(k)v搜索操作表位置h(k)空，失败；否则，成功v删除：将位置

25、h(k)置为空v插入操作表位置h(k)不空：冲突，特殊处理hash函数7.4.1 理想Hashv学生记录字典，关键字ID号(六位整数)最多100个学生，ID号951000952000hash函数h(k)=k-951000ID号01000hash表数组ht1001 初始化：hti.key=0，0i1000 搜索关键字为k的元素：计算h(k)=k-951000vhth(k)的关键字域不为0，成功；此情况下，可容易实现删除操作，hth(k)0v=0，搜索失败。此情况下，可容易实现插入操作hash表基本问题v理想情况下，hash表的搜索、插入、删除操作的时间复杂性均为(1)v上例，可能的关键字数目=h

26、ash表大小|U|=mv但一般来说，|U|=Nm冲突不可避免，hash技术要解决的关键问题常见hash函数设计方法vHash函数设计原则计算简单、快速否则(1)的优势就会被抵消函数值均匀分布于hash表避免冲突的集中带来性能上的巨大下降实际关键字集合|S|=n尽量小使1021)(miSih截取法（truncation）v忽略关键字的某些部分，其余部分直接作为hash函数值关键字8位整数，哈希表大小1000取关键字右数第1、2、5位数字作为索引21296876976计算速度快，但往往分布不均v平方取中法计算关键字的平方取二进制表示的中间部分折叠法（folding）v关键字划分为若干部分v组合成（

27、通常通过加法或乘法）索引值v8位整数可分为3、3、2三个部分v相加（如必要取模）得到索引值v21296876212+968+76=1256256v比截取法分布更加均匀取模法v关键字整数，对hash表大小取模作为函数值v索引分布很大程度依赖于模数（表大小）v小整数（2，10）的幂，冲突很多v常用的好的方法，质数v1000，1024997，1009乘式法vmod 1表示取小数部分v有研究指出v当m=1024，k=42237时)1mod()(akmkh可能效果最好618.02/)15(a477)1mod618.042237(1024)(kh7.4.2 线性探测开地址法vhash函数：取模法，h(k)

28、=k%mv例：桶数m=11如何解决冲突（collision）？v冲突：不同关键字的hash函数值相同 h(k1)=h(k2)v解决冲突两个问题关键字冲突的元素保存在哪个区域？每个冲突关键字保存的具体位置？冲突元素的保存区域v相同区域hash表中其他位置开地址法（open addressing）有什么缺点？v不同区域hash表之外的空间溢出链表法冲突元素具体保存位置v一个步骤可能无法找到，需逐步尝试多个位置，探测可放置新元素的空位vhi(k)=(h(k)+F(i)%m，i=0,1,2,v线性探测（linear probe）F(i)=i按h(k)、h(k)+1、的顺序寻找空桶线性探测开地址法实例v

29、接上例，hash表中已保存了80和40v插入58，58%11=3，与80冲突，从4开始检测空桶，插入位置4搜索操作v从h(k)开始顺序检查，直到某个桶满足：关键字与目标关键字相同，搜索成功空桶或回到h(k)，搜索失败搜索操作v搜索35，h(58)=22号桶，关键字不符；3号，不符；4号，不符；5号，成功v搜索46：2号-5号，不符；6号，失败删除操作v不能简单删除，会影响后续搜索操作删除80，会造成58、35搜索失败删除58，会造成搜索35失败解决方法v方法一数据移动，性能差！v方法二用NeverUsed标记，区分从未使用过的桶和使用后又释放的桶修改搜索算法，遇到NeverUsed桶才失败Ha

30、shTable类templateclass HashTable public:HashTable(int divisor=11);HashTable()delete ht;delete empty;bool Search(const K&k,E&e)const;HashTable&Insert(const E&e);void Output();/output the hash table HashTable类 private:int hSearch(const K&k)const;int m;/hash function divisor E*ht;/hash table array bool*

31、empty;/1D array;NeverUsed构造函数templateHashTable:HashTable(int divisor)/Constructor.m=divisor;/allocate hash table arrays ht=new E m;empty=new bool m;/set all buckets to empty for(int i=0;i m;i+)emptyi=true;辅助函数hSearchtemplateint HashTable:hSearch(const K&k)const/Search an open addressed table./Return

32、 location of k if present./Otherwise return insert point if there is space.int i=k%m;/home bucket int j=i;/start at home bucket do if(emptyj|htj=k)return j;j=(j+1)%m;/next bucket while(j!=i);/returned to home?return j;/table full三种返回情况：1、emptyb=true，可插入该位置2、htj=k，重复3、htbk，且emptyb=false，表满搜索函数Searcht

33、emplatebool HashTable:Search(const K&k,E&e)const/Put element that matches k in e./Return false if no match.int b=hSearch(k);if(emptyb|htb!=k)return false;e=htb;return true;插入操作templateHashTable&HashTable:Insert(const E&e)/Hash table insert.K k=e;/extract key int b=hSearch(k);/check if insert is to b

34、e done if(emptyb)emptyb=false;htb=e;return*this;/no insert,check if duplicate or full if(htb=k)throw BadInput();/duplicate throw NoMem();/table full return*this;/Visual C+needs this line线性探测法的特点v优点简单只要表不满，总可以找到空位，插入成功线性探测法的特点v缺点聚集问题h(k1)=i，h(k2)=j，k1可能占据k2的hash表位置，从而可能在局部造成严重的聚集，性能急剧下降，即便hash表还很空而当表

35、较满时，性能几乎一定会很差复杂性分析v初始化：(m)v搜索、插入最坏情况：(n)平均情况vUn：一次不成功搜索平均检查的桶的数目vSn：一次成功搜索平均检查的桶的数目va=n/m：负载因子hash表满的程度0.5：Sn=1.5，Un=2.50.8：Sn=5.5，Un=50.5aa11121)1(11212nnSUhash表大小的确定v对hash表的性能有重要影响v取素数，或无20的素数因子v性能决定：由n，Un，Sn值am例：n大约1000，要求Un4，Sn50.5v由Un公式a0.9，Sn公式a6/7a6/7v因此，m应该(7n/6)=1167vm=37*37=1369是较好选择v方法二：根

36、据最大可能空间，取不大于的整数，53023*23=529平方探测法（Quadratic Probe）v线性探测的缺点：聚集h(k)不相同的（相近的）关键字发生冲突v平方探测法：F(i)=i2探测h(k)、h(k)+1、h(k)+4、与线性探测的比较v解决了局部聚集问题v缺点：在表不满的情况下，也不能保证插入肯定成功定理：如果表大小为质数，只能探测到一半空间，另一半的空间探测不到乐观的看，a0.5时，总能保证插入成功证明考虑第i次探测和第j次探测，如果位置相同，则有h(k)+i2 h(k)+j2(mod m)i2 j2 0(mod m)(i+j)(i j)0(mod m)i-j整除m或i+j整除

37、m考虑前m次探测(0m-1)，情况1显然不可能，而(1,m-1),(m-1)/2,(m+1)/2)均满足情况2仅探测了(1+m)/2个位置双散列法vF(i)=i*h2(k)启用第二个hash函数vh2(k)的选择要小心vh2(k)=k%9，若k=99的话，这个方法根本不起作用了v即：h2(k)绝对不能为0！v类似h2(k)=m k%m会有比较好的效果hash表的扩展：rehashingv如果hash表较满，性能下降，插入操作可能失败v初始化一个很大的hash表，空间浪费v只能这样吗？在需要的时候扩充预先设定一个阈值当a达到此值时，将表大小扩展两倍（素数）将元素逐一插入到新的表中扩展操作显然很耗

38、时，影响对应的插入操作7.4.3 溢出链表法解决冲突冲突：额外空间保存链表相同hash函数值元素一个链表冲突情况下的插入、删除、搜索链表的插入、删除、搜索ChainHashTable类templateclass ChainHashTable public:ChainHashTable(int divisor=11)m=divisor;ht=new SortedChain m;ChainHashTable()delete ht;bool Search(const K&k,E&e)const return htk%m.Search(k,e);ChainHashTable类 ChainHashTab

39、le&Insert(const E&e)hte%m.DistinctInsert(e);return*this;ChainHashTable&Delete(const K&k,E&e)htk%m.Delete(k,e);return*this;void Output()const;/output the table private:int m;/divisor SortedChain*ht;/array of chains;一点改进每个链表尾增加一个关键字为极大值的节点（哨兵）链表搜索程序循环条件：i&(i-datadata k两种hash实现的复杂性比较v元素大小s字节，指针和整型2字节vh

40、ash表m个桶，n个元素v空间复杂性线性探测开地址法：m(s+2)溢出链表法：2m+2n+nsnms/(s+2)时，后者占优v时间复杂性最坏情况都是O(n)溢出链表法时间复杂性v链表长度为i，不成功搜索平均操作次数v平均链表长度n/m=a，代入上式astripe_hashtbl(sect)STRIPE_SHIFT)&HASH_MASK)Hash表磁盘地址Hash函数的设计采用的什么方法？Insert函数/条纹可组织为双向链表struct stripe_head struct stripe_head*hash_next,*hash_pprev;_inline_ void insert_hash(

41、raid5_conf_t*conf,struct stripe_head*sh)struct stripe_head*shp=&stripe_hash(conf,sh-sector);if(sh-hash_next=*shp)!=NULL)(*shp)-hash_pprev=&sh-hash_next;*shp=sh;sh-hash_pprev=shp;解决冲突采用的什么方法？Search函数static struct stripe_head*_find_stripe(raid5_conf_t*conf,sector_t sector)struct stripe_head*sh;for(sh=

42、stripe_hash(conf,sector);sh;sh=sh-hash_next)if(sh-sector=sector)return sh;return NULL;Delete函数static void remove_hash(struct stripe_head*sh)if(sh-hash_pprev)if(sh-hash_next)sh-hash_next-hash_pprev=sh-hash_pprev;*sh-hash_pprev=sh-hash_next;sh-hash_pprev=NULL;Hash的应用：LVMvLVM：Logical Volume Managerv管理大

43、量物理磁盘，组织为“逻辑卷”提供给用户使用vHash的使用每个逻辑卷都有自己的名字，用户使用逻辑卷就是通过这个名字内核为每个逻辑卷维护一个结构对象，逻辑卷的操作依赖此结构问题：给定名字，找到逻辑卷结构Hash函数#define NUM_BUCKETS 64#define MASK_BUCKETS(NUM_BUCKETS-1)static struct list_head _name_bucketsNUM_BUCKETS;static unsigned int hash_str(const char*str)const unsigned int hash_mult=2654435387U;uns

44、igned int h=0;while(*str)h=(h+(unsigned int)*str+)*hash_mult;return h&MASK_BUCKETS;Insert函数static int dm_hash_insert(const char*name,const char*uuid,struct mapped_device*md)struct hash_cell*cell;/新逻辑卷结构分配空间cell=alloc_cell(name,uuid,md);if(!cell)return-ENOMEM;/search，失败方可加入if(_get_name_cell(name)goto

45、 bad;Insert函数/仍是溢出链表法，list_addLinux一套很精巧的链表实现list_add(&cell-name_list,_name_buckets+hash_str(name);return 0;bad:free_cell(cell);return-EBUSY;Search函数static struct hash_cell*_get_name_cell(const char*str)struct hash_cell*hc;unsigned int h=hash_str(str);list_for_each_entry(hc,_name_buckets+h,name_list

46、)if(!strcmp(hc-name,str)return hc;return NULL;Delete函数static void _hash_remove(struct hash_cell*hc)/*remove from the dev hash*/list_del(&hc-uuid_list);list_del(&hc-name_list);free_cell(hc);Rename函数static int dm_hash_rename(const char*old,const char*new)char*new_name,*old_name;struct hash_cell*hc;new

47、_name=kstrdup(new);if(!new_name)return-ENOMEM;hc=_get_name_cell(new);if(hc)kfree(new_name);return-EBUSY;Rename函数hc=_get_name_cell(old);if(!hc)kfree(new_name);return-ENXIO;list_del(&hc-name_list);old_name=hc-name;hc-name=new_name;list_add(&hc-name_list,_name_buckets+hash_str(new_name);kfree(old_name)

48、;return 0;Hash的应用：md5vMessage-Digest Algorithm 5vRonald L.Rivest，90年代初，MD2MD3MD4MD5vhttp:/theory.lcs.mit.edu/rivest/homepage.htmlv文件内容通过Hash函数128bit的“摘要”防止文件被篡改：正确文件计算.md5文件，传输后再算一遍，是否匹配UNIX系统用户密码的保存如何成立？Hash函数值没有冲突！md5算法1.打补丁若需要，在文件内容后添加“10000”，使得文件长度%512bit=448bit2.补长度值将64bit的文件长度补在文件末尾文件表示为word流M

49、0,1,2,N-1N为16的倍数（16个words512bits）md5算法3.md buffer初始化word A:01 23 45 67word B:89 ab cd efword C:fe dc ba 98word D:76 54 32 10md5算法3.摘要的计算4个辅助函数vF(X,Y,Z)=X&Y|not(X)&ZG(X,Y,Z)=X&Z|Y¬(Z)H(X,Y,Z)=X xor Y xor ZI(X,Y,Z)=Y xor(X|not(Z)T164vTi=4294967296*abs(sin(i)的整数部分主循环v文件拆为512bits一组，对每组进行4轮计算v每轮是用一个辅助

50、函数进行16次运算md5算法/*Process each 16-word block.*/For i=0 to N/16-1 do /*Copy block i into X.*/For j=0 to 15 do Set Xj to Mi*16+j.end/*of loop on j*/*Save A as AA,B as BB,C as CC,and D as DD.*/AA=A BB=B CC=C DD=Dmd5算法 /*Round 1.*/*Let abcd k s i denote the operation a=b+(a+F(b,c,d)+Xk+Ti)s).*/*Do the fol