# Implementing key map with expire and size limit

Recently I have been asked to implement a key map with expire time for each key and possibility to limit the number of keys, in Python. I've used a dictionary + heap to store the entries, e.g.:

from datetime import datetime, timedelta
from heapq import heapify, heappop, heappush

class KeyMap:
def __init__(self, maxsize=None):
self.maxsize = maxsize
self.entries = {}
self.entries_heap = []

def set(self, key, value, expiration_time: timedelta):
expires_at = datetime.now() + expiration_time
entry = {'key': key, 'value': value, 'expires_at': expires_at}
self.entries[key] = entry
heappush(self.entries_heap, (expires_at, entry))

if len(self.entries) > self.maxsize:
_, oldest = heappop(self.entries_heap)
del self.entries[oldest['key']]

def get(self, key):
entry = self.entries[key]
if entry['expires_at'] < datetime.now():
del self.entries[key]
raise KeyError(key)
return entry[value]

def delete(self, key):
del self.entries[key]
for i in range(len(self.entries)):
if self.entries_heap[i][1]['key'] == key:
self.entries_heap[i] = self.entries_heap[-1]
self.entries_heap.pop()
heapify(self.entries_heap)


AFAIC, this should give O(log n) time for set(), O(1) for get() and O(n) for delete(). Are there any ways to improve the performance of set() and delete() methods?

• If it were possible to implement set in $O(1)$ then you could use this data structure to sort a list of numbers in $O(n)$ (by turning the numbers into datetime objects and using them as expiration times and then looking at the order they get evicted from the cache). But sorting a list of numbers takes $Ω(n\log n)$. – Gareth Rees Dec 8 '18 at 18:07
• Actually, sorting numbers can be done in O(n) time, check this, for example :) – Eugene Yarmash Dec 10 '18 at 8:41
• I was afraid someone would offer that nitpick. But if you know all about bucket sort then you know why it's actually $Ω(n\log n)$ in the general case. – Gareth Rees Dec 10 '18 at 8:48