Question

Need help on problems 3 and 4 only thanks in advance.

Define the following terms: hash table hash function perfect hash function What is a collision? Explain three ways of handling collisions (a program is not needed; a clear brief explanation suffices). Consider a hashing scheme that uses linear probing to resolve collisions. Design an algorithm (no code necessary) to delete an item from the hash table. What precautions do you need to take to make it work properly? Given the following data: 25 - 42 - 96 - 101 - 102 - 162 - 197 Construct a hash table using the hash function, h (key)= key mod tablesize, where size of the table is 11. Use the rehash function, rh (key + 3) mod tablesize to resolve collisions. Construct a second hash table using the same hash function as above, but chaining to resolve collisions.

Answer 1

Question 3:

a) The linear probing is a method to resolve collisions in hash tables. The probe is calculated using the hash function.

Summary of the deletion algorithm is below. Note that it is very similar to that of the retrieve -- this is because the data must be found before it can be deleted.

• Calculate the hash code for the given target key
• Access the hash element
• If the hash element is empty, the deletion has immediately failed.
• Otherwise, check for a match between the target and data key
  • If there is a match, delete the hash element (and set the flag)
  • If there is no match, probe the table until either:
    • An match is found between the target key and the data's key; the data can be deleted, and the deleted flag set.
    • A completely empty hash element is found

b) The basic deletion operation is merely a retrieval followed by data removal (clearing the hash element, once the target has been found.)

Unfortunately, this has a negative side-effect on the way the retrieval works. Since the data retrieval operation relies on blank hash elements as the signal to stop probing, there is the possibility that a deletion operation will render some data items unfindable. Consider where a search for 'R' (which has the same hash code as 'A') is attempted, after 'D' has been deleted:

The data 'R' will never be found, as the probing had terminated too early; this is due to the hash element that stored 'D' (and kept the probing going) being deleted.

The solution to this problem is to define two different kinds of blank hash elements:

• a purely empty element, which has never stored data; and
• an "empty but deleted" element, which stored data that has since been deleted.