为什么不能通过枚举以外的方式从HashSet中检索项目？

Question

我希望了解HashSet设计者的想法。据我所知，我的问题适用于Java和C#中的HashSets，这让我认为一定有一些很好的理由，尽管我自己想不出来。

在我将项目插入HashSet之后，为什么无法在没有枚举的情况下检索该项目，这几乎是一种低效的操作？特别是因为HashSet明确以支持高效检索的方式构建。

对我来说，Remove(x)和Contains(x)返回实际被删除或包含的项通常会很有用。这不一定是我传递给Remove(x)或Contains(x)函数的项。当然，我猜我可以通过HashMap实现相同的效果，但为什么要浪费所有那些空间和精力，当使用一个集合应该完全可以做到这一点？

我可以理解，可能存在一些设计上的问题，添加此功能将允许HashSet的用途与其在框架中的角色或未来角色不一致，但如果是这样，这些设计问题是什么？

编辑

为了回答更多问题，以下是更多细节：

我正在使用一个不可变的引用类型，并重写了哈希码、等于等方法，以在C#中模拟值类型。假设该类型具有成员A、B和C。哈希码、等于等方法仅取决于A和B。给定一些A和B，我想能够从哈希集合中检索相应的项目并获取它的C。似乎我不能使用HashSet来实现这一点，但至少我想知道是否有任何很好的理由。伪代码如下：

public sealed class X{
 object A;
 object B;
 object extra;

 public int HashCode(){
  return A.hashCode() + B.hashCode();
 }

 public bool Equals(X obj){
  return obj.A == A && obj.B == B;
 }
}

hashset.insert(new X(1,2, extra1));
hashset.contains(new X(1,2)); //returns true, but I can't retrieve extra

- sooniln

---

为什么在没有枚举的情况下无法检索该项？您的意思是get()，contains()在您的情况下是O(n)吗？ - daveb

当然 :) 我的意思是，如果不使用枚举，我无法检索到我放入集合中的确切引用。 HashSet没有get()运算符，contains()需要一个参数，该参数可能会被评估为等于您放入的引用，但可能不是您放入的确切引用。希望这样能澄清问题。 - sooniln

在这种情况下，您可以将equals()实现为return this == obj - 即仅检查相同的引用。没有对象创建控制，这是一个很高的代价。而对象创建控制可能会单独解决这个问题。 - daveb

你忽略了哈希值不一定是唯一的，它只是一个索引工具。 - paparazzo

这是至少在.NET（v4.7.2）中添加的。 - nawfal

Answer 1

在 .Net 中，你可能正在寻找的是 KeyedCollection。 http://msdn.microsoft.com/en-us/library/ms132438.aspx 你可以使用一些“通用”的技巧来避免每次重新实现此抽象类的困难。 （查看 IKeyedObject`1。）

注意：任何实现 IKeyedObject`1 接口的数据传输对象都应该有一个重写的 GetHashCode 方法，它只返回 this.Key.GetHashCode()；同样，Equals 也是如此...

我的基础类库通常会包含像这样的内容：

public class KeyedCollection<TItem> : System.Collections.ObjectModel.KeyedCollection<TItem, TItem>
    where TItem : class
{
    public KeyedCollection() : base()
    {
    }

    public KeyedCollection(IEqualityComparer<TItem> comparer) : base(comparer)
    {
    }

    protected override TItem GetKeyForItem(TItem item)
    {
        return item;
    }
}

public class KeyedObjectCollection<TKey, TItem> : System.Collections.ObjectModel.KeyedCollection<TKey, TItem>
    where TItem : class, IKeyedObject<TKey>
    where TKey : struct
{
    public KeyedCollection() : base()
    {
    }

    protected override TItem GetKeyForItem(TItem item)
    {
        return item.Key;
    }
}

///<summary>
/// I almost always implement this explicitly so the only
/// classes that have access without some rigmarole
/// are generic collections built to be aware that an object
/// is keyed.
///</summary>
public interface IKeyedObject<TKey>
{
    TKey Key { get; }
}

- leat

---

我不确定 KeyedCollection<TItem, TItem> 在实际中是否有用。 - nawfal

Answer 2

你打算如何从哈希集合中检索项目？集合的定义不涉及任何排序，因此没有索引可用于检索所需对象。

集合作为一个概念，用于测试包含性，即所讨论的元素是否在哈希数据集中。如果您想使用键值或索引从数据源检索值，则建议查看Map或List。

编辑：基于原始问题的编辑的其他答案

根据您的新信息，似乎您有兴趣将数据实现为Java Enum，类似于以下内容：

 public enum SoonilsDataType {
      A, B, C;

      // Just an example of what's possible
      public static SoonilsDataType getCompositeValue(SoonilsDataType item1,
           SoonilsDataType item2) {
           if (item1.equals(A) && 
                     item2.equals(B)) {
                return C;
           }
      }
 }

枚举类型会自动继承values()方法，该方法返回枚举“集合”中的所有值列表，您可以像Set一样使用它来测试包含关系。此外，由于它是一个完整的类，您可以定义新的静态方法来执行组合逻辑（就像我在示例代码中尝试的那样）。唯一需要注意的是，枚举类型无法在运行时添加新实例，这可能不是您想要的（但如果集合数据大小不会在运行时增长，则应使用枚举类型）。

- Peter

---

@andresp 我知道这已经很晚了，但是如果你知道在可枚举集合（包括HashSet）中只有一个元素，那么扩展方法First()和/或Single()正是你想要/需要的。 - Anthony

我甚至都不记得我需要这个的具体情况，但还是谢谢你 :) - andresp

@quetzalcoatl 如果你知道你只有一个元素，他的评论并不是针对OP的。 - Wolfzoon

@Peter，我仍然在想你希望通过SoonilsDataType实现什么。特别是因为发布的代码失败了，因为getCompositeValue没有if语句之外的返回语句。 - Wolfzoon

@Wolfzoon：我根据标题写了这个评论，即“没有枚举”的哈希集部分，可能我没有注意到andresp！=sooniln，谢谢！ :) - quetzalcoatl

Answer 3

如果在插入对象后更改对象，则它的哈希值可能已更改（如果重写了hashCode()，则尤其可能）。如果哈希值发生变化，在集合中查找就会失败，因为您将尝试查找一个在不同位置哈希的对象。

另外，如果要查找不同实例但相等的对象，则需要确保在对象中覆盖hashCode和equals方法。

请注意，以上全部是针对Java的 - 我假设C#有类似的功能，但由于我已经好几年没有使用C#了，我会让其他人来说它的能力。

- aperkins

---

这是确实如此，但目前完全有可能通过在将其添加到集合后保留引用来破坏 HashSet（以及具有此不变量的所有组件）。 您可以使用该引用对其进行突变并使不变性无效。 API已经依赖于用户履行此契约，返回对象引用不会改变此情况。 - sooniln

Answer 4

我想设计者希望确保在Set接口和HashSet类中定义的remove（Object）方法也适用于Collection接口; 该方法返回一个布尔值，指示对象是否已成功删除。如果设计者想要提供功能，使remove（Object）返回已经存在于Set中的“相等”对象，这意味着不同的方法签名。

此外，由于要删除的对象在逻辑上等于传递给remove（Object）的对象，因此可以争论返回包含的对象所添加的价值。但是，我以前遇到过这个问题，并使用Map来解决问题。

请注意，在Java中，HashSet在内部使用HashMap，因此在使用HashMap时不会有额外的存储开销。

- Adamski

---

你关于Java的看法是正确的 :) 不幸的是，C#并不使用HashMap来实现HashSet，如果可能的话，我想保留一些空间/时间上的优势。 - sooniln

Answer 5

为什么不直接使用 HashMap<X,X> 呢？这正是您想要的。只需每次执行 .put(x,x)，然后就可以使用 .get(x) 获取存储的等于 x 的元素。

- user1111929

Answer 6

这是库设计者的疏忽。如我在另一个答案中提到的，该方法已添加到.NET Framework 4.7.2（以及其之前的.NET Core 2.0）；请参见HashSet<T>.TryGetValue。引用来源：

/// <summary>
/// Searches the set for a given value and returns the equal value it finds, if any.
/// </summary>
/// <param name="equalValue">The value to search for.
/// </param>
/// <param name="actualValue">
/// The value from the set that the search found, or the default value
/// of <typeparamref name="T"/> when the search yielded no match.</param>
/// <returns>A value indicating whether the search was successful.</returns>
/// <remarks>
/// This can be useful when you want to reuse a previously stored reference instead of 
/// a newly constructed one (so that more sharing of references can occur) or to look up
/// a value that has more complete data than the value you currently have, although their
/// comparer functions indicate they are equal.
/// </remarks>
public bool TryGetValue(T equalValue, out T actualValue)

- Douglas

Answer 7

解决方案。我认为希望找到一个元素是完全合理的，因为用于搜索的代表可能与找到的元素不同。特别是如果元素包含键和值信息，并且自定义相等比较器仅比较键部分。请参见代码示例。该代码包含实现自定义搜索并捕获找到的元素的比较器。这需要比较器的实例。清除对找到的元素的引用。通过Contains进行搜索。访问找到的元素。在共享比较器实例时注意多线程问题。

using System;
using System.Collections.Generic;

namespace ConsoleApplication1 {

class Box
{
    public int Id;
    public string Name;
    public Box(int id, string name)
    {
        Id = id;
        Name = name;
    }
}

class BoxEq: IEqualityComparer<Box>
{
    public Box Element;

    public bool Equals(Box element, Box representative)
    {
        bool found = element.Id == representative.Id;
        if (found)
        {
            Element = element;
        }
        return found;
    }

    public int GetHashCode(Box box)
    {
        return box.Id.GetHashCode();
    }
}

class Program
{
    static void Main()
    {
        var boxEq = new BoxEq();
        var hashSet = new HashSet<Box>(boxEq);
        hashSet.Add(new Box(3, "Element 3"));
        var box5 = new Box(5, "Element 5");
        hashSet.Add(box5);
        var representative = new Box(5, "Representative 5");
        boxEq.Element = null;
        Console.WriteLine("Contains {0}: {1}", representative.Id, hashSet.Contains(representative));
        Console.WriteLine("Found id: {0}, name: {1}", boxEq.Element.Id, boxEq.Element.Name);
        Console.WriteLine("Press enter");
        Console.ReadLine();
    }
}

} // namespace

- Michiel de Wolde

Answer 8

看起来你实际上正在寻找一个 Map<X,Y>，其中 Y 是 extra1 的类型。

---

（以下是抱怨）

equals和hashCode方法定义了有意义的对象相等性。HashSet类假定如果两个对象根据Object.equals(Object)定义相等，则这两个对象之间没有区别。

我甚至可以说，如果“object extra”具有意义，则您的设计并不理想。

- Robert Munteanu

---

我对你的不满表示同意 :) 这个 map 是可以用的，但是我决定不要增加额外的开销，可能会自己编写一个集合（因为这不是生产代码，哈哈）+1 - sooniln

Answer 9

在思考同样的问题后，最终成功查看了源代码：

源代码：http://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs

集合是一组唯一的项目（对象或值）。在 .net 实现中，如果比较器的 Equals 方法返回两个项目为 true，则一个项目与另一个项目相同（不唯一）。而不是两个项目具有相同的哈希代码。因此，检查项目的存在是一个两步过程。首先使用哈希集来最小化要进行比较的项目数量，然后进行比较本身。

如果您希望检索一个项目，您必须能够向检索函数提供唯一标识符。您可能知道您想要的项目的哈希代码。但这还不够。因为多个项目可以具有相同的哈希值。您还需要提供项目本身，以便可以调用 Equal 方法。显然，如果您拥有该项目，则没有获取它的理由。

可以创建一个数据结构，要求没有两个唯一的项返回相同的哈希码。然后你可以从中获取一个项目。它将比添加更快，并且如果你知道哈希值，则检索将是可能的。如果将两个不相等但返回相同哈希值的项放入其中，则第一个将被覆盖。据我所知，在 .net 中不存在这种类型，而且这与字典不同。

*假设 GetHash 方法相同。

- user1852503

Answer 10

这些语言中的集合对象大多设计为值的集合，而不是可变对象。它们通过使用equals检查放入其中的对象是否唯一。这就是为什么contains和remove返回布尔值而不是对象：它们检查或删除您传递给它们的值。

实际上，如果您在集合上执行contains（X），并期望获得不同的对象Y，则意味着X和Y相等（即X.equals（Y）=> true），但有些不同，这似乎是错误的。

- penpen

---

集合根据您指定的比较方法是唯一的。仅仅因为我希望在我的集合中使用比较方法A，并不意味着当我考虑相同的对象时，比较方法B就没有价值了。关于可变性的评论，请参见我对aperkins的回答。 - sooniln

即使对象是不可变的，返回存储实例仍然可能具有重要的实用性。其中一种情况是，假设有大量不可变的嵌套数据结构（例如从XML文档解析而来），并且希望将对相同但未共享的数据结构的引用替换为对共享数据结构的引用。具有查找操作的HashMap<T>可以返回传入的项，这将是理想的选择。 - supercat