Combining Example: A Set That Picks a Random Item in O(1)

An array allows a random index, and a map from item to index allows O(1) deletion.

A set that must insert, delete and pick a random item, all in O(1), is a second combination of two structures, with the roles arranged differently from a cache. This card covers how an array and a hash map from item to index share the work, and the one move that lets deletion stay O(1): fill the gap with the last item.

A hash set inserts and deletes in O(1) on average but cannot pick a random item without walking its contents, because its items have no positions to choose between. An array picks a random item in O(1), by choosing a random index, but deleting from the middle shifts every later item, O(n), and finding the item first is a search. So the items live in an array, and a hash map records where each one is. The steps follow inserts of 10, 20, 30 and 40, then a delete of 20, as a run printed them.

Inserting four items into the combined set and deleting one from the middle

Insert 10, 20, 30 and 40: append, and record the index

Each insert checks the map for the item, appends it to the array and records its index in the map. Both are O(1).

text

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

Delete 20: find its index, then fill the gap with the last item

The map says 20 is at index 1. Instead of shifting 30 and 40 left, the delete removes the last item, 40, from the end of the array and writes it into index 1. It then sets 40's entry in the map to 1 and deletes 20's entry. Order in the array is lost, which a set never promised.

text

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

A random pick chooses an index from 0 to 2 and returns the item there. Over 6,000 seeded picks, the run chose 10 2,025 times, 30 1,925 times and 40 2,050 times: about a third each, with no gap to land on.

The two combinations differ in which structure holds the items. In this one the array holds them and the map holds positions; in an LRU cache the list holds them and the map holds references. In both, the map is the index into the other structure, and it must change whenever an item moves.

Data Structures

← → move through sections and cards