7

AHashSet<T>可以在 O(1) 中确定它是否包含某个项目。如果我在我的自定义类上覆盖Equals()和GetHashCode()，我可以拥有一个对象 A 和另一个对象 A'，它们的身份不Equals()相等，但返回true并GetHashCode()返回相同的哈希码。

现在，假设 A 在散列集中，我想在给定 A' 的 O(1) 中检索 A（从散列集的角度来看，它等于 A）。

var a = new MyClass("A");
var a_prime = new MyClass("A");
Debug.Assert(a.Equals(a_prime));
Debug.Assert(a.GetHashCode() == a_prime.GetHashCode());

var set = new HashSet<MyClass>();
set.Add(a);
Debug.Assert(set.Contains(a_prime));

// This:    
var retrieved_a = set.Get(a_prime);

这该怎么做？

（请注意，这不是我要找的答案，而且根本没有答案。）

一些背景信息：我想使用该集合来实习我自己的对象，就像 C# 实习生字符串一样：相等的对象只需要一个实例。这样，我可以将元数据附加到这样的对象，并确保在没有该元数据的任何地方都没有其他相同的实例。

4

3 回答 3

7

没有任何方法HashSet可以满足您的要求。

您可以使用 aDictionary代替：

var dict = new Dictionary<MyClass, MyClass>();
dict[a] = a;
Debug.Assert(dict.ContainsKey(a_prime));
var retrieved_a = dict[a_prime];
于 2012-06-06T23:07:17.103 回答
1

如果我没记错的话，Dictionary没有基本集合操作的恒定时间实现，而HashSet有。这是一种使用恒定时间相等查找来实现它的方法，而不会增加 HashSet 的其他复杂性。如果您需要抓取许多随机元素，则使用此方法至关重要。我在下面写的是 Java 语法，因为我不懂 C#，但这个想法是与语言无关的。

class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();

     //selects equal element in constant time
     A equalElement(A input) {
         return contents.get(indices.get(input));
     }

     //adds new element in constant time
     void add(A a) {
         indices.put(a,contents.size());
         contents.add(a);
     }

     //removes element in constant time
     void remove(A a) {
         int index = indices.get(a);
         contents.set(index,contents.get(contents.size()-1));
         contents.remove(contents.size()-1);
         indices.set(contents.get(contents.size()-1),index);
         indices.remove(a);
     }

     //all other operations (contains(), ...) are those from indices.keySet()
}
于 2012-09-13T22:22:12.757 回答
0

使用HashSet.TryGetValue. （从.NET Framework 4.7.2开始可用。）

于 2020-12-09T14:56:09.787 回答