复习下学期华侨学院data structures ch

1、 Data Structures and Algorithm Analysis in CCS222HashingMotivating ExampleSuppose we want to store a list whose elements are integers between 1 and 5:Define an array of size 5, and if the list has element j, then j is stored in Aj-1, otherwise Aj-1 contains 0.Complexity of find operation is O(1), bu

2、t the example is too simplistic to be relevant to most situations.Hash tableThe objective of a hash table is to find an element optimizing for average case search time, not worst case.Supposing we know the elements belong to 1,2U.If we are allowed an overall space of U, then this can be done as desc

3、ribed before.But U can be very large (think how many train tickets are sold each day, but we want to be able to access each tickets information in a reasonable amount of time).Space for storage is called a “hash table” (H).Section 5.1, WeissAssume that the hash table has size MThere must be a hash f

4、unction which maps an element to a value p in 0,.M-1, and the element is placed in position p in the hash table. The function is called hj, (the hash value for j is hj)If hj = k, then the element is added to Hk.Suppose we want a list of integers, then an example hash function is hj = j modulo M.Pseu

5、do-Random Functions Consider a simplistic hash function such as M = 5List contains 1 , 3, 9, 81398 Uh oh! We have a collision!Entry 01234Hash tableWhat happens if the desired elements are not numbers, (e.g., names)?Then we use a function to convert each element to an integer and hash the integer.If

6、we want to store string, such as “abc”Represent each symbol by the ASCII code, choose a number r to modify it, then calculate the integer value ASCII(a)r2 + ASCII(b)r + ASCII ( c )What about non-numerics?ImplementationHash tables are arrays.The size of a hash table is normally a prime number.Two dif

7、ferent elements may hash to the same value (collision).Hashing needs collision resolution.Hash functions are chosen so that the hash values are spread over 0,.M-1, and there are only few collisions.Separate ChainingStore all the elements mapped to the same position in a linked list.Hk is the list of

8、 all elements mapped to k.To find an element j, compute h(j). Let h(j) = k. Then search in bucket list HkTo insert an element j, compute h(j). Let h(j) = k. Then insert in bucket list HkTo delete an element, delete from the bucket list.1398 Entry 01234Insertion is O(1) (for bucket depth of 1).Worst

9、case searching complexity depends on the maximum length of a list Hp. O(q) if q is the maximum length.We are interested in average search time, not worst case.A) Search for 7, look in position 2 in the array, find it empty, conclude 7 is not thereB) Search for 13, look in position 3 in the array, se

10、arch the bucket list, 13 not found, conclude that 13 is not thereC) Insert 4, add it in the bucket list starting with 9Some ExamplesLoad factor is the average size of a list. = number of elements in the hash table/ number of positions in the hash table(M)Average find complexity is 1 + We want to be

11、approximately 1To reduce worst case complexity we choose hash functions which distribute the elements evenly in the list.Ideal Search ComplexityOpen AddressingSeparate chaining requires manipulation of pointers and dynamic memory allocation which are expensive.Open addressing is an alternate scheme.

12、Want to insert key (element) j Compute h(j) = kIf Hk is empty store in Hk, otherwise try Hk+1, Hk+2, etc. (increment in modulo size)Linear ProbingEvery position in hash table contains one element each.Can always insert a key as long as the table is not fullFinding may be difficult if the table is cl

13、ose to full. To maintain performance could require memory allocation many times in excess actual data to be stored.M = 5List contains 1 , 3, 9, 81398 Entry 01234Linear ProbingThe idea is to declare a hash table large enough so that it is never full.Initially, all slots are empty.Elements are inserte

14、d as described.When an element is deleted, the space is marked deleted (empty and deleted are different).During the find operation, one looks for element k starting from where it should be (Hh(k), till the element is found, or an empty slot is found.In the latter case, we conclude that the element i

15、s not in the list.Memory is CheapLooking for 13, Start from the position which has 3, then look at that with 9, then that with 8, next with 1, reach an empty slot, conclude not there Looking for 8, start from the position which has 3, then look at that with 9, then that with 8, conclude foundM = 5Li

16、st contains 1 , 3, 9, 81398 Entry 01234When It WorksIs there any problem if empty and deleted are not distinguished? Yes, may conclude that element not present even if it isDelete 9 for some reasonSearch for 8, start from the position with 3, go to next slot, finds nothing, conclude empty and thus 8

17、 is not there!M = 5List contains 1 , 3, 9, 81398 Entry 01234When It DoesntXThus a separate mechanism for differentiating between empty and deleted is required (lazy deletion, of a sorts).1) When we insert an element k, then start from Hh(k) and move till an empty or deleted slot can be found. 2) An

18、element can be inserted as long as the hash-table is not full.3) If hash values are clustered, then even if hash table is relatively empty, finding may be difficult.Linear Probing, SummarizedQuadratic ProbingAn alternative to linear probing.To insert key k, try slot h(k). If the slot is full try slot h(k) + 1, then h(k) + 4, then h(k) + 9 and so on.Advantage?Are we guaranteed to be able to insert as long as the hash table is not full? Clustering should be reduced.M = 3, first two positions full, let h(k) = 0, h(k) + n2 m