Combining Data Structures

Combining data structures means keeping the same items in two structures at once, so that each covers the operation the other is slow at. It matters because many programs need a set of operations no single structure makes cheap, such as a cache that finds a key, tracks the order of use and evicts the oldest, all in constant time. The topic starts with the LRU cache, built from a hash map and a doubly linked list, and traces it through a sequence of gets and puts. It implements the cache in three languages alongside each language's built-in shortcut, then builds a second combination, an array and a map of indexes that picks a random item in O(1). It ends with the bug both combinations invite: changing one structure and forgetting its partner.