| Hashing Review Part 1 |
| The following review questions were covered in Labs 02 and 03 and are questions taken from the course website. NOT ALL questions from the course website were discussed in lab. Please note that the information presented here does not necessarily represent a complete answer to the review question. The information is intended to spark student's memory for those who attended lab OR provide a base (hint) from where to start for those students who did not attend lab.
| Question 1: Insert the given keys into the table provided in TWO different ways: 1) Using Synonym Chaing 2) Using Coalesced Hashing Compare your results in terms of amount of work to load the tables as well as the average chain lengths. What are your conclusions? RECORD KEYS: 14,23,15,48,36,25,16,35,58,24,13 HASH FUNCTION: hash(key) = key mod 11 Assume an increment step size of 1 |
| note: this image has been updated on Dec 9 |
| Question 2: Insert the given keys into the table provided using computed chaining. RECORD KEYS: 27,18,29,28,39,13,16,38,53 HASH FUNCTION: hash(key) = key mod 11 INCREMENT FUNCTION: increment(key) = Quotient(Key/11) mod 11 |
| Question 3: What does the term cellar refer to when applied to hash tables? |
|  | Seperate overflow area in a 2-pass load. |
| Question 4: In a hashed file that uses Synonum Chaining to resolve conflicts, how do you solve the problem of always having to be alble to find a key by starting at its home address? How does it solve the problem? |
|  | Use a 2-pass load, this way unique home addresses are loaded first. |

BACK

© Copyright 2002
Questions? Please Email: gwen@cpsc.ucalgary.ca
Last modified December 9, 2002