CSE 326, Spring 1998: Homework 6

Due 5/15/98

1. (15 points) Consider the problem of lazy deletion in closed hashing with linear probing. Assume we have an on going process of insertions, deletions, and finds. Design four algorithms where each algorithm is briefly described in pseudocode. Assume the keys are non-negative integers which are hashed into a table T of size HSize. An empty table entry can be indicated using -2. Use -1 in a location to indicate that the entry formerly there has been deleted.
   • "Find(x)" which returns the index of where x is stored if it is in the table and -1 otherwise.
   • "Insert(x)" which inserts x into the table with the precondition that x is not currently in the table. Naturally, a location with a -1 in it can be used to place a newly inserted item.
   • "Delete(x)" which removes x from the table using lazy deletion.
   • "Rehash(T)" which returns a new table of the same size HSize which contains all the items of the old table, but has no items marked as deleted.