Say, a simple LRU cache:

* Inserting into the cache is just normal insertion.

* To delete excessive items, simply iterate to get the first few items' keys, then delete.

* To lookup, simply do a key-based lookup, then delete and re-insert.