Part 07 Skip List and Hashing-FL

简介

---

(

&

)

简介

Skip List and Hashing

Concept& Implementation of Dictionary– Skip list, Hashing

Application of Hashing– LZW compression (Learn by yourself)

Part VII Dictionary

简介

Dictionary A dictionary is a collection of elements Each element has a field called keyThe general three skills for Every key is usually distinct DSA– most Typical dictionary operations are: S(earch) I(nsert).D(elete).– Determine whether or not the dictionary is empty– Determine the dictionary size (i.e.,# of pairs)– Insert a pair into the dictionary– Search the pair with a specified key– Delete the pair with a specified keyPPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.pptPart VII Dictionary 3

– (key, value)

简介

Accessing Dictionary Elements Random Access– Any element in the dictionary can be retrieved by simply performing a search on its key

Sequential Access– Elements are retrieved one by one in ascending order of the key field– Sequential Access Operations: Begin– retrieves the element with smallest key Next– retrieves the next elementPPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.pptPart VII Dictionary 4

简介

Dictionary with Duplicates Keys are not required to be distinct Word dictionary is such an example– Pairs are of the form (word, meaning)– May have two or more entries for the same word– For example, the meanings of the word, rank: (rank, a relative position in a society) (rank, an official position or grade) (rank, to give a particular order or position to) PPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.ppt etc. Part VII Dictionary 5

简介

Application of Dictionary Collection of student records in a class– (key, value)= (student-number, a list of assignment and exam marks)– All keys are distinct

Get the element whose key is Tiger Woods Update the element whose key is Seri Pak Exercise: Give other real-world applications of dictionaries and/or dictionaries with duplicatesPPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.pptPart VII Dictionary 6

简介

ADT 7.1 for the abstract data type Dictionary

Part VII Dictionary

简介

Skip List and Hashing

Concept& Implementation of Dictionary– Skip list, Hashing

Application of Hashing– LZW compression (Learn by yourself)

Part VII Dictionary

简介

Skip list The search operation on a sorted array using the binary search method takes O(logn) The search operation on a sorted chain takes O(n) How can we improve the search performance of a sorted chain? By putting additional pointers in some of the chain nodes

Chains augmented with additional forward pointers are called skip listsPPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.pptPart VII Dictionary 9

简介

Skip Lists Skip lists improve the performance of insert and delete operations Employ a randomization technique to determine where and

how many to put additional forward pointers The expected performance of search and delete operations on skip lists is O(logn) However, the worst-case performance is (n)PPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.pptPart VII Dictionary 10

简介

Dictionary as a Skip List Read Example 7.3 and see Figure 7.1 for– A sorted chain with head and tail nodes– Adding forward pointers– Search and insert operations in skip lists

For general n, the level 0 chain includes all elements Level 1 chain includes every second element Level 2 chain includes every fourth element Level i chain includes 2ith element An element is a level i element iff it is in the chains for levels 0 through iPPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.pptPart VII Dictionary 11

简介

Skip List– pointer levels

level 0 chain PPTs from others\dpnm.postech.ac.kr_cs233_lecture\lecture7.ppt includes all elements Level 1 chain includes every second element

Level 2 chain includes every fourth elementPart VII Dictionary 12

简介

Skip List– search“77”

We have learned that the average comparison number is“?” when searching some element in the chain. - Yes, it is (n+1)/2=[(n/20)+1]/2, namely O(n) As for“77” here, we have to compare all the elements!

Part VII Dictionary

简介

Skip List– search

When searching some element in the level 1 skip list, we can conclude the average comparison number is[(n/21)+1]/2+(21+1)/2

As for“77” here, we have to compare 4 elements!Part VII Dictionary 14

简介

Skip List– search

When searching some element in the level 2 skip list, we can conclude the average comparison number is[(n/22)+1]/2+(n/23+1)/2+(21+1)/2

As for“77” here, we have to compare 3 elements!Part VII Dictionary 15

简介

Skip List– search Conclusion– When searching some element in the level i Based on the skip list, we can conclude the average knowledge of comparison number is in skip list, searching[(n/2i)+1]/2+(/n2i+1+1)/2+(/n2i+2+1)/2+…+ we can see that it is a 1+1)/2+(2 kind of simulation of– Asymptotic O(logn)

Binary Search!

Part VII Dictionary