Updating key that collides with deleted item causes dead items

[ghost]

Say A and B collide at attempt = 0. If we do the following

• insert("A", <value of A>)
• insert("B", <value of B>)
• delete("A")
• insert("B", <new value>)

The second B will be inserted where A used to be, at hash("B", n, 0), and the B at hash("B", n, 1) will become wasted space. Further, if we then call delete("B"), B will just be restored to its original value, rather than actually being deleted.

[Kle0s]

absolutely right.
a simple (but fucking the complexity of the function) solution is to run through the items first, checking if there's an item with the key. if you find one, update the value and end the function call by return. otherwise, continue to adding a new item as shown in the tutorial.

[Lorilandly]

furthermore, when such a hash table is resized, the behavior is undefined.
If the dead B has a larger hash result, it will actually replace the new B in the resized hash table.