Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 278-281 (Section 7.5), pages 283-284 (Section 7.6)

(2nd) pages 365-368 (Section 8.6), pages 341-342 (Section 8.3)

Additional material

Order
IntegerOrder
SkipListNode
SkipListDictionary

Question

Consider the following implementation of a dictionary. Assume that the keys are 0, ..., K.

Variables

hash-table: array of sequences of elements
invariant: hash-table[k] contains the elements of the items in the dictionary with key k.

Initialization

for k 0, ..., K do
    hash-table[k] empty sequence

Algorithms

Give the algorithms for findElement, insertItem and removeElement.