7

キーにブール配列を使用するC＃の辞書を作成しようとしています。

 Dictionary<bool[], string>

bool配列の長さは1000に固定されており、すべて同じ長さです。ハッシュコードに問題があり、「排他的論理和」の一般的な方法は、配列の長さのためにあまり意味がありません。

StackOverflowに関する同様の質問は、GetHashCodeメソッドの「排他的論理和」で解決されます。私はそれがこの文脈で機能するとは思わない。私はそれを次のように使用したいと思います：

 Dictionary<bool[], string> myDict = 
             new Dictionary<bool[], string>(EqualityComparer);

ここで、EquaityComparerは次のようなことを行います。

   public class EqualityComparer : IEqualityComparer<bool[]>
    {
        public bool Equals(bool[] x, bool[] y)
        {
            return x.SequenceEqual(y);
        }

        public int GetHashCode(bool[] x)
        {
            // this part doesn't work correctly
            int hc = x.GetHashCode();
            return hc;
        }
    }

もちろん、bool配列が可変であり、パフォーマンスに関連する派生キーのサイズに関する通常の懸念はすべてここに当てはまります...解決策はありませんが。

4

4 に答える 4

8

あなたEqualsとの両方HashCodeが正しくありません。

おそらくSequenceEqual、配列が等しいかどうかを比較するために使用するか、単純なforループを使用する必要があります。

ハッシュコードを計算するには、標準的な方法のいずれかを使用できます。2つのアイテムが等しい場合、それらは同じハッシュを持っている必要があることが非常に重要です。

例

public int GetHashCode(bool[] x)
{
    int result = 29;
    foreach (bool b in x)
    {
        if (b) { result++; }
        result *= 23;
    }
    return result;
}

関連している

于 2012-07-17T17:42:06.010 に答える
1

パフォーマンスと一貫性のためにbool[]、別のクラスに保存することをお勧めします。キーが変更されない可能性があることはすでにわかっているため、キー クラスにハッシュを格納することでこれを利用できます。ディクショナリの内部操作は、1 回のアクセスでこのハッシュを複数回使用する場合があります (ただし、内部実装の詳細を知る必要はないため、これが何度も実行される可能性があると想定するのが最善です)。

パフォーマンスのために、外部へのアクセスや参照を保持したい場合もありますbool[]が、最も安全な方法は、キー クラスで安全なコピーを作成することです。

public class BoolArrayKey
{
    private int hash;
    private bool[] data;

    public BoolArrayKey(bool[] source)
    {
        data = new bool[source.Length];
        Array.Copy(source, data, source.Length);
    }

    public override bool Equals(object obj)
    {
        BoolArrayKey other = obj as BoolArrayKey;
        if (other == null)
        {
            return false;
        }

        return other.data.SequenceEqual(data);
    }

    public override int HashCode()
    {
        if (hash == 0)
        {
            // Mark's hash implementation here, store the result in `hash`.
        }

        return hash;    
    }
}

頻繁に 0 のハッシュ値が予想される場合は、別のbool変数を使用して値が計算されたかどうかを示すことができます。

于 2012-07-17T19:33:09.900 に答える
0

最高のパフォーマンスを得るには、ハッシュと比較が非常に遅くなる bool[] 配列を使用しないでください。たとえば、同じ情報を 1/32 の長さの Uint32[] 配列に格納すると、ハッシュと比較がはるかに高速になります。

bool[] 配列を保持する場合は、ハッシュ/比較に安全でないコードを使用することを検討してください。

安全なコードのみを使用する場合は、少なくともループ内の条件を削除します。

hash = hash * 3 + (int) x[i];

また、独自のループを使用して比較すると、SequenceEqual よりも高速になるはずです

于 2012-07-17T18:39:45.363 に答える
0

GetHashCode を実装するためのルールは、等しい 2 つのオブジェクトは同じハッシュ コードを生成する必要があるということです。1 つのガイドラインは、衝突をできるだけ少なくすることです (ハッシュ コードが一意である必要はありません)。

この実装では、BitArray クラスを使用してブール配列を 32 個のグループで取得し、それらをビットとして扱い、結果の 32 ビット整数のハッシュ コードを計算します。

public int GetHashCode(bool[] x)
{
    // Trivial case
    if (x.Length == 0) return 0;

    // Convert the bool array to a BitArray to use framework functions
    BitArray binary = new BitArray(x);

    //Determine the max # of 32-bit INTS this array represents
    int intLength = (x.Length-1)/32 + 1;
    int [] ints = new int[intLength];

    // Copy each block of 32-bits to an int
    binary.CopyTo(ints, 0);

    // Take the exclusive OR of each int and return the result's hash code
    return ints.Aggregate((i1, i2) => i1 ^ i2).GetHashCode();
}
于 2012-07-17T18:42:34.413 に答える