辞書・線形リスト・2分木を、組み合わせる。Ruby で書くと、

class LRU_hash
def initialize (max_size = 3)
# ary は、hash に追加・アクセスした順
@hash = {}; @ary = []
@max_size = max_size
end

def push (key)
if @hash.has_key? key
# 一旦、要素を削除してから、最後尾に追加しなおす
@ary.delete key
else
if @max_size == @hash.size
# 先頭要素を削除してから、最後尾に追加する
@hash.delete(@ary.shift)
end
@hash[key] = true
end
@ary.push key
end

def print_buf
puts @ary.join ', '
end
end

ary = ["あ", "a", "あ", "い", "b", "あ", "c"]
hash = LRU_hash.new 4
ary.map { |key| hash.push key }
hash.print_buf #=> い, b, あ, c