My favourite simple "eviction" algorithm is just to wipe out the entire cache as soon as it gets full.

Insertion:

    %hash = () if keys %hash > 100000;
    $hash{$key} = $val;

Retrieval:

    return $hash{$key};

Desirable properties include bounded memory usage (assuming bounded size of $val), O(1) (amortised) insertion/retrieval, and (most importantly) it only takes a second to write and there's almost 0 chance of writing it wrong.

The downside is that the mean utilisation is only 50%.