Skip to main content
 首页 » 编程设计

python之有没有办法在 O(1) 时间内使用其中一个键获取值

2025年02月15日10zhoujg

我正在为应用程序建模数据,并决定选择字典作为我的数据结构。但是数据中的每一行都有多个键。所以我创建了一个字典,其中包含映射每一行的多个键,例如:

>>> multiKeyDict = {} 
>>> multiKeyDict[('key1','key2','key3')] = 'value1' 
>>> multiKeyDict.get(('key1','key2','key3')) 
'value1' 

现在我必须在 O(1) 时间内使用 key1 检索所有值。根据我的研究,我知道我可以做到:

我也愿意接受任何更好的数据结构而不是使用字典。

请您参考如下方法:

您没有多个 key 。就Python字典而言,只有一个键,一个元组对象。除了 O(N) 线性时间之外,您无法搜索元组的组成部分。

如果您的 key 是唯一的,只需单独添加每个 key :

multiKeyDict['key1'] = multiKeyDict['key2'] = multiKeyDict['key3'] = 'value1' 

现在您有 3 个键都引用一个值。此处不复制值对象,仅复制对它的引用。

您找到的 multi_key_dict 包使用中间映射将给定的组成键映射到复合键,然后再映射到值。这也为您提供了 O(1) 搜索,具有相同的限制,即每个构成键必须是唯一的。

如果您的键不是唯一的,那么您需要将每个键映射到另一个容器,然后保存值,例如一个集合:

for key in ('key1', 'key2', 'key3): 
    multiKeyDict.setdefault(key, set()).add(value) 

现在查找一个键会为您提供该键引用的所有值的集合。

如果您也需要能够组合键,那么您可以为这些组合添加额外的引用。键值对比较便宜,都是引用。键和值对象本身不重复。