11 映射

2018-10-19 约 926 字预计阅读 2 分钟

无处不在的映射

1. 映射

前面我们讲解了基于数组和链表最基础的数据结构。在继续下面的内容之前，我们先来说一说映射。因为映射与我们接下来的很多数据结构与算法相关。映射可以看作是搜索或查找的扩展，后面介绍的很多数据结构都是为实现快速的增删改查。因此在继续其他数据结构的介绍之前，我想先介绍一下映射的抽象数据类型以及它的常见几种实现方式。

1.1 映射的抽象数据类型

抽象基类

Python 中使用抽象基类来表达抽象数据类型。如下所示，抽象基类包含两类方法

一是由 abc.abstractmethod 装饰的抽象方法，这些方法必需由继承自抽象基类的子类来提供具体实现
二是在抽象方法基础上定义的具体方法，基类上的具体方法通过继承可以实现最大化代码复用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


import abc


class ADT(object):
    __metaclass__ = abc.ABCMeta

    @abc.abstractmethod
    def abstract_method(self):
        pass

    def specific_method(self):
        return self.abstract_method()

Python 中映射 map 的 ADT 与 MutableMapping 抽象基类相对应。

映射的抽象方法

映射 M 有如下五个抽象方法，这些方法必需由子类提供具体实现:

M[k]: 返回键 k 对应的值，键不存在则触发异常，对应 Python __getitem__
M[k]=v: 对应 Python __setitem__
del M[k]: 对应 Python __delitem__
len(M): 对应 Python __len__
iter(M): 迭代映射 M 中的所有键，对应 Python __iter__

映射的具体方法

为了方便其他功能实现，映射包含了如下具体方法，子类通过继承 MutableMapping 可以自动获取:

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)
M == M2
M ！= M2

因为这些方法很容易做到见名知意，我就不再一一解释了。

1.2 map 的实现层次

map ADT 有众多的实现方式，为了方便代码重用，我们使用如下层次结构

MutableMapping 是 Python 提供的映射的抽象，提供了现成的映射具体方法
MapBase: 继承自 MutableMapping，为自定义的映射类型提供扩展支持
UnsortedMap: 基于未排序数组的映射实现
HashMapBase: 映射的散列表实现
SortedTableMap: 基于二分查找的映射实现
SkipList: 映射的跳表实现
TreeMap: 二叉搜索树木及其变种的映射实现

2. 实现

本节我们就以最简单的 UnsortedMap 为例，实现一个最简单的映射。更加高级的实现我们会在后面一一讲解。

2.1 MapBase

MapBase 是我们在 MutableMapping 基础上自定义的抽象基类，它提供了一个 _Item 类用于保存键与值的映射关系。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class MapBase(MutableMapping):
    class _Item(object):
        __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

        def __gt__(self, other):
            return self._key > other._key

2.2 UnsortedMap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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 error' + 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 j in range(len(self._table)):
            if k == self._table[j]._key:
                self._table.pop(j)
                return
        raise KeyError('Key error' + repr(k))

    def __len__(self):
        return len(self._table)

    def __iter__(self):
        for item in self._table:
            yield item._key

目录