Python中适合实现pair-key键对查找的优质数据结构是什么

你当前的实现有两个硬伤：

1. 代码无法直接运行：Python里set是可变类型，不可哈希，不能作为字典键，执行会直接抛TypeError: unhashable type: 'set'
2. 就算把键替换成可哈希的frozenset勉强跑通，单键查询需要遍历全量条目，时间复杂度O(n)，数据量上去之后性能会非常差。

要同时支持单键、双键的高效查询，最实用的方案是维护双层索引，增删数据时同步更新两份索引，两种查询都能做到O(1)时间复杂度。

核心是维护两个独立的字典索引，分别适配两种查询场景：

• 双键精确查询索引：键为排序后的二元元组（适配键对无序的特性，保证(a,b)和(b,a)被识别为同一个键），值为存储的业务内容
• 单键查询索引：键为单个字符串，值为所有包含该单键的业务内容列表

可以用一个简单的封装类统一维护索引，避免手动同步出错：

class PairKeyMap:
    def __init__(self):
        self._pair_idx = {}  # 双键查询索引
        self._single_idx = {} # 单键查询索引

    def put(self, k1: str, k2: str, val: str) -> None:
        # 生成无序对的标准键
        norm_pair = tuple(sorted((k1, k2)))
        self._pair_idx[norm_pair] = val
        # 同步更新单键索引
        self._single_idx.setdefault(k1, []).append(val)
        self._single_idx.setdefault(k2, []).append(val)

    def get_by_pair(self, k1: str, k2: str) -> str | None:
        norm_pair = tuple(sorted((k1, k2)))
        return self._pair_idx.get(norm_pair)

    def get_by_single(self, k: str) -> list[str]:
        return self._single_idx.get(k, [])

使用示例 #

pmap = PairKeyMap()
pmap.put("a", "b", "a-b relationship")
pmap.put("c", "d", "c-d relationship")
pmap.put("e", "f", "e-f relationship")

# 单键查询
print(pmap.get_by_single("a")) # ['a-b relationship']
# 双键查询，传参顺序不影响结果
print(pmap.get_by_pair("b", "a")) # a-b relationship
print(pmap.get_by_pair("a", "b")) # a-b relationship

补充说明 #

• 如果你的键对是有序的（比如表示有向关系，a→b和b→a是两个不同条目），生成双键索引键时不需要排序，直接按传入顺序生成元组即可，单键索引逻辑不需要调整
• 如果需要支持删除操作，只要在两个索引中同步移除对应条目即可，逻辑复杂度很低
• 相比全表遍历的实现，双索引方案在数据量超过1000条时，查询速度会有数百倍的提升，内存占用的增加几乎可以忽略。

内容的提问来源于stack exchange，提问作者smuseus