(2022.05.07 Sat)
Python中的dict字典類型可能是最重要的數(shù)據(jù)結(jié)構(gòu)之一觉痛，其中每個鍵值key映射到一個關(guān)聯(lián)的值鹦倚。由key映射到關(guān)聯(lián)值的被稱作關(guān)聯(lián)序列(associative array)或映射(maps)。映射的案例包括
- DNS服務器接收到hostname請求后，返回host對應的ip地址
- 數(shù)據(jù)庫中一個學生id對應的學生相關(guān)信息
- RGB色彩空間中顏色對應的色值
映射的簡單實現(xiàn)
映射的抽象類型馆里，應該有如下方法，注意這些方法也是Python內(nèi)置的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)
直覺上可柿，我們可以使用如下方法實現(xiàn)字典/映射的功能：
鍵k和對應的值v保存為一個k-v pair鸠踪，保存為tuple類型，即(k, v)复斥。將該鍵值對推入一個list中营密。查詢和更新時，遍歷list永票，找到符合條件的key卵贱，并返回和修改對應的值，或執(zhí)行其他操作侣集。判斷特定的鍵是否包含在該字典中键俱，則遍歷list如果發(fā)現(xiàn)有鍵值對的key是
，則返回
True世分。
下面是一個簡單實現(xiàn)
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
調(diào)用
>>> 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
復雜度分析
考慮到這種實現(xiàn)方式中對字典的查詢和修改都要遍歷整個list编振，查詢的復雜度都為，效率低下。
Reference
1 Goodrich and etc., Data Structures and Algorithms in Python
