ハッシュテーブルアルゴリズムの最初から最後までの徹底的な分析

注: この記事は 3 つの部分に分かれています。最初の部分は、Baidu の面接の質問における Top K アルゴリズムの詳細な説明です。2 番目の部分は、ハッシュテーブルアルゴリズムの詳細な説明です。3 番目の部分は、最速のハッシュテーブルアルゴリズムの作成です。

パート1: Top Kアルゴリズムの詳細な説明

問題の説明

Baidu のインタビューの質問:

検索エンジンは、ユーザーが各検索で使用したすべての検索文字列をログファイルに記録します。各クエリ文字列の長さは 1 ～ 255 バイトです。
レコードが 1,000 万件あると仮定します (これらのクエリ文字列は繰り返し度が高いです。合計数は 1,000 万ですが、重複を除いた後では 300 万を超えることはありません。クエリ文字列の繰り返し率が高いほど、より多くのユーザーがクエリを実行し、人気があることを意味します)。最も人気のある 10 個のクエリ文字列をカウントしてください。使用されるメモリは 1G を超えてはなりません。

必要な知識:

ハッシュテーブルとは何ですか?

ハッシュテーブル (ハッシュテーブルとも呼ばれます) は、キー値に基づいて直接アクセスされるデータ構造です。つまり、キーコード値をテーブル内の場所にマッピングしてレコードにアクセスし、検索を高速化します。このマッピング関数はハッシュ関数と呼ばれ、レコードを格納する配列はハッシュテーブルと呼ばれます。

ハッシュテーブルの方法は、実は非常に簡単です。ハッシュ関数と呼ばれる固定アルゴリズム関数を使用してキーを整数に変換し、その整数の係数を配列の長さで計算します。係数の結果は配列の添え字として使用され、その数値を添え字として配列スペースに値が格納されます。

ハッシュテーブルをクエリに使用する場合、ハッシュ関数を再度使用してキーを対応する配列インデックスに変換し、スペースを見つけて値を取得します。このようにして、配列の位置決め性能を最大限に活用してデータを検索できます（記事の第2部と第3部ではハッシュテーブルについて詳しく説明します）。

問題分析:

最も人気のあるクエリをカウントするには、まず各クエリの出現回数をカウントし、次に統計結果に基づいて上位 10 件を見つけます。したがって、このアイデアに基づいて 2 つのステップでアルゴリズムを設計できます。

つまり、この問題の解決は次の2 つのステップに分かれます。

ステップ1: 統計を照会する

クエリ統計には 2 つの方法があります。

1. 直接ソート法

最初に思い浮かぶアルゴリズムはソートです。まず、ログ内のすべてのクエリをソートし、ソートされたクエリを走査して、各クエリの出現回数をカウントします。

しかし、質問には明確な要件があり、メモリは 1G を超えてはいけません。レコードは 1,000 万件あり、各レコードは 255Byte です。明らかに、2.375G のメモリを占有します。この条件は要件を満たしていません。

データ構造コースで学んだことを思い出してみましょう。データ量が多くてメモリに収まらない場合は、外部ソートを使用してソートできます。マージソートは O(NlgN) というより優れた時間計算量を持つため、ここでマージソートを使用できます。

ソート後、すでに順序付けされたクエリファイルを走査し、各クエリの出現回数をカウントして、ファイルに再度書き込みます。

包括的な分析により、ソートの時間計算量は O(NlgN)、トラバーサルの時間計算量は O(N) であることが示され、アルゴリズムの全体的な時間計算量は O(N+NlgN)=O(NlgN) となります。

2. ハッシュテーブル方式

最初の方法では、ソートを使用して各クエリの出現回数をカウントしました。時間計算量は NlgN です。では、より低い時間計算量でこれを保存するより良い方法はあるでしょうか?

タイトルには、1,000 万のクエリがあるものの、重複度が高いため、実際には 255 バイトのクエリが 300 万しかないと書かれています。したがって、これらすべてをメモリに格納することを検討できます。次に必要なのは、適切なデータ構造だけです。ここでは、ハッシュテーブルが間違いなく最初の選択肢です。ハッシュテーブルのクエリ速度は非常に速く、時間の計算量はほぼ O(1) です。

次に、アルゴリズムについて説明します。キーをクエリ文字列、値をクエリの出現回数としてハッシュテーブルを維持します。クエリが読み取られるたびに、文字列がテーブルにない場合は文字列を追加して値を 1 に設定します。文字列がテーブルにある場合は、文字列のカウントを 1 増やします。最終的に、この膨大なデータの処理をO(N)の時間計算量内で完了しました。

アルゴリズム 1 と比較すると、この方法では時間計算量が 1 桁改善されて O(N) になりますが、これは時間計算量に関する最適化だけではありません。この方法ではデータファイルの IO が 1 回だけ必要ですが、アルゴリズム 1 ではより多くの IO 時間が必要です。したがって、アルゴリズム 2 はアルゴリズム 1 よりもエンジニアリングで操作しやすいと言えます。

ステップ2: トップ10を見つける

アルゴリズム1: 通常のソート

ソートアルゴリズムについては皆さんよくご存知だと思いますので、ここでは詳しく説明しません。注目すべきは、ソートアルゴリズムの時間計算量は NlgN であるということです。この問題では、1G のメモリを使用して 300 万件のレコードを保存できます。

アルゴリズム 2: 部分ソート

質問では上位 10 件を見つける必要があるため、すべてのクエリを並べ替える必要はありません。必要なのは、10 個の配列を維持し、10 個のクエリを初期化し、各クエリの統計数に従って大きいものから小さいものに並べ替え、300 万件のレコードを走査することだけです。レコードが読み取られるたびに、配列の最後のクエリと比較されます。このクエリより小さい場合は走査を続行し、そうでない場合は配列の最後のデータを削除して現在のクエリに追加します。最後に、すべてのデータが走査されると、この配列内の 10 個のクエリが、探している上位 10 個になります。

この方法では、アルゴリズムの最悪の時間計算量はN*K （ K は最大の数字を指す）であることを分析するのは難しくありません。

アルゴリズム3: ヒープ

アルゴリズム 2 では、時間の計算量を NlogN から NK に最適化しました。これは大きな改善だと言わざるを得ませんが、もっと良い方法はあるのでしょうか?

分析してみましょう。アルゴリズム 2 では、各比較が完了した後、要素を線形リストに挿入する必要があり、順次比較が使用されるため、必要な操作の複雑さは K です。ここで注目すべきは、配列が順序付けられており、検索するたびにバイナリ検索法を使用できるため、操作の複雑さが logK に削減されることです。ただし、データの移動回数が増えるため、データの移動に問題が生じます。ただし、このアルゴリズムはアルゴリズム 2 よりも改善されています。

以上の分析を踏まえて考えてみましょう。要素を素早く検索し、素早く移動できるデータ構造はあるでしょうか?答えは「はい」です。それは山積みです。

ヒープ構造の助けを借りて、対数時間で検索および調整/移動を行うことができます。したがって、私たちのアルゴリズムは、この点まで改善することができます。サイズ K (この質問では 10) の小さなルートヒープを維持し、300 万のクエリを走査して、それぞれルート要素と比較します。

考え方は上記のアルゴリズム 2 と同じですが、アルゴリズム 3 では配列の代わりに最小ヒープデータ構造を使用し、対象要素の検索にかかる時間の計算量を O(K) から O(logK) に削減します。

次に、ヒープデータ構造を使用することで、アルゴリズム 3 の最終的な時間計算量はN'logKに削減され、これはアルゴリズム 2 と比較して大幅な改善となります。

要約:

この時点で、アルゴリズムは完全に終了しています。上記の最初のステップの後、ハッシュテーブルを使用して各クエリの出現回数をカウントします (O (N))。次に、2 番目のステップでは、ヒープデータ構造を使用して上位 10 件を検索します (N*O (logK))。したがって、最終的な時間計算量はO(N) + N'*O(logK) となります。 (N は 1000 万、N' は 300 万です)。もっと良いアルゴリズムがあれば、コメントを残してください。パート１、終了。

#p#

パート2: ハッシュテーブルアルゴリズムの詳細な分析

ハッシュとは

ハッシュは、一般的に「ハッシュ」と翻訳され、「ハッシュ」と直接書き起こされることもあります。ハッシュは、ハッシュアルゴリズムを使用して、任意の長さの入力 (プレマッピング、プレイメージとも呼ばれます) を固定長の出力に変換します。出力はハッシュ値です。この変換は圧縮マッピングです。つまり、ハッシュ値のスペースは通常、入力のスペースよりもはるかに小さく、異なる入力が同じ出力にハッシュされる可能性があり、ハッシュ値から入力値を一意に特定することは不可能です。簡単に言えば、任意の長さのメッセージを固定長のメッセージダイジェストに圧縮する機能です。

HASH は主に情報セキュリティ暗号化アルゴリズムの分野で使用され、長さの異なる情報をランダムな 128 ビットコードに変換します。これらのコード値は HASH 値と呼ばれます。言い換えれば、ハッシュはデータの内容とデータストレージアドレス間のマッピング関係を見つけることです。

配列の特性は、アドレス指定は簡単ですが、挿入と削除は難しいことです。一方、リンクリストの特性は、アドレス指定は難しいですが、挿入と削除は簡単です。では、両方の特性を組み合わせて、アドレス指定しやすく、挿入や削除も簡単なデータ構造を作成できるでしょうか?答えはイエスです。これが、これから説明するハッシュテーブルです。ハッシュテーブルを実装する方法は数多くあります。次に説明するのは、最も一般的に使用されるジッパーメソッドです。これは、図に示すように、「リンクされたリストの配列」として理解できます。

左側は明らかに配列です。配列の各メンバーには、リンクリストの先頭へのポインターが含まれています。もちろん、このリンクリストは空の場合もあれば、多くの要素が含まれる場合もあります。要素のいくつかの特性に基づいて要素を異なるリンクリストに割り当て、これらの特性に基づいて正しいリンクリストを見つけて、リンクリストから要素を見つけます。

要素の特性を配列の添え字に変換する方法はハッシュと呼ばれます。もちろん、ハッシュ方法は複数あります。ここでは、よく使用される 3 つの方法を紹介します。

1. 除算ハッシュ

最も直感的なのは、上の図で使用されているハッシュ方式です。式は次のとおりです。

インデックス = 値 % 16

アセンブリを勉強した人なら誰でも、係数は実際には除算演算によって得られることを知っているので、「除算ハッシュ方式」と呼ばれます。

2. スクエアハッシュ法

インデックスの検索は非常に頻繁に行われる操作であり、乗算は除算よりも時間の節約になります (現在の CPU では、おそらくそれを実感できないでしょう)。そのため、除算を乗算とシフト操作に置き換えることを検討します。式：

index = (値 * 値) >> 28 (右にシフトして、2^28 で割ります。表記: 左にシフトすると増加し、乗算になります。右にシフトすると減少し、除算になります。 )

この方法は、値が均等に分散されている場合は良い結果を生成できますが、上で描いたグラフの各要素のインデックスは 0 であり、完全に失敗しています。まだ疑問が残るかもしれませんが、値が非常に大きい場合、値 * 値はオーバーフローしませんか?答えは「はい」ですが、乗算ではオーバーフローは考慮されません。乗算結果を取得しようとしているのではなく、インデックスを取得しようとしているからです。

3. フィボナッチハッシュ

平方ハッシュ法の欠点は明らかなので、値自体を乗数として取るのではなく、理想的な乗数を見つけることはできるでしょうか?答えはイエスです。

1、16ビット整数の場合、この乗数は40503です。

2. 32ビット整数の場合、この乗数は2654435769です。

3. 64ビット整数の場合、この乗数は11400714819323198485です。

これらの「理想的な乗数」はどのようにして導き出されるのでしょうか?これは黄金比の法則と呼ばれる法則に関連しており、黄金比の法則を説明する最も古典的な表現は間違いなく有名なフィボナッチ数列であり、次の形式の数列です: 0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946、…さらに、フィボナッチ数列の値は、太陽系の8つの惑星の軌道半径の比率と驚くほど一致しています。

一般的な 32 ビット整数の場合、式は次のようになります。

インデックス = (値 * 2654435769) >> 28

このフィボナッチハッシュ法を使用すると、上の図は次のようになります。

明らかに、フィボナッチハッシュ法は元のハッシュ法よりもはるかに優れています。

適用範囲

高速な検索と削除のための基本的なデータ構造では、通常、データの合計量がメモリに収まることが求められます。

基本原則とポイント

ハッシュ関数の選択、文字列、整数、配列の特定のハッシュメソッド。

衝突処理には、ジッパー方式とも呼ばれるオープンハッシュと、オープンアドレッシング方式とも呼ばれるクローズドハッシュの 2 種類があります。

拡張機能

d-左ハッシュの d は複数を意味します。問題を単純化して、2-左ハッシュを見てみましょう。 2 左ハッシュとは、ハッシュテーブルを T1 と T2 と呼ばれる同じ長さの 2 つの半分に分割し、T1 と T2 にそれぞれハッシュ関数 h1 と h2 を装備することを指します。新しいキーを保存するときに、2つのハッシュ関数を同時に使用して、2つのアドレスh1[key]とh2[key]を計算して取得します。このとき、T1 の h1[key] の位置と T2 の h2[key] の位置をチェックして、どちらの位置に (衝突する) キーがより多く格納されているかを確認し、負荷の少ない位置に新しいキーを格納する必要があります。両側に同じ数の位置がある場合、たとえば、両方の位置が空であるか、両方にキーが格納されている場合、新しいキーは左側の T1 サブテーブルに格納され、2-left がそこから得られます。キーを検索するときは、キーを 2 回ハッシュし、同時に 2 つの場所を検索する必要があります。

問題例（大量データ処理）

ハッシュテーブルは大量のデータ処理に広く使用されていることは知られています。以下に、Baidu の面接での別の質問を示します。

タイトル: 膨大なログデータから、特定の日に Baidu に最も多くアクセスした IP アドレスを抽出します。

解決策: IP の数は依然として最大 2^32 に制限されているため、ハッシュを使用して IP をメモリに直接保存し、統計を実行することを検討できます。

#p#

パート 3: 最速のハッシュテーブルアルゴリズム

次に、最速の Hasb テーブルアルゴリズムを詳しく分析してみましょう。

まず、簡単な質問から始めます。膨大な数の文字列の配列があり、1 つの文字列が与えられ、その文字列が配列内に存在するかどうかを調べて見つけるように求められます。あなたならどうしますか? 一番簡単な方法は、最初から最後まで正直に検索し、見つかるまで一つずつ比較することです。プログラミングを学んだ人なら誰でもそのようなプログラムを作ることができると思いますが、プログラマーがそのようなプログラムをユーザーに提供した場合、私は言葉を失いながら評価することしかできません。本当に機能するかもしれませんが...それだけです。

最も適切なアルゴリズムは、当然、ハッシュテーブルを使用することです。まずは基本的な知識を紹介しましょう。いわゆるハッシュは一般的に整数です。特定のアルゴリズムにより、文字列を整数に「圧縮」することができます。もちろん、32 ビットの整数を文字列にマッピングすることはできませんが、プログラムでは、2 つの文字列によって計算されたハッシュ値が等しい確率は非常に小さくなります。MPQ のハッシュアルゴリズムを見てみましょう。

関数1:次の関数は、長さ0×500（10進数：1280）のcryptTable[0x500]を生成します。

 void暗号化テーブルの準備()
 {
    符号なしlongシード = 0x00100001 、インデックス1 = 0 、インデックス2 = 0 、i; 
   
 (インデックス1 = 0 ; インデックス1 < 0x100 ; インデックス1++ )
    {
 (インデックス2 = インデックス1、 i = 0 ; i < 5 ; i++、 インデックス2 += 0x100 )
        {
            符号なしロングtemp1、temp2; 
   
            シード = (シード * 125 + 3 ) % 0x2AAAAB ;
            temp1 = (シード & 0xFFFF ) << 0x10 ; 
   
            シード = (シード * 125 + 3 ) % 0x2AAAAB ;
            temp2 = (シード & 0xFFFF ); 
   
            cryptTable[index2] = ( temp1 | temp2 );
       }
   }
 }

関数 2:次の関数は、lpszFileName 文字列のハッシュ値を計算します。ここで、dwHashType はハッシュのタイプです。この関数は次の関数 3 : GetHashTablePos 関数で呼び出され、その可能な値は 0、1、および 2 です。この関数は、lpszFileName 文字列のハッシュ値を返します。

符号なしロングハッシュ文字列( char *lpszFileName, 符号なしロングdwHashType )
 {
    符号なし文字*key = (符号なし文字*)lpszFileName;
符号なしロングシード1 = 0x7FED7FED ;
符号なしロングシード2 = 0xEEEEEEEE ;
整数ch; 
   
 ( *キー != 0 )の間
    {
        ch = toupper(*key++); 
   
        シード1 = cryptTable[(dwHashType &lt;&lt; 8 ) + ch] ^ (シード1 + シード2);
        シード2 = ch + シード1 + シード2 + (シード2 &lt;&lt; 5 ) + 3 ;
    }
 seed1を返します。
 }

Blizzard のアルゴリズムは非常に効率的で、「一方向ハッシュ」と呼ばれます (一方向ハッシュは、元の文字列 (実際には文字列のセット) を導出することが事実上不可能になるように構築されたアルゴリズムです)。たとえば、このアルゴリズムを使用すると、文字列「unitneutralacritter.grp」は 0xA26067F3 として評価されます。

最初のアルゴリズムを改良して、文字列のハッシュ値を 1 つずつ比較するように変更することはできますか? 答えは、それでは十分とは言えません。最速のアルゴリズムを得るには、1 つずつ比較することはできません。通常、この問題を解決するためにハッシュテーブルが構築されます。ハッシュテーブルは大きな配列です。この配列の容量は、プログラムの要件に応じて定義されます (例: 1024)。各ハッシュ値は、モジュラス演算 (mod) を通じて配列内の位置に対応します。このように、文字列のハッシュ値に対応する位置が占有されているかどうかを比較するだけで、最終結果が得られます。これがどれだけ速いか考えてみてください。はい、これは最速の O(1) です。では、このアルゴリズムを詳しく見てみましょう。

 typedef構造体
{
 int nハッシュA;
 int nハッシュB;
 char bが存在する;
 …
 } 何らかの構造がTRUEです。

可能な構造定義?

関数 3:次の関数は、ハッシュテーブルに対象の文字列が存在するかどうかを確認します。存在する場合は、検索する文字列のハッシュ値を返します。存在しない場合は -1 を返します。

 int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )
 //lpszString はハッシュ テーブルで検索される文字列であり、lpTable は文字列のハッシュ値を格納するハッシュ テーブルです。  
 {
 int nHash = HashString(lpszString); //上記の関数 2 を呼び出し、検索する文字列 lpszString のハッシュ値を返します。  
 int nHashPos = nHash % nTableSize; 
   
 if ( lpTable[nHashPos].bExists &amp;&amp; !strcmp( lpTable[nHashPos].pString, lpszString ) )
    { //見つかったハッシュ値がテーブル内に存在し、検索対象の文字列がテーブル内の対応する位置にある文字列と同じ場合、  
 return nHashPos; //上記の関数2を呼び出した後に見つかったハッシュ値を返します 
    }
それ以外 
    {
戻り値- 1 ;
    }
 }

これを見ると、誰もが非常に深刻な疑問を抱いていると思います。「ハッシュテーブル内の 2 つの文字列の対応する位置が同じ場合はどうなるでしょうか?」結局のところ、配列の容量には限りがあり、この可能性は非常に高いのです。この問題を解決する方法はたくさんあります。最初に思いつくのは、「リンクリスト」を使用することです。大学で学んだデータ構造のおかげで、いつでも機能するこの魔法の武器を習得しました。遭遇する多くのアルゴリズムは、リンクリストに変換して解決できます。ハッシュテーブルの各エントリにリンクリストを掛け、対応する文字列をすべて保存するだけです。ここで物事は完璧に終わったようです。問題が私だけに任されていたら、この時点でデータ構造の定義とコードの記述を開始するでしょう。

しかし、Blizzard のプログラマーが採用したアプローチはより微妙です。基本的な原理は、ハッシュテーブル内の文字列を検証するために、1 つのハッシュ値ではなく3 つのハッシュ値を使用することです。

MPQ はファイル名ハッシュテーブルを使用して、すべてのファイルを内部的に追跡します。しかし、このテーブルの形式は通常のハッシュテーブルとは少し異なります。まず、検証のために実際のファイル名をテーブルに格納するためのインデックスとしてハッシュを使用する代わりに、実際にはファイル名をまったく格納しません。代わりに、3 つの異なるハッシュが使用されます。1 つはハッシュテーブルのインデックス作成用、2 つは検証用です。これら 2 つの検証ハッシュは実際のファイル名を置き換えます。

もちろん、この結果、2 つの異なるファイル名が 3 つの同一のハッシュにハッシュ化されます。しかし、これが起こる平均的な確率は 1:18889465931478580854784 であり、誰にとっても十分に小さいはずです。さて、データ構造に戻ると、Blizzard が使用するハッシュテーブルはリンクリストを使用しませんが、問題を解決するために「延期」アプローチを採用しています。このアルゴリズムを見てみましょう。

#p#

関数 4、 lpszString はハッシュテーブルで検索する文字列です。lpTable は文字列ハッシュ値を格納するハッシュテーブルです。nTableSize はハッシュテーブルの長さです。

 int GetHashTablePos( char *lpszString, MPQHASHTABLE *lpTable, int nTableSize )
 {
定数  int HASH_OFFSET = 0 、HASH_A = 1 、HASH_B = 2 ; 
   
 int nHash = ハッシュ文字列( lpszString, HASH_OFFSET );
 int nHashA = ハッシュ文字列( lpszString, HASH_A );
 int nHashB = ハッシュ文字列( lpszString, HASH_B );
 int nHashStart = nHash % nTableSize;
 int nHashPos = nHashStart; 
   
 ( lpTable[nHashPos].bExists )の間
   {
 /* 文字列がテーブル内に存在するかどうかだけを判別したい場合は、2 つのハッシュ値を比較するだけです。
     * 構造体内の文字列が比較されます。これによってスピードは上がりますか?ハッシュテーブルが占有するスペースを削減しますか?これ
      *この方法は一般的にどのような状況で使用されますか? */  
 lpTable[nHashPos].nHashA == nHashAの場合
        &amp;&amp; lpTable[nHashPos].nHashB == nHashB )
       {
 nHashPosを返します。
       }
それ以外 
       {
            nHashPos = (nHashPos + 1 ) % nTableSize;
       } 
   
 (nHashPos == nHashStart)の場合
壊す;
    }
戻り値- 1 ;
 }

上記のプログラムでは次のことを説明しています。

1. 文字列のハッシュ値を3つ計算する（1つは場所用、2つは検証用）

2.ハッシュテーブルでこの位置を確認する

3. ハッシュテーブル内のこの位置は空ですか?空の場合、文字列は存在しないので -1 が返されます。

4. 存在する場合は、他の 2 つのハッシュ値も一致するかどうかを確認します。一致する場合は、文字列が見つかったことを意味し、そのハッシュ値が返されます。

5. 次の位置に移動します。テーブルの末尾まで移動した場合は、テーブルの先頭まで巻き戻して検索を続けます。

6. 元の位置に戻ったかどうかを確認します。元の位置に戻った場合は、「見つかりません」に戻ります。

7. 3に戻る

さて、これがこの記事で紹介した最も高速なハッシュテーブルアルゴリズムです。何ですか? 速さが足りないんですか? :D。皆様のご批判、ご訂正を歓迎いたします。

——————————————–

補足1. 単純なハッシュ関数:

 /*keyは文字列、nTableLengthはハッシュテーブルの長さです
*この関数で得られたハッシュ値は均等に分配されます*/  
符号なしlong getHashIndex(定数  char *キー、 int nTableLength )
 {
    符号なしlong nHash = 0 ; 
     
 (*キー)の間
    {
        nHash = (nHash<< 5 ) + nHash + *key++;
    } 
          
戻り値( nHash % nTableLength );
 }

補足2、完全なテストプログラム:

ハッシュテーブルの配列の長さは固定です。配列が大きすぎると無駄になり、小さすぎると効率的ではありません。適切な配列サイズはハッシュテーブルのパフォーマンスにとって重要です。ハッシュテーブルのサイズは、できれば素数にしてください。もちろん、ハッシュテーブルのサイズはデータの量によって異なります。データ量が変化するアプリケーションの場合、最適な設計は、動的にサイズ変更可能なハッシュテーブルを使用することです。ハッシュテーブルのサイズが小さすぎる場合、たとえば、ハッシュテーブル内の要素数がハッシュテーブルの 2 倍のサイズである場合は、ハッシュテーブルのサイズを、通常は 2 倍に増やして増やす必要があります。

ハッシュテーブルのサイズに指定できる値は次のとおりです。

17、37、79、163、331、

673、1361、2729、5471、10949、

21911、43853、87719、175447、350899、

701819、1403641、2807303、5614657、11229331、

22458671, 44917381, 89834777, 179669557, 359339171,

718678369, 1437356741, 2147483647

以下は Linux でテストされたプログラムの完全なソースコードです。

 #include <stdio.h>
 #include <ctype.h> //修正していただいたcityloveさんに感謝します。  
 //crytTable[] には、HashString 関数で使用されるデータがいくつか格納されます。  
 // 関数内の初期化 
符号なしlong cryptTable[ 0x500 ]; 
    
 //次の関数は、長さ0x500（10進数：1280）のcryptTable[0x500]を生成します。  
 void暗号化テーブルの準備()
 {
    符号なしlongシード = 0x00100001 、インデックス1 = 0 、インデックス2 = 0 、i; 
    
 (インデックス1 = 0 ; インデックス1 < 0x100 ; インデックス1++ )
    {
 (インデックス2 = インデックス1、 i = 0 ; i < 5 ; i++、 インデックス2 += 0x100 )
        {
            符号なしロングtemp1、temp2; 
    
            シード = (シード * 125 + 3 ) % 0x2AAAAB ;
            temp1 = (シード & 0xFFFF ) << 0x10 ; 
    
            シード = (シード * 125 + 3 ) % 0x2AAAAB ;
            temp2 = (シード & 0xFFFF ); 
    
            cryptTable[index2] = ( temp1 | temp2 );
       }
   }
 } 
    
 //次の関数は、lpszFileName 文字列のハッシュ値を計算します。ここで、dwHashType はハッシュ タイプです。  
 //以下のGetHashTablePos関数内でこの関数を呼び出します。可能な値は0、1、2です。  
 //lpszFileName 文字列のハッシュ値を返します。  
符号なしロングハッシュ文字列( char *lpszFileName, 符号なしロングdwHashType )
 {
    符号なし文字*key = (符号なし文字*)lpszFileName;
符号なしロングシード1 = 0x7FED7FED ;
符号なしロングシード2 = 0xEEEEEEEE ;
整数ch; 
    
 ( *キー != 0 )の間
    {
        ch = toupper(*key++); 
    
        シード1 = cryptTable[(dwHashType << 8 ) + ch] ^ (シード1 + シード2);
        シード2 = ch + シード1 + シード2 + (シード2 << 5 ) + 3 ;
    }
 seed1を返します。
 } 
    
 //mainのargv[1]の3つのハッシュ値をテストします。  
 //./ハッシュ "arr/units.dat"  
 //./ハッシュ "unit/neutral/acritter.grp"  
 int main( int argc, char **argv )
 {
    符号なしlong ulHashValue;
整数i = 0 ; 
    
 （引数!= 2 ）の場合
    {
        printf( "引数を2つ入力してください/n" );
戻り値- 1 ;
    } 
    
 /* 配列を初期化: crytTable[0x500]*/   
     暗号化テーブルを準備します。 
    
 /*配列crytTable[0x500]の値を出力します*/   
 ( ; i < 0x500 ; i++ )の場合
     {
 ( i % 10 == 0 )の場合
         {
             printf( "/n" );
         } 
    
         printf( "%-12X" , cryptTable[i] );
     } 
    
     ulHashValue = ハッシュ文字列( argv[ 1 ], 0 );
     printf( "/n----%X ----/n" , ulHashValue ); 
    
     ulHashValue = ハッシュ文字列( argv[ 1 ], 1 );
     printf( "----%X ----/n" , ulHashValue ); 
    
     ulHashValue = ハッシュ文字列( argv[ 1 ], 2 );
     printf( "----%X ----/n" , ulHashValue ); 
    
戻る  0 ;
 }