34

我正在寻找对 HashSet 设计者负责人的深入了解。据我所知，我的问题同时适用于 Java 和 C# HashSet，这让我认为这一定有一些充分的理由，尽管我自己也想不出任何理由。

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

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

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

编辑

要回答更多问题，以下是更多详细信息：

我正在使用具有覆盖哈希码、等号等的不可变引用类型来模拟 C# 中的值类型。假设该类型具有成员 A、B 和 C。Hashcode、equals 等仅依赖于 A 和 B。假设某些 A 和 BI 希望能够从哈希集中检索该等价项并获得它是 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
4

12 回答 12

11

在 .Net 中，您可能正在寻找的是 KeyedCollection http://msdn.microsoft.com/en-us/library/ms132438.aspx

你可以通过一些“通用”的聪明来解决每次重新实现这个抽象类的麻烦。（请参阅 IKeyedObject`1。）

注意：任何实现 IKeyedObject`1 的数据传输对象都应该有一个重写的 GetHashCode 方法，只需返回 this.Key.GetHashCode(); 同样适用于平等......

我的基类库通常以这样的方式结束：

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; }
}
于 2011-01-26T15:56:44.617 回答
9

您打算如何从哈希集中检索项目？根据定义，集合没有以任何方式排序，因此没有可用于检索相关对象的索引。

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

编辑：基于对原始问题的编辑的附加答案

Soonil，根据您的新信息，您可能有兴趣将您的数据实现为 Java 枚举，类似于以下内容：

 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() 返回枚举的“集合”中所有值的列表，您可以使用与集合相同的方式来测试包含。此外，因为它是一个完整的类，您可以定义新的静态方法来执行复合逻辑（就像我在示例代码中试图暗示的那样）。关于 Enum 的唯一问题是您不能在运行时添加新实例，这可能不是您想要的（尽管如果集合的数据大小在运行时不会增长，那么 Enum 就是您想要的）。

于 2009-09-29T20:57:25.100 回答
4

如果在插入后更改对象，则它的哈希可能已更改（如果 hashCode() 已被覆盖，则尤其可能发生这种情况）。如果散列发生变化，则在集合中查找它会失败，因为您将尝试查找在与存储位置不同的位置散列的对象。

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

请注意，这都是针对 Java 的——我假设 C# 也有类似的东西，但是自从我使用 C# 以来已经有好几年了，我会让其他人谈论它的功能。

于 2009-09-29T20:46:24.747 回答
3

Set我想接口和类的设计者HashSet希望确保接口remove(Object)上定义的方法Collection也适用于Set；此方法返回一个布尔值，表示对象是否已成功删除。如果设计者想要提供 remove(Object) 返回“相等”对象的功能，Set这将意味着不同的方法签名。

此外，鉴于被移除的对象在逻辑上等于传递给 remove(Object) 的对象，因此在返回包含的对象时添加的值是有争议的。但是，我自己之前也遇到过这个问题，并且使用了 Map 来解决这个问题。

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

于 2009-09-29T21:01:21.533 回答
3

为什么不只使用 a HashMap<X,X>？这正是你想要的。.put(x,x)每次都这样做，然后你就可以用 .x 获得等于 x 的存储元素.get(x)。

于 2012-09-13T22:18:31.217 回答
3

这是图书馆设计师的疏忽。正如我在另一个答案中提到的，此方法已添加到.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)
于 2018-07-07T07:53:56.040 回答
1

在我看来，您实际上是在寻找 a Map<X,Y>，其中 Y 是 的类型extra1。

（下面吐槽）

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

我想说的object extra是，如果有意义，那么您的设计并不理想。

于 2009-09-30T17:54:38.490 回答
1

解决了。希望找到一个元素对我来说似乎完全有效，因为用于搜索的代表可能与找到的元素不同。如果元素包含键和值信息，并且自定义相等比较器仅比较键部分，则尤其如此。请参阅代码示例。该代码包含一个实现自定义搜索并捕获找到的元素的比较器。这需要一个比较器的实例。清除对找到的元素的引用。通过包含执行搜索。访问找到的元素。共享比较器实例时要注意多线程问题。

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
于 2016-03-11T07:30:57.823 回答
0

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

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

于 2009-09-29T20:55:25.620 回答
0

通过让我自己的对象将自己定义为 KeyValuePairs，我得到了一个关于使用 Map 的方法的有趣建议。虽然是一个很好的概念，但不幸的是 KeyValuePair 不是一个接口（为什么不呢？）并且是一个结构，它把这个计划从空中发射出去。最后，我将推出自己的 Set，因为我的约束允许我使用此选项。

于 2009-10-01T18:54:07.217 回答
0

简短的回答；因为这些项目不能保证是不可变的。

我遇到了您描述的确切问题，其中 HashCode 基于成员类中的固定字段，但该类包含可以在不更改哈希的情况下更新的附加信息。

我的解决方案是实现一个基于 ICollection<T> 的通用 MyHashSet<T>，但包裹在 Dictionary<int, List<T>> 以提供所需的查找效率，其中 int 键是 T 的 HashCode。但是，这表明如果成员对象的 HashCode 可以更改，那么字典查找后跟列表中项目的相等比较将永远找不到更改的项目。没有强制成员不可变的机制，因此唯一的解决方案是枚举批次。

于 2012-03-14T12:53:41.910 回答
0

在想了同样的事情之后，并且能够很好地查看源代码：

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

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

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

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

*假设 GetHash 方法是相同的。

于 2014-11-15T07:52:41.077 回答