Python中不可哈希对象的集合

Question

是否有一个类似于Python set的等价物，用于非哈希对象？（例如可以相互比较但无法哈希的自定义类？）

- Tzach

---

那会是哪个对象？ - user1907906

字符串是可哈希的。 - user1907906

您可以为自定义类定义__hash__方法。 - perreal

不完全是这样；您仍然需要创建对象的可哈希表示形式；该过程可以封装，但是对于特定的对象而言是不同的。 - Martijn Pieters

那么集合并不是正确的方法；你必须对每个输入与现有字符串进行模糊匹配。这根本不是一个集合操作。 - Martijn Pieters

Answer 1

如果您的值不可哈希，则使用set没有意义。请改用list。如果您的所有对象只能测试相等性，则每次测试成员资格都必须扫描每个元素。obj in listvalue 就是这样，扫描列表直到找到相等匹配为止：

if not someobj in somelist:
   somelist.append(someobj)

我会给你提供一个“唯一”值列表。

是的，这将比使用集合慢，但是通过哈希，集合只能实现O(1)复杂度。

如果您的对象是可排序的，您可以通过使用bisect模块来加速操作，将测试降低到O(log N)复杂度。确保您使用从二分测试中获取的信息插入新值以保留顺序。

- Martijn Pieters

---

我想问一下，如果这些列表进行交集/差集操作，那么时间复杂度会是二次的，而且没有任何方法可以改进（假设无法排序），我的理解正确吗？ - georg

如果你指的是set()，那么使用它是没有意义的，因为它不起作用。你的答案使用list实现了set API，这是正确的方法，但应该具有类似的接口。 - Elazar

我相信我们都同意底线。只是你的措辞（“没有使用集合的意义”）有点令人困惑。 - Elazar

但问题并不是在问您是否可以将内置的set与非可哈希对象一起使用。整个问题的基础是您不能这样做。它正在寻找一个等效的对象。当然，在这种情况下，“等效”的确切含义可能不清楚。但考虑到该问题特别提到了可比较的项，可以安全地假设它不是在寻找一个性能等效的解决方案，而是一个语法等效的解决方案。 - JesusFreke

是的，显然。问题是在问是否有一个非可哈希对象的集合等价物。我的答案提到了我能找到的一个等价物。对我来说，这似乎是一个更有用的答案，也是我查看此问题时寻找的答案类型。我完全知道如何实现这样的类（根据提问者的评论，他们也知道）-但我宁愿找到并使用一个预先存在的类，而不是重新发明轮子。 - JesusFreke

Answer 2

在编程中，可以使用来自blist库的 sortedset类，它提供了一组类似于集合的API，适用于可比较（并且潜在地非哈希）的对象，使用基于排序列表的存储机制。

- JesusFreke