Updating One Structure but Not Its Partner

A combined structure is correct only while its two parts agree, and the commonest bug is an operation that changes one part and forgets the other. This card covers the two forms that bug takes, in an LRU cache and in a set built from an array and a map of indexes, why neither fails on the operation that causes it, and how to make the update impossible to forget.

The set keeps its items in an array and each item's index in a hash map. To delete an item, it moves the last item into the gap and removes the last slot, so the moved item has a new index and the map must be told. The faulty version below forgets that one line. The run inserts 10, 20, 30 and 40, then deletes 20, inserts 50 and deletes 40.

array: [10, 40, 30]
map:   {10: 0, 30: 2, 40: 3}

array: [10, 40, 30, 50]
map:   {10: 0, 30: 2, 40: 3, 50: 3}

array: [10, 40, 30]
map:   {10: 0, 30: 2, 50: 3}

With the one line restored, the same run ended with the array [10, 50, 30] and the map {10: 0, 30: 2, 50: 1}: 40 gone, 50 present in both.

The LRU form is the mirror image. An eviction that removes the oldest key from the order but not from the map left a cache of capacity 2, after put(a), put(b) and put(c), with order b, c and map keys a, b, c. The next get(a) returned 1, a value the cache had evicted, and put a back in the order, which then held 3 keys.

In both forms the faulty operation reports success, and the failure surfaces one or more operations later, far from its cause. The fix is structural: give each change one method that updates both parts, such as a single _unlink that every removal goes through, and never touch either part from anywhere else. A check that the map and the other structure hold the same items, run after each operation in tests, catches the slip on the line that makes it.