And here's another interesting algorithm/structure: Randomized Slide to Front

[Richard Hodges via Digitalmars-d]

I had a little think about the pathological case of most searches 
being for one of a few elements.

I'm sure my idea is not new, but it seems to me that keeping a 
'hit count' for each element solves this. The decision of whether 
to swap then becomes:

++ Frequency[I]
if I >= Threshold1 then
   choose an index J that is [either I/2 or rand(0...I-1), 
depending on preference]
   if (Frequency[I] - Frequency[J]) >= Threshold2 then
     swap Item[I] and Item[J]
     swap Frequency[I] and Frequency[J]
     I = J
   endif
endif
return I

I wrote a little test in c++ (sorry guys, old habits die hard):

template<class T>
struct mrucache
{
     using vector_type  = std::vector<T>;
     using iterator = typename vector_type::iterator;
     using const_iterator = typename vector_type::const_iterator;

     void add(T item) {
         _items.push_back(std::move(item));
         _frequency.push_back(0);
     }

     template<class Pred>
     iterator find_if(Pred&& pred)
     {
         using std::begin;
         using std::end;
         auto iter = std::find_if(begin(_items),
                                  end(_items),
                                  std::forward<Pred>(pred));
         if (iter != end(_items))
         {
             auto i = std::distance(_items.begin(), iter);
             ++ _frequency[i];
             i = maybe_swap(i);
             iter = std::next(begin(_items), i);
         }
         return iter;
     }

     std::size_t maybe_swap(std::size_t i)
     {
         if (i >= closeness_threshold)
         {
             auto candidate_i = i / 2;
             if ((_frequency[i] - _frequency[candidate_i]) >= 
difference_threshold) {
                 swap(_items[i], _items[candidate_i]);
                 swap(_frequency[i], _frequency[candidate_i]);
                 i = candidate_i;
             }
         }
         return i;
     }

     auto begin() const { return _items.begin(); }
     auto end() const { return _items.end(); }

     static const size_t closeness_threshold = 4;
     static const int difference_threshold = 1;

     std::vector<T> _items;
     std::vector<int> _frequency;
};