Optimize a cache

[Florian Lindner]

Hello,
I am building a object cache in python, The cache has a maximum size and the
items have expiration dates.
At the moment I'm doing like that:

cache = {} # create dictionary

cache[ID] = (object, timestamp) # Save a tuple with the object itself and a
timestamp (from datetime.datetime.now()) under a unique object ID. This
make looking up a certain item a cheap operation (AFAIK). After looking up
my program checks if the expiration date and returns cache[ID][1] or
retrieve a new object and overwrite the one saved in the cache.

My problem now:
When len(cache) > cacheSize I need to remove the oldest objects (the ones
with the smalest timestamp). For that I need to iterate through all items
and get the oldest one: (pseudo code)

oldest = datetime.datetime.now()

for i in cache:
        if i[1] < a:
                id = i
                n = i[0]

del cache[id]


What possible you see to optimize this lookup? Or anything else you see to
make it better?

Thanks,

Florian