1

ハッシュ化されたセットの内部がどのように機能するか、HashSet<T>およびそれらがパフォーマンスを発揮する理由をよりよく理解しようとしています。次の記事を発見し、バケット リストhttp://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/を使用して簡単な例を実装しました。

私がこの記事を理解している限り (以前もそう思っていました)、バケット リスト自体は、各バケット内の特定の量の要素をグループ化します。1 つのバケットはGetHashCode、要素で呼び出されるハッシュコードによって表されます。より良いパフォーマンスは、要素よりもバケットが少ないという事実に基づいていると思いました。

今、私は次の素朴なテストコードを書きました:

    public class CustomHashCode
    {
        public int Id { get; set; }

        public override int GetHashCode()
        {
            //return Id.GetHashCode(); // Way better performance
            return Id % 40; // Bad performance! But why?
        }


        public override bool Equals(object obj)
        {
            return ((CustomHashCode) obj).Id == Id;
        }

    }

そして、ここでプロファイラー:

    public static void TestNoCustomHashCode(int iterations)
    {

        var hashSet = new HashSet<NoCustomHashCode>();
        for (int j = 0; j < iterations; j++)
        {
            hashSet.Add(new NoCustomHashCode() { Id = j });
        }

        var chc = hashSet.First();
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int j = 0; j < iterations; j++)
        {
            hashSet.Contains(chc);
        }
        stopwatch.Stop();

        Console.WriteLine(string.Format("Elapsed time (ms): {0}", stopwatch.ElapsedMilliseconds));
    }

私の素朴な考えは、パフォーマンスを向上させるはずのバケットの量を（単純なモジュロで）減らしましょう。しかし、それはひどいものです (私のシステムでは、50000 回の反復で約 4 秒かかります)。また、単純に Id をハッシュコードとして返すと、最終的に 50000 バケットになるため、パフォーマンスが低下するはずだとも考えました。しかし、その逆です。何かを改善するのではなく、単にいわゆる衝突のトーンを生成しただけだと思います。繰り返しになりますが、バケット リストはどのように機能するのでしょうか。

4

3 に答える 3

3

Contains基本的にチェック：

  1. アイテムのハッシュコードを取得します。
  2. 対応するバケットを検索します。これは、アイテムのハッシュコードに基づく直接配列ルックアップです。
  3. バケットが存在する場合は、バケット内のアイテムを検索しようとします。これにより、バケット内のすべてのアイテムが繰り返されます。

バケットの数を制限することで、各バケット内のアイテムの数を増やし、アイテムが存在するかどうかを確認するために、ハッシュセットが反復して等しいかどうかを確認する必要があるアイテムの数を増やしました。したがって、特定のアイテムが存在するかどうかを確認するのに時間がかかります。

おそらく、ハッシュセットのメモリフットプリントを減らしました。疑わしいですが、挿入時間を短縮したかもしれません。存在チェック時間を短縮していません。

于 2012-12-12T10:39:36.143 に答える
1

単純なHashSet<T>ものはこのように実装できます（スケッチだけで、コンパイルされません）

class HashSet<T>
{
    struct Element
    {
        int Hash;
        int Next;
        T item;
    }

    int[] buckets=new int[Capacity];
    Element[] data=new Element[Capacity];

    bool Contains(T item)
    {
        int hash=item.GetHashCode();
        // Bucket lookup is a simple array lookup => cheap
        int index=buckets[(uint)hash%Capacity];
        // Search for the actual item is linear in the number of items in the bucket
        while(index>=0)
        {
           if((data[index].Hash==hash) && Equals(data[index].Item, item))
             return true;
           index=data[index].Next;          
        }
        return false;
    }
}

これを見ると、検索のコストはContainsバケット内のアイテムの数に比例します。したがって、バケットの数を増やすと検索が安くなりますが、バケットの数がアイテムの数を超えると、追加のバケットの獲得はすぐに減少します。

多様なハッシュコードを持つことは、バケット内のオブジェクトを比較するための早期の役割も果たし、潜在的にコストのかかるEquals呼び出しを回避します。

要するにGetHashCode、可能な限り多様でなければなりません。その大きなスペースを適切な数のバケットに減らすのが仕事ですHashSet<T>。これは、コレクション内のアイテムの数とほぼ同じです（通常は2倍以内）。

于 2012-12-12T11:07:20.167 に答える
1

バケットの数を減らしても、パフォーマンスは向上しません。実際には、 のGetHashCodeメソッドはInt32整数値自体を返します。これは、可能な限り多くのバケットを生成するため、パフォーマンスにとって理想的です。

ハッシュ テーブルのパフォーマンスを向上させるのは、キーからハッシュ コードへの変換です。これは、コレクション内のほとんどのアイテムをすばやく削除できることを意味します。考慮する必要があるのは、同じバケット内のアイテムのみです。バケットが少ない場合は、排除できるアイテムがはるかに少ないことを意味します。

の最悪の実装でGetHashCodeは、すべてのアイテムが同じバケットに入れられます。

public override int GetHashCode() {
  return 0;
}

これはまだ有効な実装ですが、ハッシュ テーブルが通常のリストと同じパフォーマンスを得ることを意味します。つまり、一致を見つけるためにコレクション内のすべてのアイテムをループする必要があります。

于 2012-12-12T10:54:24.803 に答える