34

HashSet 設計者の頭の中への洞察を探しています。私が知る限り、私の質問は Java と C# HashSets の両方に当てはまるので、自分では考えられませんが、それには正当な理由があるに違いないと思います。

項目を HashSet に挿入した後、その項目を列挙せずに取得することが不可能であり、ほとんど効率的な操作ではないのはなぜですか? 特に、HashSet は効率的な検索をサポートする方法で明示的に構築されているためです。

Remove(x) と Contains(x) が、削除または含まれている実際のアイテムを返すようにすると便利なことがよくあります。これは、必ずしも Remove(x) または Contains(x) 関数に渡す項目ではありません。確かに、HashMap を使用して同じ効果を達成できると思いますが、セットでこれを完全に実行できるはずなのに、なぜそのすべてのスペースと労力を無駄にするのでしょうか?

この機能を追加すると、フレームワークでの役割または将来の役割と一致しない HashSet の使用が可能になるという設計上の懸念があることは理解できますが、そうである場合、これらの設計上の懸念は何ですか?

編集

さらにいくつかの質問に答えるために、詳細を以下に示します。

C# で値の型をエミュレートするために、オーバーライドされたハッシュコード、equals などで不変の参照型を使用しています。型にメンバー A、B、および C があるとします。ハッシュコード、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で、おそらく探しているのはKeyedCollectionhttp ://msdn.microsoft.com/en-us/library/ms132438.aspxです。

この抽象クラスを「一般的な」巧妙さで毎回再実装することの厄介さを回避することができます。（IKeyedObject`1を参照してください。）

注：IKeyedObject`1を実装するデータ転送オブジェクトには、this.Key.GetHashCode（）;を返すだけのオーバーライドされた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 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() を継承し、列挙型の「セット」内のすべての値のリストを返します。これを使用して、セットと同じ方法で包含をテストできます。また、完全なクラスであるため、新しい静的メソッドを定義して複合ロジックを実行できます (コード例で言及しようとしていたように)。列挙型に関する唯一のことは、実行時に新しいインスタンスを追加できないことです。これは、必要なものではない可能性があります (ただし、実行時にセットのデータ サイズが大きくならない場合は、列挙型が必要です)。

于 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）に渡されるオブジェクトと論理的に等しいことを考えると、含まれているオブジェクトを返す際に追加される値については議論の余地があります。しかし、私は以前にこの問題を抱えており、マップを使用して問題を解決しました。

Javaでは、aHashSetはHashMap内部で使用するため、HashMap代わりにを使用しても追加のストレージオーバーヘッドは発生しないことに注意してください。

于 2009-09-29T21:01:21.533 に答える
3

を使用しないのはなぜHashMap<X,X>ですか？これはまさにあなたが望むことをします。.put(x,x)毎回行うだけで、格納されている要素を x と等しい値で取得できます.get(x)。

于 2012-09-13T22:18:31.217 に答える
1

Map<X,Y>Y が の型である を実際に探しているように見えますextra1。

（以下の暴言）

equals メソッドと hashCode メソッドは、意味のあるオブジェクトの等価性を定義します。HashSet クラスは、定義されているように 2 つのオブジェクトが等しい場合Object.equals(Object)、これら 2 つのオブジェクト間に違いはないと想定します。

もしobject extra意味があるなら、あなたのデザインは理想的ではないとまで言えます。

于 2009-09-30T17:54:38.490 に答える
0

自分のオブジェクトをKeyValuePairsとして定義することにより、マップを使用する方法について興味深い提案がありました。良いコンセプトですが、残念ながらKeyValuePairはインターフェースではなく（なぜですか？）、その計画を空中から発射する構造体です。私の制約が私にこのオプションを許すので、最後に私は私自身のセットを転がします。

于 2009-10-01T18:54:07.217 に答える
0

これらの言語のセット オブジェクトは、ほとんどの場合、値のセットとして設計されており、可変オブジェクト用ではありません。それらは、等号を使用して、それらに入れられたオブジェクトが一意であることを確認します。そのため、contains と remove は、オブジェクトではなくブール値を返します。渡された値をチェックまたは削除します。

実際、セットに対して contains(X) を実行し、別のオブジェクト Y を取得することを期待する場合、X と Y は等しい (つまり、X.equals(Y) => true) ことを意味しますが、多少異なります。間違っているようです。

于 2009-09-29T20:55:25.620 に答える
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 メソッドが 2 つの項目に対して true を返す場合、その項目は別の項目と同じです (一意ではありません)。2 つのアイテムのハッシュ コードが同じ場合は、そうではありません。そのため、アイテムの存在のチェックは 2 段階のプロセスです。最初にハッシュセットを使用して比較するアイテムの数を最小限に抑え、次に圧縮自体を行います。

アイテムを取得する場合は、取得関数に一意の識別子を指定できる必要があります。欲しいアイテムのハッシュコードを知っているかもしれません。しかし、それだけでは十分ではありません。複数のアイテムが同じハッシュを持つことができるためです。また、Equal メソッドを呼び出すことができるように、項目自体を提供する必要があります。明らかに、アイテムを持っている場合、それを取得する理由はありません。

2 つの一意のアイテムが同じハッシュ コードを返さないことを要求するデータ構造を作成できます。そして、そこからアイテムを取得できます。追加*した方が早いですし、ハッシュさえわかれば取得も可能です。等しくないが同じハッシュを返す 2 つのアイテムがそれに入れられると、最初のアイテムが上書きされます。私の知る限り、この Type は .net には存在しません。これは辞書と同じではありません。

* GetHash メソッドが同じであることを前提としています。

于 2014-11-15T07:52:41.077 に答える