Python面试题系列之19: 实现一键多值的字典

Question

怎样实现一个键对应多个值的字典？

知识点详解

字典都是由一组组键值对构成，一个键对应一个单值的映射。而这里要求一个键映射多个值，实际上就需要将键所对应的多个值放到一个另外的容器中，如可以采用列表、集合来存储它们。

至于选用列表还是集合，这取决于你的实际需求，比如是否需要对值进行去重。一个键对应多个值，最终可以构造出像这样子的字典：

dic1 = {
    'a' : [1, 2, 3],
    'b' : [4, 5]
}

dic2 = {
    'a' : {1, 2, 3},
    'b' : {4, 5}
}

一种很常见的实现方式如下：

d = {}
for key, value in k_v:
    if key not in d:
        d[key] = []
    d[key].append(value)

但这种方式的实现，不得不添加一个初始值（上述代码中的空列表[]），因为每次调用都得创建一个新的初始值的实例，否则会抛出KeyError。

为了解决这个初始化问题，我们可以使用defaultdict，先来看看官方给出的定义。

dict subclass that calls a factory function to supply missing values.
defaultdict属于内建函数dict的一个子类，调用工厂函数提供缺失的值。

这里出现了另一个名词，工厂函数。它指的是能够产生类实例的内建函数，这一类的内建函数都是类对象，当调用它们时，实际上是创建了一个类实例。如int()、bool()、dict()、set()、list()、tuple()等都是工厂函数。

关于 defaultdict ，我们还可以通过一段官方的说明来进一步了解它。

class collections.defaultdict([default_factory[, …]])

Returns a new dictionary-like object. defaultdict is a subclass of the built-in dict class. It overrides one method and adds one writable instance variable. The remaining functionality is the same as for the dictclass and is not documented here.

The first argument provides the initial value for the default_factory attribute; it defaults to None. All remaining arguments are treated the same as if they were passed to the dict constructor, including keyword arguments.

defaultdict objects support the following method in addition to the standard dict operations:
missing(key)
If the default_factory attribute is None, this raises a KeyError exception with the key as argument.
If default_factory is not None, it is called without arguments to provide a default value for the given key, this value is inserted in the dictionary for the key, and returned.
If calling default_factory raises an exception this exception is propagated unchanged.
This method is called by the getitem() method of the dict class when the requested key is not found; whatever it returns or raises is then returned or raised by getitem().
Note that missing() is not called for any operations besides getitem(). This means that get() will, like normal dictionaries, return None as a default rather than using default_factory.

defaultdict objects support the following instance variable:
default_factory
This attribute is used by the missing() method; it is initialized from the first argument to the constructor, if present, or to None, if absent.

总结一下，在官方说明中，首先告诉我们collections.defaultdict会返回一个类似dictionary的对象，这里注意是类似，不是完全一样的对象。defaultdict是内置dict类的子类，除了支持dict的操作，它重载了__missing__(key)方法作为扩展。此外defaultdict添加了一个可写的实例变量default_factory，这个属性被__missing__()方法使用，它从构造函数的第一个参数（如果存在）初始化，如果不存在则初始化为None。

defaultdict类的初始化函数，接受一个类型(本质上是工厂函数)作为参数，当所访问的键不存在的时候，可以实例化一个值作为默认值。

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> print(d)
defaultdict(<class 'list'>, {})
>>> d['a']
[]
>>> d['a'].append('1')
>>> d['a'].append('2')
>>> print(d)
defaultdict(<class 'list'>, {'a': ['1', '2']})

defaultdict类除了接受类型名称作为初始化函数的参数之外，还可以使用任何不带参数的可调用函数，到时该函数的返回结果作为默认值，这样使得默认值的取值更加灵活。

>>> from collections import defaultdict
>>> def zero():
...     return 0
...
>>> d = defaultdict(zero)
>>> print(d)
defaultdict(<function zero at 0x00000153CF166A60>, {})
>>> d['zz']
0
>>> print(d)
defaultdict(<function zero at 0x00000153CF166A60>, {'zz': 0})

所以针对本题目的需求，换成defaultdict的写法，代码如下。

d = defaultdict(list)
for key, value in k_v:
    d[key].append(value)

这里已不再需要执行初始化操作了，而只需要关注添加元素本身的操作即可。有没有觉得代码更加简洁，更加pythonic了！

Answer

使用原生dict实现的话，需要对值进行初始化的操作，示例如下：

d = {}
for key, value in k_v:
    if key not in d:
        d[key] = []
    d[key].append(value)

如果使用defaultdict的话代码就会加简洁：

d = defaultdict(list)
for key, value in k_v:
    d[key].append(value)

后记

要实现字典中的键映射多个值，这并不难。这里之所以引入defaultdict，其目的是利用了它会自动初始化每个key对应的值的这一特性，这样我们只需要关注添加元素本身的操作即可。而Python原生的数据结构dict，用d[key]这样的方式访问，当指定的key不存在时，是会抛出 KeyError异常的。好了，以上就是本篇全部内容。

备注：本篇首发于知识星球「人人都是Pythonista」。