Define the following terms: hash table hash function perfect hash function What

Question

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.

Explanation / Answer

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.

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:

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.