Python实现多键字典

实现背景

在许多场景中，有时需要通过多种信息来获取某个特定的值，而各种编程语言（包括Python）使用的字典（Dict）数据结构通常只支持单个键值寻值key-val对，即“一对一”（一个键对应一个值）。而“多对一”的字典在复杂信息映射下有很高实用价值。例如：

在实现非确定性下推自动机的时候，转移函数出现下面的形式：
$$\delta (q,X)=\{(p,Z)\}。$$
如果采用“一对一”字典的形式，那么只能以$q$作为键（key），$(X,p,Z)$的集合作为其对应的值（val）。即dict[q] = {(X,p,Z)}。这样在访问和设置值的时候，遍历的复杂度显然增加了。

显然我们更希望采用形如d[q][X]={(p,Z)}的形式，以q,X作为一对键值去访问和获取(p,Z)对。这就希望有一种数据结构能够实现“多对一”的访问。

为此，可以设计“多键字典”来满足该要求。即对于一个键的个数为$n$的多键字典$D$，它可以通过：
$$D[ke{y}_1][ke{y}_2]...[ke{y}_n]$$
的方式，来获取键值对$(ke{y}_1,ke{y}_2,...,ke{y}_n)$所对应的值。

设计思路

有两种方式可以实现上面提到的“多键字典”。

• 第一种方式是将给定的多键对（multi-keys-pair）转化为一个字符串进行映射：
  对于给定键值对$(ke{y}_1,ke{y}_2,...,ke{y}_n)$，可以将其转化为一个字符串：key_1,key_2,...key_n（即所有键之间用逗号分隔），然后用已有的字典dict映射即可。注意，键之间一定要有分隔符，如果直接连接起来的话，有可能会造成哈希冲突导致两个不同的多键对被映射到同一处。例如：(aa,b)和(a,ab)中的键如果直接连接都会形成aab的字符串，导致哈希冲突。这种方式实现起来比较简单。
• 第二种方式也是本文所介绍和实现的方式：
  采取”嵌套字典”的作法，这种方法也很容易想到，具体做法如下：
  1. 设置“根字典”。
  2. 对于给定的多键对$(ke{y}_1,ke{y}_2,...,ke{y}_n)$和其对应的值$val$，进行映射时按照下面的规则：
     • 令$d=root\_dict$
     • 遍历多键对$ke{y}_1,ke{y}_2,ke{y}_3,...,ke{y}_{n-1}$:
       • 如果$ke{y}_i(i\le n-1)$不在$d$中，那么令$d[ke{y}_i]=new\_dict$（否则不需要进行这一步）。然后令$d=d[ke{y}_i]$（进行字典的嵌套）
     • 令$d[ke{y}_n]=val$。进行完上一步的的时候，$d$已经指向了“最后一层”字典，这时才真正地对multi_keys~val进行映射。

字典的嵌套如下图所示：

此外为了方便，需要设置一个集合对多键对进行存储以便之后获取（对应dict.keys()）。

代码实现

除了上面介绍的基本原理，还实现了字典的诸如keys(),values(),items()的常用操作，以及对in进行重载等：

import copy
from typing import List,Set,Tuple,Any
class multi_key_dict:def __init__(self,key_num = 1) -> None:"""Initialize a multi-key dictionary.Args:key_num (int, optional):the number of keys. Defaults to 1."""assert key_num >= 1self.__key_num = key_numself.__dict = dict()self.__keys = set()passdef set_value(self,keys:tuple,val)->None:"""Set the value of multi_keys_dict[key_1][key_2]...[key_n].Args:keys (tuple): A tuple that contains keys in order. Its length must be equal to the number of keys.val (_type_): Value."""assert len(keys) == self.__key_numd = self.__dictfor i in range(0,self.__key_num-1):key = keys[i]if key not in d:d[key] = dict()d = d[key]d[keys[self.__key_num -1]] = valself.__keys.add(keys)        def get_value(self,keys:tuple)->Any:"""Get the value of multi_keys_dict[key_1][key_2]...[key_n].Args:keys (tuple): A tuple that contains keys in order. Its length must be equal to the number of keys."""assert len(keys) == self.__key_numd = self.__dictfor i in range(0,self.__key_num):d = d[keys[i]]return ddef keys(self)->Set[tuple]:"""Get all keys of the multi_key_dict."""return self.__keys.copy()def values(self)->List[Any]:"""Get all values of the multi_key_dict."""values = []for key in self.__keys:values.append(self.get_value(key))return valuesdef items(self)->Set[Tuple[Tuple,Any]]:"""Get set of all "(keys,val)" in multi_keys_dict."""mutli_keys_dict_items = set()for keys in self.__keys:val = self.get_value(keys)mutli_keys_dict_items.add((keys,val))return mutli_keys_dict_itemsdef __contains__(self,keys:tuple)->bool:"""Check whether the given multi_keys is in the dict.Args:keys (tuple): A tuple that contains keys in order. Its length must be equal to the number of keys.Returns:bool: The result."""assert len(keys) == self.__key_numif keys in self.__keys:return Truereturn Falsedef clear(self)->None:"""Clear all the "keys-val" pairs in the dict.Note that the number of keys is not reset."""self.__dict.clear()self.__keys.clear()def keys_num(self)->int:"""Get the number of keys.""" return self.__key_numdef __str__(self) -> str:items = self.items()s = str()for key,val in items:s += f'{key} : {val}\n'return sdef copy(self):"""Return a deep copy of this dict."""copy.deepcopy(self)

进行测试：

def test_multi_keys_dict():d = multi_key_dict(3)l = [('a','b','c'),('d','e','f'),('g','h','i'),('g','h','j')]# test 'set_value' and 'get_value'for i in range(0,len(l)):d.set_value(l[i],i)assert d.get_value(l[i]) == i# test 'keys'keys = d.keys()for elem in l:assert elem in keys# test 'values':values = d.values()for i in range(0,len(l)):assert i in values# test 'items':items = d.items()for i in range(0,len(l)):assert (l[i],i) in items# test 'in':for elem in l:assert elem in d# test 'clear':d.clear()assert len(d.keys()) == 0print('Test passed!')if __name__ == '__main__':test_multi_keys_dict()