python - 我可以在 Python 中用什么替换 tuple(sorted(my_string))？

Question

我想使用诸如“顺序无关紧要的字符”之类的东西作为在 Python 中构建字典的键。

像“abc”和“cba”可以给我相同的哈希索引，而“aab”和“ab”可以给我不同的哈希索引。

我发现一种方法是使用 tuple(sorted(my_string)) 对字符列表进行哈希处理，但这可能需要 O(NlogN) 时间复杂度。

我尝试使用 Counter，但它不可哈希。 Frozenset 是可散列的，但它不允许重复。

是否有更好的方法(O(N) 时间复杂度)来替换 tuple(sorted(my_string))？

如有错误请指正。谢谢!

Answer 1

您可以使用 frozenset(Counter(my_string).items()) 获得 O(N) 时间复杂度。不过，您可能想计算这在实践中是否真的获胜，因为此代码的常数因子可能高到足以超过 ''.join(sorted(my_string)) 的额外对数因子。