(2022.05.12 Thur)
前面介绍的映射允许用户在查询过程中通过精确检索找到key k的关联值。本节我们考虑另一种情况，即映射表中对应的key都是按顺序排列的。比如金融交易系统中的数据按timestamp排序，其中的timestamp作为映射的key。

有序映射sorted map中的key按升/降序排列，其属性和内置方法实现的功能与一般映射相同。

本文介绍有序映射的两种实现方式，分别基于数组和基于链表。

基于数组的有序映射

顾名思义，基于数组的有序映射其实现方式为数组array。这种方式实现的有序映射称为sorted search table。如下面的一个数组所示，为方便演示，数组中的元素只用元素的key k，代替该元素的(k, v) pair。该数组的index范围[0, 5]，对应的元素的key为从小到大排序。

Python实现

该实现代码中，查找某key是否在映射中如果不存在则返回比该key大的最小元素。

class SortedSearchMap(MapBase):
    def _find_index(self, k, low, high):
        if high < low:
            return high + 1
        else:
            mid = (low + high) // 2
            if k == self._table[mid]._key:
                return mid
            elif k < self._table[mid]._key:
                return self._find_index(k, low, mid-1)
            else:
                return self._find_index(k, mid+1, high)
    def __init__(self):
        self._table = []
    def __len__(self):
        return len(self._table)
    def __getitem__(self, k):
        j = self._find_index(k, 0, len(self._table)- 1)
        if j == len(self._table) or self._table[j]._key != k:
            raise KeyError('Key Error: '+ repr(k))
        return self._table[j]._value
    def __setitem__(self, k, v):
        j = self._find_index(k, 0, len(self._table) − 1)
        if j < len(self. table) and self. table[j]._key == k:
            self._table[j]._value = v # reassign value
        else:
            self._table.insert(j, self._Item(k,v))
    def __delitem__(self, k):
        """Remove item associated with key k (raise KeyError if not found)."""
        j = self._find_index(k, 0, len(self. table) − 1)
        if j == len(self._table) or self._table[j]._key != k:
            raise KeyError('Key Error: '+ repr(k))
        self._table.pop(j) # delete item
    def __iter__(self):
        """Generate keys of the map ordered from minimum to maximum."""
        for item in self._table:
            yield item._key
    def __reversed__(self):
        """Generate keys of the map ordered from maximum to minimum."""
        for item in reversed(self._table):
            yield item._key
    def find_min(self):
        """Return (key,value) pair with minimum key (or None if empty)."""
        if len(self._table) > 0:
            return (self._table[0]._key, self._table[0]._value)
        else:
            return None
    def find_max(self):
        """Return (key,value) pair with maximum key (or None if empty)."""
        if len(self._table) > 0:
            return (self._table[−1]._key, self._table[−1]._value)
        else:
            return None

    def find_ge(self, k):
        '''Return (key,value) pair with least key greater than or equal to k.'''
        j = self._find_index(k, 0, len(self._table) − 1) # j s key >= k
        if j < len(self._table):
            return (self._table[j]._key, self._table[j]._value)
        else:
            return None
    def find_lt(self, k):
        '''Return (key,value) pair with greatest key strictly less than k.'''
        j = self._find_index(k, 0, len(self._table) − 1) # j s key >= k
        if j > 0:
            return (self._table[j−1]._key, self._table[j−1]._value) # Note use of j-1
        else:
            return None
    def find_gt(self, k):
        '''Return (key,value) pair with least key strictly greater than k.'''
        j = self._find_index(k, 0, len(self._table) − 1) # j s key >= k
        if j < len(self._table) and self._table[j]._key == k:
            j += 1 # advanced past match
        if j < len(self._table):
            return (self._table[j]._key, self._table[j]._value)
        else:
            return None
    def find_range(self, start, stop):
        '''Iterate all (key,value) pairs such that start <= key < stop.
            If start is None, iteration begins with minimum key of map.
            If stop is None, iteration continues through the maximum key of map.
        '''
        if start is None:
            j = 0
        else:
            j = self._find_index(start, 0, len(self._table)−1) # find first result
        while j < len(self._table) and (stop is None or self._table[j]._key < stop):
            yield (self._table[j]._key, self._table[j]._value)
            j += 1

复杂度分析

查找某key是否存在于这个映射中，可用二元搜索binary search。此时查询是否存在的复杂度为，这一点优于采用数组实现的无序映射的查询复杂度。对映射中的key赋值，如果是新加值，最坏情况是在index=0复杂度为，而修改值则复杂度为。删除key时，最坏情况是个元素整体向前平移，则复杂度为。

基于链表的有序映射

对链表做查询的复杂度为，而修改的复杂度为。基于链表的有序映射，其实现方式被称为跳表skip list。跳表为查询和更新提供了一种折中方案，代价是更多的存储空间。

映射M的跳表包含了一些列list 。其中的每个保存了映射M的元素子集，且其中的key保持升序，并在头尾加入两个哨兵键sentinel keys，定义为和是小于和大于所有可能键的值且可以插入到映射M中。此外list满足下面条件：

• 包含映射M中的所有元素，包括哨兵key
• 对于，list 包括了从中随机生成的子集
• 仅包含哨兵key和

这里的定义为跳表的高度。

下面介绍如何在跳表中查询特定key。一个sorted map ，其中元素为10个，先需要找到key为55的元素关联的数值。首先从最高的一层开始从找到该元素下一层中的对应元素。向右寻找遇到元素17，17小于50所以接着找下一层中的17右边的下一个元素，即25。25小于50，于是25找到下一层中的25右边的下一个元素31，以此类推。直到找到key为50的元素。

Screen Shot 2022-05-12 at 1.50.28 PM.png

可以看到跳表的存在避免了链表表示map过程中的复杂度为的全文检索。代价是修改元素的代价从变为，和更多的存储空间。考虑到每一层的平均元素个数是前一层的50%，除外，其他所有层的累计元素个数为，故存储空间的占用近乎提高一倍。

Reference

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