Is there a data structure that behaves like a "buffer dictionary"?

Question

I need a data structure that behaves mostly like a dictionary (can access/remove any element by key), but also has the following properties:

• Can hold a maximum of N elements (in practice, N is in hundreds, thousands).
• The structure contains the last operation number that's incremented on each access (get/set/delete).
• The elements have their last access tracked - whenever an item is added or accessed, the operation number is saved alongside that item in the structure.
• If a new item is to be added and the structure holds the maximum amount of elements, the element with the lowest operation number (last accessed a long time ago, before all the other elements' last accesses) is removed and the new element is inserted instead.

I use such a structure to maintain a cache of objects - retrieving each element is very time-consuming and a limited amount of elements is accessed very frequently. If the element is no longer used all that often, it'll eventually land on the bottom of this cache, to be replaced on the next insert into this structure.

My current implementation (in Python 3) is a dictionary holding keys -> tuple of the last access number and the object itself. It works well, but I'm almost sure I've seen a very similar structure somewhere - is there anything that behaves like such a cache?

Answer 1

As far as I know there are no native data structures that behaves as this kind of "cache".

CircularDict meets your first requirement (set a maximum number of elements or memory that it can store), and partially the last one (when a new element is added, if full, will delete the oldest inserted element). But it is based on the order of your put and set operations. Currently, it does not take into account gets

from circular_dict import CircularDict

# Initialize a CircularDict with a maximum length of 3
my_cache = CircularDict(maxlen=3)

# Fill it with 4 items (one more than maxlen)
my_cache['1'] = 'value1'
my_cache['2'] = 'value2'
my_cache['3'] = 'value3'
my_cache['4'] = 'value4'

print(circ_dict)

Output will look like:

{'2': 'value2', '3': 'value3', '4': 'value4'}