Robin Hood - bug when inserting into tombstones #1
Description
Hey there!
I'm trying to implement hash dicts in Elm based on your repo and videos (and the awesome C++Now 2018 talk by Malte).
I've just got round to Robin Hood, and I have a property based test suite set up checking that outwardly my dict behaves exactly the same as the "known to be correct" stdlib Dict.
The test suite has found an issue with your approach to inserting an item into a Tombstone. Consider this scenario:
- Start with empty table (4 buckets)
- Insert "A" (let's say it hashes to bucket index 3) -> will end up in bucket 3 with offset 0
- Insert "B" (hashes to bucket index 3) -> will end up in bucket 0 with offset 1
- Remove "A" -> now bucket 3 is a Tombstone
- Insert "B" -> it sees a tombstone in bucket 3, and gets inserted there
- Convert to list -> you get two Bs instead of just one!
That's because after step 5 the array looks like:
| idx | offset | key |
|---|---|---|
| 0 | 1 | "B" |
| 1 | -1 | Empty |
| 2 | -1 | Empty |
| 3 | 0 | "B" |
instead of
| idx | offset | key |
|---|---|---|
| 0 | 1 | "B" |
| 1 | -1 | Empty |
| 2 | -1 | Empty |
| 3 | 0 | Tombstone |
On the other hand, if in step 5 you continued to the next index after seeing a tombstone, you'd find the B in bucket 0 and would replace its value / end there.