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

Question

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

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

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

使用 this 包来完成工作但不确定它是否为 O(1)
按照此处的建议搜索键：

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

Answer 1

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

如果您的密钥是唯一的，只需单独添加每个密钥：

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)

现在查找一个键可以得到该键引用的所有值的集合。

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

Answer 2

另一种可能性是为共享键组件的行对象列表建立索引。如果共享任何特定键值的行数很小，这将非常有效。（假设行对象具有访问为 row.key1、row.key2 等的键，这不是一个非常相关的细节）。未经测试的代码：

index = {}
for row in rows:
    index.setdefault( row.key1, []).append(row)
    index.setdefault( row.key2, []).append(row)
    index.setdefault( row.key3, []).append(row)

然后查找匹配的行，例如 key2 和 key3

candidates = index[ key2] 
if len( index[key3]) < len(candidates): 
    candidates = index[key3] # use key3 if it offers a better distribution
results = []
for cand in candidates:
    if cand.key2 == key2 and cand.key3 == key3: # full test is necessary!
        results.append( cand)

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

Is there a way to get values using one of the keys in O(1) time

python

dictionary

data-modeling