1

編集:64ビットまたは128ビットも機能します。私の脳は、それで十分だと思って、何らかの理由で32ビットにジャンプしました。

主に数値(int、decimal)と、それぞれ12文字を超えることのない3つの文字列で構成される構造体があります。ハッシュコードとして機能する整数値を作成し、すばやく作成しようとしています。一部の数値もnull許容です。

BitVector32またはBitArrayは、この取り組みで使用するのに便利なエンティティのようですが、このタスクでそれらを自分の意志に合わせて曲げる方法がわかりません。私の構造には、3つの文字列、12の小数(そのうち7つはnull許容)、および4つのintが含まれています。

私のユースケースを単純化するために、次の構造体があるとしましょう。

public struct Foo
{
    public decimal MyDecimal;
    public int? MyInt;
    public string Text;
}

各値の数値識別子を取得できることはわかっています。MyDecimalとMyIntは、数値の観点からはもちろんユニークです。また、文字列にはGetHashCode()関数があり、通常は一意の値を返します。

では、それぞれに数値の識別子を使用して、この構造を一意に識別するハッシュコードを生成することは可能ですか?たとえば、同じ値を含む2つの異なるFooを比較し、毎回同じハッシュコードを取得できます(アプリのドメイン、アプリの再起動、時刻、木星の衛星の配置などに関係なく)。

ハッシュはまばらであるため、ユースケースからの衝突は予想されません。

何か案は?最初に実行したときは、すべてを文字列表現に変換して連結し、組み込みのGetHashCode()を使用しましたが、それはひどく...非効率的です。

編集:もう少し背景情報。構造データはWebクライアントに配信されており、クライアントは含まれている値の多くの計算、文字列の構成などを実行してページを再レンダリングします。前述の19のフィールド構造は、単一の情報ユニットを表しており、各ページには多くのユニットが含まれる可能性があります。レンダリングされた結果のクライアント側のキャッシュを実行したいので、サーバーから同じハッシュ識別子が表示された場合、クライアント側で再計算せずにユニットをすばやく再レンダリングできます。JavaScriptの数値はすべて64ビットなので、32ビットの制約は人為的で制限的なものだと思います。64ビットは機能しますが、サーバー上で2つの64ビット値に分割できれば128ビットでも機能すると思います。

4

5 に答える 5

3

まばらなテーブルであっても、「まばら」が何を意味するかに応じて、衝突に備える必要があります。

ハッシュ衝突確率 (一様分布)

このグラフを 32 ビットで打ち負かすには、同時にハッシュするデータについて非常に具体的な仮定を立てることができる必要があります。

SHA256 を使用します。ハッシュは CLR のバージョンに依存せず、衝突もありません。まあ、まだいくらかはありますが、隕石の影響よりも頻度が低いので、何も予測しない余裕があります.

于 2012-04-26T20:42:51.210 に答える
1

ハッシュ関数の定義によるハッシュコードは、一意であることを意味するものではありません。これらは、すべての結果値に可能な限り均等に分散されることのみを目的としています。オブジェクトのハッシュコードを取得することは、2つのオブジェクトが異なるかどうかをすばやく確認する方法です。2つのオブジェクトのハッシュコードが異なる場合、それらのオブジェクトは異なります。ただし、ハッシュコードが同じである場合は、確実にオブジェクトを深く比較する必要があります。ハッシュコードの主な用途は、ほぼO(1)の取得速度を可能にするすべてのハッシュベースのコレクションです。

したがって、この観点から、GetHashCode複雑である必要はなく、実際には複雑であってはなりません。非常に高速であることと、均等に分散された値を生成することの間でバランスを取る必要があります。ハッシュコードを取得するのに時間がかかりすぎると、ディープ比較に対する利点がなくなるため、意味がなくなります。もう一方の極端な場合、ハッシュコードは常に1たとえば(高速に点灯)、すべての場合で深い比較につながり、このハッシュコードも無意味になります。

したがって、バランスを正しく取り、完璧なハッシュコードを考え出そうとしないでください。すべて(またはほとんど)のメンバーを呼び出し、演算子GetHashCodeを使用して結果を組み合わせます。ビット単位のシフト演算子またはを使用することもできます。フレームワークの種類は非常に最適化されていますが、各アプリケーションの実行で同じであるとは限りません。保証はありませんが、変更する必要はなく、多くの場合変更されません。リフレクターを使用して、反映されたコードに基づいて独自のバージョンを確認または作成します。Xor<<>>GetHashCode

あなたの特定のケースでは、ハッシュコードを見るだけで構造をすでに処理したかどうかを判断するのは少し危険です。ハッシュが優れているほどリスクは小さくなりますが、それでもリスクは小さくなります。究極で唯一のユニークなハッシュコードは...データそのものです。Object.Equalsハッシュコードを操作するときは、コードが本当に信頼できるものになるようにオーバーライドする必要もあります。

于 2012-04-26T21:22:17.140 に答える
1

ここここを見てみることをお勧めします。32ビットだけで衝突が発生しないことを保証できるとは思いません。

于 2012-04-26T20:06:35.680 に答える
0

.NET での通常の方法は、構造体の各メンバーで GetHashCode を呼び出し、結果を xor することだと思います。

ただし、GetHashCode が異なるアプリ ドメインで同じ値に対して同じハッシュを生成すると主張しているとは思いません。

このハッシュ値が必要な理由と、時間の経過とともに安定している必要がある理由、さまざまなアプリドメインなどについて、質問にもう少し情報を提供していただけますか.

于 2012-04-26T20:11:01.320 に答える
0

あなたはどんなゴールを目指していますか?パフォーマンスの場合は、構造体を関数パラメーターとして渡すたびに値によってコピーされるため、クラスを使用する必要があります。

3 つの文字列、12 の小数 (うち 7 は null 可能)、および 4 つの整数。

64 ビット マシンでは、ポインターのサイズは 8 バイトになり、10 進数は 16 バイト、int は 4 バイトになります。パディングを無視すると、構造体はインスタンスごとに 232 バイトを使用します。これは、推奨される最大値である 16 バイトと比較してはるかに大きく、これはパフォーマンス的に理にかなっています (クラスは、そのオブジェクト ヘッダーのために少なくとも 16 バイトを必要とします...)。

値のフィンガープリントが必要な場合は、16 バイトのフィンガープリントを生成する SHA256 などの暗号化グレードのハッシュ アルゴを使用できます。これはまだユニークではありませんが、少なくとも十分にユニークです。しかし、これはかなりのパフォーマンスも犠牲にします。

Edit1: Java Script Web クライアント キャッシュ内のオブジェクトを識別するためにハッシュ コードが必要であることを明らかにした後、私は混乱しています。サーバーが同じデータを再度送信するのはなぜですか? クライアントがまだ受信していないデータのみを送信するようにサーバーをよりスマートにする方が簡単ではないでしょうか?

あなたの場合、SHAハッシュアルゴリズムは、オブジェクトインスタンスタグを作成するのに問題ありません。


なぜハッシュコードが必要なのですか? メモリ効率の良い方法で値を格納することが目標である場合は、辞書を使用して同一の値を 1 回だけ格納し、検索キーとして int を使用する FooList を作成できます。

using System;
using System.Collections.Generic;

namespace MemoryEfficientFoo
{
    class Foo // This is our data structure 
    {
        public int A;
        public string B;
        public Decimal C;
    }

    /// <summary>
    /// List which does store Foos with much less memory if many values are equal. You can cut memory consumption by factor 3 or if all values 
    /// are different you consume 5 times as much memory as if you would store them in a plain list! So beware that this trick
    /// might not help in your case. Only if many values are repeated it will save memory.
    /// </summary>
    class FooList : IEnumerable<Foo> 
    {
        Dictionary<int, string> Index2B = new Dictionary<int, string>();
        Dictionary<string, int> B2Index = new Dictionary<string, int>();

        Dictionary<int, Decimal> Index2C = new Dictionary<int, decimal>();
        Dictionary<Decimal,int> C2Index = new Dictionary<decimal,int>();

        struct FooIndex
        {
            public int A;
            public int BIndex;
            public int CIndex;
        }

        // List of foos which do contain only the index values to the dictionaries to lookup the data later.
        List<FooIndex> FooValues = new List<FooIndex>();

        public void Add(Foo foo)
        {
            int bIndex;
            if(!B2Index.TryGetValue(foo.B, out bIndex))
            {
                bIndex = B2Index.Count;
                B2Index[foo.B] = bIndex;
                Index2B[bIndex] = foo.B;
            }

            int cIndex;
            if (!C2Index.TryGetValue(foo.C, out cIndex))
            {
                cIndex = C2Index.Count;
                C2Index[foo.C] = cIndex;
                Index2C[cIndex] = cIndex;
            }

            FooIndex idx = new FooIndex
            {
                A = foo.A,
                BIndex = bIndex,
                CIndex = cIndex
            };

            FooValues.Add(idx);
        }

        public Foo GetAt(int pos)
        {
            var idx = FooValues[pos];
            return new Foo
            {
                A = idx.A,
                B = Index2B[idx.BIndex],
                C = Index2C[idx.CIndex]
            };
        }

        public IEnumerator<Foo> GetEnumerator()
        {
            for (int i = 0; i < FooValues.Count; i++)
            {
                yield return GetAt(i);
            }
        }
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            FooList list = new FooList();
            List<Foo> fooList = new List<Foo>();
            long before = GC.GetTotalMemory(true);
            for (int i = 0; i < 1000 * 1000; i++)
            {
                list
                //fooList
                    .Add(new Foo
                    {
                        A = i,
                        B = "Hi",
                        C = i
                    });

            }
            long after = GC.GetTotalMemory(true);
            Console.WriteLine("Did consume {0:N0}bytes", after - before);
        }
    }
}

同様のメモリ節約リストがここにあります

于 2012-04-26T21:13:33.533 に答える