如何限制字典的大小？

Question

我想在Python中使用字典，但希望限制它里面的键值对数量为X。换句话说，如果字典现在已经存储了X个键值对，当我再插入一个新的键值对时，我希望能把其中一个已有的键值对删除掉。如果能删除最近最少使用的那个键值对就更好了，不过这不是必须的。

如果标准库里已经有这样的功能，请告诉我，这样我就省时间了！

Answer 1

这里有一个简单的，不使用LRU（最近最少使用）算法的Python 2.6+解决方案（在旧版本的Python中，你可以用UserDict.DictMixin做类似的事情，但在2.6及以后的版本中不推荐这样做，使用collections里的抽象基类会更好）:

import collections

class MyDict(collections.MutableMapping):
    def __init__(self, maxlen, *a, **k):
        self.maxlen = maxlen
        self.d = dict(*a, **k)
        while len(self) > maxlen:
            self.popitem()
    def __iter__(self):
        return iter(self.d)
    def __len__(self):
        return len(self.d)
    def __getitem__(self, k):
        return self.d[k]
    def __delitem__(self, k):
        del self.d[k]
    def __setitem__(self, k, v):
        if k not in self and len(self) == self.maxlen:
            self.popitem()
        self.d[k] = v

d = MyDict(5)
for i in range(10):
    d[i] = i
    print(sorted(d))

正如其他回答提到的，你可能不想去继承字典（dict）这个类——虽然明确地使用self.d有点繁琐，但这样做可以确保每个其他的方法都能正确地由collections.MutableMapping提供。

Answer 2

cachetools 是一个很不错的工具，它可以帮你实现一种叫做映射哈希的功能，这个工具在 Python 2 和 3 中都能用。

以下是文档中的一段摘录：

在这个模块中，缓存是一个可以改变的、最大大小固定的映射。当缓存满了，也就是说如果再添加一个新项目就会超过这个最大大小时，缓存需要根据合适的缓存算法来决定哪些项目要被丢弃。

Answer 3

Python 2.7 和 3.1 版本有一个叫做 OrderedDict 的东西，早期的 Python 版本也有纯 Python 的实现。

from collections import OrderedDict

class LimitedSizeDict(OrderedDict):
    def __init__(self, *args, **kwds):
        self.size_limit = kwds.pop("size_limit", None)
        OrderedDict.__init__(self, *args, **kwds)
        self._check_size_limit()

    def __setitem__(self, key, value):
        OrderedDict.__setitem__(self, key, value)
        self._check_size_limit()

    def _check_size_limit(self):
        if self.size_limit is not None:
            while len(self) > self.size_limit:
                self.popitem(last=False)

你还需要重写其他可以插入项目的方法，比如 update。使用 OrderedDict 的主要目的是让你可以轻松控制哪些项目被移除，否则普通的 dict 就可以满足需求了。