Implementing a cache

[Ola Fosheim Grøstad via Digitalmars-d-learn]

On Saturday, 2 July 2016 at 12:10:28 UTC, qznc wrote:
> With AA cache eviction is inefficient. It requires to sort the 
> keys of the AA with respect to a field in the value. Stack

No, you just need the hash of the key in the object for many 
types of hash-tables. There are many solutions, but here are some 
for Least Recently Used (LRU) schemes:

1. The simplest efficient solution is to use a hash + an embedded 
double-linked list and an intrusive reference counter.

When the refcount > 0 you unlink the object.
When the refcount == 0 you put the object at the tail of the list.
When you need memory you deallocate the head of the list.

2. Use a hash + partially time-sorted queue for objects that are 
not in use, and do a partial quick-sort to find LRU lazily (when 
you need to evict).

Not using a hash for lookup seems silly, unless the ID can be 
efficiently used for a trie like search tree. This might work out 
ok for URLs.