字典和映射map, since 2022-05-07

(2022.05.07 Sat)

Python中的dict字典类型可能是最重要的数据结构之一，其中每个键值key映射到一个关联的值。由key映射到关联值的被称作关联序列(associative array)或映射(maps)。映射的案例包括

• DNS服务器接收到hostname请求后，返回host对应的ip地址
• 数据库中一个学生id对应的学生相关信息
• RGB色彩空间中颜色对应的色值

映射的简单实现

映射的抽象类型，应该有如下方法，注意这些方法也是Python内置的dict类型中存在的：

• M[k]
• M[k] = v
• del M[k]
• len(M)
• iter(M)
• k in M
• M.get(k, d=None)
• M.setdefault(k, d)
• M.pop(k, d=None)
• M.popitem()
• M.clear()
• M.keys()
• M.values()
• M.items()
• M.update(M2)

直觉上，我们可以使用如下方法实现字典/映射的功能：
键k和对应的值v保存为一个k-v pair，保存为tuple类型，即(k, v)。将该键值对推入一个list中。查询和更新时，遍历list，找到符合条件的key，并返回和修改对应的值，或执行其他操作。判断特定的键是否包含在该字典中，则遍历list如果发现有键值对的key是，则返回True。

下面是一个简单实现

from collections import MutableMapping

class MapBase(MutableMapping):
    class _Item:
        __slots__ = '_key', '_value'
        def __init__(self, k, v):
            self._key = k
            self._value = v
        def __eq__(self, other):
            return self._key == other._key
        def __ne__(self, other):
            return not (self == other)
        def __lt__(self, other):
            return self._key < other._key

class UnsortedTableMap(MapBase):
    def __init__(self):
        self._table = []
    def __getitem__(self, k):
        for item in self._table:
            if k == item._key:
                return item.value
        raise KeyError('key not set, ', repr(k))
    def __setitem__(self, k, v):
        for item in self._table:
            if k == item._key:
                item._value = v
                return 
        self._table.append(self._Item(k, v))
    def __delitem__(self, k):
        for ind in range(len(self._table)):
            if k == self._table[ind]._key:
                self._table.pop(ind)
                return 
        raise KeyError('no key existing ', repr(k))
    def __len__(self):
        return len(self._table)
    def __iter__(self):
        for item in self._table:
            yield item._key

调用

>>> pd = UnsortedTableMap()
>>> pd['a']=1
>>> pd._table
[<__main__.MapBase._Item object at 0x10bb4c940>]
>>> pd['b']=999
>>> pd['c'] = 156
>>> len(pd)
3
>>> del pd['b']
>>> len(pd)
2

复杂度分析
考虑到这种实现方式中对字典的查询和修改都要遍历整个list，查询的复杂度都为，效率低下。

Reference

1 Goodrich and etc., Data Structures and Algorithms in Python