Probing with markers

Build the table from the figure in lesson 3: m slots, keys are whole numbers, and a key’s home slot is key % m. If a slot is taken, try the next one, (i + 1) % m. The table never grows.

• contains starts at the home slot and probes until it finds the key (True) or an empty slot (False). It skips 'DEL' markers. It never looks at more than m slots.
• remove finds the key the same way and puts 'DEL' in its slot.
• insert does nothing if the key is already there, and returns its slot. Otherwise it puts the key in the first 'DEL' slot it passed, or else in the empty slot where it stopped, and returns that slot. If it finds neither in m probes, it returns -1.

T = ProbeTable(10)
T.insert(23); T.insert(43); T.insert(13)   # 3, 4, 5
T.remove(43)                               # True
T.slots()
# [None, None, None, 23, 'DEL', 13,
#  None, None, None, None]
T.contains(13)                             # True

The tests make an object and call its methods in order. A test shows the list of calls, and compares the list of everything they returned (methods that return nothing give None).

Limits

• Up to 131,072 slots and 100,000 keys. Keys may be negative.