プログラマーの修道仙の道--ユーザーのアクセス記録を極めて最適化

野菜のように苦労しないでください.
年末ボーナスのない日にも、仕事は続きます.....1枚の氷と火の図は仕方がない.
料理が少し前にデザインされたユーザースペースを覚えていますか?見たことがない学生は転送ドアに入ってください=』高性能訪問者記録システムを設計します
何か残った問題を覚えていますか.メニューを繰り返して、ユーザーアクセスレコードのキャッシュに現在のユーザーのレコードがあるかどうかをどう判断しますか?チェーンテーブルは、ビジネスシーンで最も主要なデータ構造ですが、現在のこの問題の最良の解決策ではありません.そのため、要素に迅速にアクセスできるデータ構造が必要です.それは今日お話しするハッシュリストです
ハッシュ・リスト
ハッシュテーブルとも呼ばれるハッシュテーブル(Hash table)は、キー値(Key value)に基づいて直接アクセスするデータ構造である.つまり、キー値をテーブルの1つの場所にマッピングすることでレコードにアクセスし、検索を高速化します.このマッピング関数をハッシュ関数と呼び,記録を格納する配列をハッシュリストと呼ぶ.
ハッシュ・テーブルは、私たちがよく言うKey-Value形式にほぼ等しいことができます.
ハッシュ・テーブルは、配列が下付きでランダムにデータにアクセスする特性をサポートするため、ハッシュ・リストは配列の拡張であり、配列によって進化している.配列がなければ,ハッシュリストはないといえる.なぜ配列を使うのですか?配列が下付き文字で要素にアクセスする時間の複雑さがO(1)であるため、わからない学生は野菜の以前の配列に関する文章を参考にすることができる.配列の下付き文字で要素にアクセスする以上、Keyを下付き文字に変換する方法も考えなければならない.これは次に述べるハッシュ関数である.
ハッシュ関数
ハッシュ関数は一般的には,1つのKeyを配列の下にあるブラックボックスに変換することである.ハッシュ関数は、ハッシュ・リストで非常に重要な役割を果たします.ハッシュ関数は、その名の通り、関数です.これをhash(key)と定義することができ、keyは要素のキー値を表し、hash(key)の値はハッシュ関数で計算されたハッシュ値を表す.ハッシュ関数にはどのような要件がありますか?

ハッシュ関数で計算された値は、非負の整数値です.

key 1=key 2の場合hash(key 1)==hash(key 2)

key 1≠key 2の場合hash(key 1)≠hash(key 2)

簡単に言えば以上の3点、第1点:ハッシュ値は実は配列の下付き文字なので、だから非負の整数でなければなりません(>=0)、2番目:同じkeyで計算されるハッシュ値は同じでなければなりません.3番目の点に重点を置いて言えば、実は3番目の点は理論的なもので、異なるKeyで得られるハッシュ値は異なるはずだと想像していますが、実際には、この点は難しいです.この式が成立すれば、無限のKeyのハッシュ値を計算します.ハッシュリストの下部の数グループは無限大にしなければならない.業界で有名なMD 5やSHAなどのハッシュアルゴリズムも、このような衝突を完全に避けることはできない.もちろん,下位層の配列が小さいほど,この衝突の確率は大きくなる.したがって、完璧なハッシュ関数は実際には存在しません.存在しても、時間コストがかかり、人件費は想像を超える可能性があります.
ハッシュの競合
どんなに良いハッシュ関数でもハッシュ競合を回避できない以上、この問題を解決するために他の方法を探さなければなりません.

アドレス

もし衝突したらどうしますか?方法の1つは、衝突した位置で配列内の空きスペースを探し始め、空きスペースを見つけて挿入することです.お店に買い物に行って、売り切れたことに気づいたら、どうしますか.次の売っている店を探して買いましょう.いずれのプローブ法を用いても,ハッシュ内の空き位置が多くない場合,ハッシュ競合の確率が大幅に向上する.ハッシュ・リストの操作効率を可能な限り保証するために、一般的には、ハッシュ・リストに一定の割合の空きスロットがあることを可能な限り保証します.空格子点の数をロードファクタ(load factor)で表した.
ハッシュ・リストのマウント・ファクタ=表に埋め込まれた要素の数/ハッシュ・リストの長さ
ロードファクタが大きいほど、空き位置が少ないほど衝突が多くなり、ハッシュのパフォーマンスが低下することを示す.ハッシュ関数をf=(key%1000)と仮定し、下図に示すように

チェーンアドレス法(ファスナー法)

ファスナー法は最もよく用いられるハッシュ値の衝突を解決する方法に属する.基本的な考え方は,配列の各要素がチェーンテーブルを指し,ハッシュ値が衝突するとチェーンテーブルの末尾に新しい要素が増加することである.検索時と同様に、ハッシュ値に基づいて配列位置にナビゲートした後、チェーンテーブルに沿って要素を検索します.ハッシュ関数の設計が非常に悪い場合,同じハッシュ値が非常に多い場合,ハッシュテーブル要素の検索はチェーンテーブル検索に劣化し,時間的複雑度はO(n)に劣化する.

再ハッシュ法

この方法は本質的に複数回のハッシュ値を計算するので、必然的に複数のハッシュ関数が必要であり、衝突が発生すると別のハッシュ関数を使用してハッシュ値を計算し、衝突が発生しなくなるまで、この方法では「集約」は発生しにくいが、計算時間が増加する.

共通オーバーフロー領域

を確立する
このシナリオについては,ネットワーク上で紹介されているものが少なく,一般に応用されているものも少ない.ハッシュ値が競合する要素は別のコンテナに配置され、もちろんコンテナの選択は配列であり、チェーンテーブルでもキューでも可能である.しかし、何であれ、ハッシュリストの利点を保証するには、この容器の選択を慎重に考慮する必要があります.
拡張読書

ここでは一度強調する必要があります.ハッシュ・テーブルの最下位は、配列が下付きでアクセスされる特性(時間的複雑度O)に依存します.(1))、また、一般的なハッシュは、大量の衝突を避けるためにロードファクタの定義があり、これは、新しい配列に空間を開く必要があり、要素copyを新しい配列に割り当てる必要がある配列拡張の特性に関連している.データの記憶量やデータの大体の記憶量を知っていれば、ハッシュを初期化する際に、できるだけ一度に十分な空間を割り当てることができる.その後の配列拡張の弊害を避ける.メモリが緊張している場合、このような使い捨て割り当てを優先する案も他の案よりずっと良いことが証明されています.

ハッシュ・リストのアドレス・スキームには、配列の末尾に空き位置がない場合、どうすればいいのでしょうか.これはループチェーンテーブルを思い出させ、配列も同じで、ループ配列を組み立てることができます.末尾に空席がなければ、配列の先頭で検索を続けることができます.

ハッシュ・テーブル要素の削除については、説明する必要があると思います.まずファスナー方式に基づくハッシュリストは、要素がチェーンテーブルにあるため、1つの要素を削除する時間の複雑さはチェーンテーブルと同じであり、後続の検索にも問題はありません.しかし、アドレス方式のハッシュテーブルは異なり、位置N要素を削除すると、N位置が空の位置になっているため、N以降の同じハッシュ値の要素は検索できないと仮定します.ハッシュリストの検索方式が空の位置を决めた后の要素は断片化しました....これもファスナーベースのハッシュリストが一般的に使われる理由の一つでしょう.

工業クラスのハッシュ関数では、元素のハッシュ値をできるだけ平均的に分布させることが要求の一つであり、これは空間の十分な利用のためだけでなく、大量のhashCodeが同じ位置に落ちることを防止するためでもあり、ファスナー方式の極端な場合には、1つの要素を検索する時間的複雑度は、チェーンテーブル内の要素を検索する時間的複雑度O(n)に劣化し、これにより、ハッシュリストの最大特性が失われる.

ファスナー方式で実現されたチェーンテーブルの中で、実は私は双方向チェーンテーブルを使用する傾向があり、このように1つの要素を削除する際に、双方向チェーンテーブルの優位性を同時に発揮することができ、このようにハッシュリストの要素を削除する時間の複雑さをO(1)に低下させることができる.

ハッシュ・リストでは、要素の位置がハッシュ関数によって決定されるため、1つのハッシュ・リストを巡るすべての場合、要素の順序は要素を追加する前後の順序ではありません.この点は、具体的なビジネス・アプリケーションで注意する必要があります.

Net Core c#コード
いくつかの場所で料理を強調する必要があります.

現在のプロジェクトで使用されている分散フレームワークは、Actorモデルに基づくOrleansなので、各ユーザーのアクセスレコードはマルチスレッドの問題を心配する必要はありません.

私がhashtableというデータコンテナを使用しなかったのは、hashtableが梱包・解体の問題が発生しやすいからです.

双方向チェーンテーブルを使用するのは、現在の要素が検出されたためであり、前の要素と次の要素も検出されたことに相当し、現在の要素の削除操作時間の複雑さはO(1)

であることができる.
ユーザー・アクセス・レコードのエンティティ

 class UserViewInfo
    {
        //  ID
        public int UserId { get; set; }
        //    ，utc   
        public int Time { get; set; }
        //    
        public string UserName { get; set; }
    }

ユーザースペースアクセスレコードのコードの追加

class UserSpace
    {
        //       
        const int CacheLimit = 1000;
        //                   
        LinkedList cacheUserViewInfo = new LinkedList();
        //         Dictionary       ，      ，               ，      
        Dictionary dicUserView = new Dictionary(1250);

        //         
        public void AddUserView(UserViewInfo uv)
        {
            //             ，  hashtable       
            if (dicUserView.TryGetValue(uv.UserId, out UserViewInfo currentUserView))
            {
                //    ，                  ，      
                cacheUserViewInfo.Remove(currentUserView);
                cacheUserViewInfo.AddFirst(currentUserView);
            }
            else
            {
                //     ，                 
                cacheUserViewInfo.AddFirst(uv);
                dicUserView.Add(uv.UserId, uv);
            }
            //                 
            if (cacheUserViewInfo.Count > CacheLimit)
            {
                //          ，  hashtable   ,     ，dictionary                 ，                O（1）
                var lastItem = cacheUserViewInfo.Last.Value;
                dicUserView.Remove(lastItem.UserId);
                cacheUserViewInfo.RemoveLast();
            }
        }
    }

注目を追加し、より美しいバージョンを表示し、より素晴らしいものを得る