Example of LRU Cache in Python3 using OrderedDict.

lru_cache.py

from collections import OrderedDict


class LRUCache(object):
    def __init__(self, max_size=4):
        if max_size <= 0:
            raise ValueError

        self.max_size = max_size
        self._items = OrderedDict()

    def _move_latest(self, key):
        # Order is in descending priority, i.e. first element
        # is latest.
        self._items.move_to_end(key, last=False)

    def __getitem__(self, key, default=None):
        if key not in self._items:
            return default

        value = self._items[key]
        self._move_latest(key)
        return value

    def __setitem__(self, key, value):
        if len(self._items) >= self.max_size:
            keys = list(self._items.keys())
            key_to_evict = keys[-1]
            self._items.pop(key_to_evict)

        self._items[key] = value
        self._move_latest(key)


class TestLRUCache(object):
    def test_init(self):
        n = 10
        lru = LRUCache(max_size=n)
        assert lru.max_size == n
        assert hasattr(lru, "_items")

    def test_set(self):
        lru = LRUCache()
        lru["a"] = 1
        assert lru._items["a"] == 1

    def test_evict_over_limit(self):
        n = 2
        lru = LRUCache(max_size=n)
        lru["a"] = 1
        lru["b"] = 2
        lru["c"] = 3

        assert len(lru._items) == n

    def test_set_moves_to_top(self):
        lru = LRUCache(max_size=2)
        lru["a"] = 1
        lru["b"] = 2

        assert list(lru._items.keys()) == ["b", "a"]

        lru["a"] = 1
        assert list(lru._items.keys()) == ["a", "b"]

    def test_get(self):
        value = 1
        lru = LRUCache()
        lru["a"] = value
        assert lru["a"] == value

    def test_get_moves_to_top(self):
        lru = LRUCache()
        lru["a"] = 1
        lru["b"] = 2

        assert list(lru._items.keys()) == ["b", "a"]

        lru["a"]
        assert list(lru._items.keys()) == ["a", "b"]


tester = TestLRUCache()
for method in dir(tester):
    if not method.startswith("test"):
        continue
    getattr(test, method)()