《【精品数据结构】Hashing.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】Hashing.ppt（29页珍藏版）》请在三一文库上搜索。
1、Chapter 7,Hashing,7.1 Dictionaries,A dictionary is a collection of elements; each element has a field called key, and no two elements have the same key value. Operations: Insert(x): insert an element with a specified key value x Search(k,x):search an element with a specified key value k, put the ele
2、ment into x Delete(k,x):delete an element with a specified key value k,put the element into x,7.2 Linear List Representation,A dictionary can be maintained as an ordered Linear List(e1,e2,) ei are dictionary elements and their keys are increased from left to right We may define two classes Sorted Li
3、st and Sorted Chain to facilitate this representation,1. SortedList Sequential Search(program 2.1) The array can be ordered or unordered Time complexity: ASLsucc=(1+2+n)/n = (n+1)*n/2)/n=(n+1)/2=O(n),2.Binary Search It is suitable for sorted list example,Example:,1) amid=x, found 2) amidx, x is in t
4、he left half of the array,search again 3) amidx, x is in the right half of the array,search again,Programbinary search Template int SortedList:BinarySearch(const T ,Analysis of binary search time complexity: Best case: compare one time Worst case: no longer than the height of the binary search tree
5、Average compare times:,2. SortedChain class SortedChain (program 7-1) Search ,Delete(program 7-2) Insert (program 7-3),7.3 Hashing,1.Ideal hashing O(1) Another representation of a dictionary is to use hashing Address=hash(key), also called : name-address function,7.4 Hashing,2.example,7.4 Hashing,3.
6、problems Find a proper hash function How to solve a collision Select a suitable loading factor . =n/b, n is number of elements in the hash table, b is the number of buckets in the hash table,7.4 Hashing,4.hashing function,7.4 Hashing,5.how to solve a collision 1)linear open address If hash(k)=d,and
7、the bucket is already occupied ,then we will examine successive buckets d+1, d+2,m-1, 0, 1, 2, d-1, in the array example,7.4 Hashing,Example: a hash table with 11 buckets,the divisor D to use is 11.,7.4 Hashing,Performance analysis the adding sequence is 80,40,65,24,58,35 ASLsucc=(1+1+1+1+2+3)/6=1.5
8、,7.4 Hashing,C+ Implementation 1)Assume that each element to be stored in the hash table is of type E and has a field key of type k. 2)the hash table is implemented using two arrays: ht and empty . 3)emptyi is true iff hti does not have an element in it. It is defined for the deletion operation,7.4
9、Hashing,Program 7.11 C+ class definiition for hash tables template class HashTable public: HashTable(int divisor =11); HashTable()deleteht; delete empty;,7.4 Hashing,bool Search(const K,7.4 Hashing,Program 7.12constructor for hashtable template HashTable:HashTable(int divisor) /Constructor. D=diviso
10、r; /allocate hash table arrays ht=new ED; empty= new boolD;,7.4 Hashing,/set all buckets to empty for(int i=0;iD;i+) emptyi=true; ,7.4 Hashing,Program 7.13search function template int HashTable:hSearch(const K /start at home bucket,7.4 Hashing,do if(emptyj | htj=k) return j; j=(j+1)%D; /next bucket
11、while(j!=i); /returned to home? return j; /table full; ,7.4 Hashing,Template bool HashTable:Search(const K ,7.4 Hashing,Program 7.14insertion into a hash table template HashTable /check if insert is to be done,7.4 Hashing,if(emptyb)emptyb=false; htb=e; return *this; /no insert ,check if duplicate or
12、 full if(htb=k)throw BadInput();/duplicate throw NoMem(); /table full ,7.4 Hashing,2) Hashing with chains,0 0 0,11,33,55,66 0,36,69 0,16,49,82 0,0 1 2,3 4 5,7.4 Hashing,C+ Implementation of chained hash tables template class ChainHashTable public: ChainHashTable(int divisor=11) D=divisor; ht=new SortedChainD; ChainHashTable()delete ht;,7.4 Hashing,bool Search(const K,