Database Systems: The Complete Book (2nd Edition), by Hector Garcia-Molina Jeffrey D. Ullman Jennifer Widom Department of Computer Science Stanford University

Exercise 14.3.3: The material of this section assumes that search keys are unique. However, only small modifications are needed to allow the techniques to work for search keys with duplicates. Describe the necessary changes to insertion, deletion, and lookup algorithms, and suggest the major problems that arise when there are duplicates in each of the following kinds of hash tables: (a) simple (b) linear (c) extensible.