Javaの折りたたみ手法のガイド

1. 前書き

このチュートリアルでは、要素への一定時間のアクセスを提供するさまざまなデータ構造で使用されるハッシュ手法を検討します。
いわゆる「折り畳み手法」について詳しく説明し、ミッドスクエアとビニングの手法について簡単に紹介します。

2. 概要

オブジェクトを保存するためのデータ構造を選択するときの考慮事項の1つは、オブジェクトにすばやくアクセスする必要があるかどうかです。
Javaユーティリティパッケージは、オブジェクトを格納するための非常に多くのデータ構造を提供します。 データ構造の詳細については、https：//www.baeldung.com/java-collections [Java Collections]編集ページを参照してください。このページには、それらのいくつかのガイドが含まれています。
ご存じのように、これらのデータ構造の一部を使用すると、含まれる要素の数に関係なく、一定の時間で要素を取得できます。
おそらく、最も単純なものは配列です。 実際、インデックスを使用して配列内の要素にアクセスします。 *当然、アクセス時間は配列のサイズに依存しません。*実際、多くのデータ構造では、背後で配列を頻繁に使用しています。
問題は、配列インデックスは数値でなければならないことですが、多くの場合、これらのデータ構造をオブジェクトで操作することを好みます。
この問題に対処するために、多くのデータ構造は、オブジェクトに配列インデックスとして機能できる数値を割り当てようとします。 *この値を_hash value_または単に_hash_と呼びます。*

3. ハッシング

**ハッシュとは、オブジェクトを数値に変換することです*。*これらの変換を実行する関数は、_ハッシュ関数_と呼ばれます。
簡単にするために、文字列を配列インデックスに変換するハッシュ関数、つまり、範囲_ [0、N] _から_N_の整数に変換するハッシュ関数を考えてみましょう。
当然、ハッシュ関数はさまざまな文字列に適用されます*。 したがって、その「グローバル」プロパティが重要になります。
link：/uploads/strings-to-numbers.png [] + *残念ながら、ハッシュ関数が常に異なる文字列を異なる数値に変換することは不可能です*。
文字列の数は、任意の範囲_ [0、N] _の整数の数よりもはるかに大きいと簡単に確信できます。 したがって、ハッシュ関数が等しい値を生成する一対の等しくない文字列が存在することは避けられません。 *この現象は_collision_と呼ばれます。*
ハッシュ関数の背後にあるエンジニアリングの詳細については詳しく説明しませんが、優れたハッシュ関数は、それが定義されている文字列を数値に均一にマッピングしようとすることは明らかです。
もう1つの明らかな要件は、優れたハッシュ関数が高速であることです。 ハッシュ値の計算に時間がかかりすぎる場合、要素にすばやくアクセスできません。
このチュートリアルでは、マッピングを高速に保ちながらマッピングを均一にしようとする*テクニックの1つを検討します。

4. 折りたたみ技術

私たちの目標は、文字列を配列インデックスに変換する関数を見つけることです。 考えを説明するために、この配列に10 ^ 5 ^要素の容量を持たせたいとし、文字列_Java言語_を例として使用してみましょう。

4.1. 説明

文字列の文字を数字に変換することから始めましょう。 ASCIIは、この操作の適切な候補です。
link：/uploads/convert-to-ascii1.png []
次に、取得した数値をいくつかのサイズのグループに整理します。 通常、10 ^ 5 ^である配列のサイズに基づいてグループサイズの値を選択します。 文字を変換した数字には、一般性を失うことなく2〜3桁の数字が含まれているため、グループサイズを2に設定できます。
link：/uploads/arrange-ascii-codes.png []
次のステップは、各グループの数字を文字列であるかのように連結し、合計を見つけることです。
link：/uploads/folding-sum.png []
次に、最終ステップを実行する必要があります。 番号_348933_がサイズ10 ^ 5 ^の配列のインデックスとして機能するかどうかを確認しましょう。 当然、最大許容値_99999._を超えます。最終結果を見つけるためにモジュロ演算子を適用することにより、この問題を簡単に克服できます。
348933 % 10000 = 48933

4.2. 最後に

アルゴリズムには時間のかかる操作が含まれていないため、非常に高速です。 *入力文字列のすべての文字が最終結果に貢献します。*この事実は衝突を減らすのに役立ちますが、完全に回避することはできません。
たとえば、折りたたみをスキップし、モジュロ演算子をASCII変換された入力文字列に直接適用する場合（オーバーフローの問題は無視します）
749711897321089711010311797103101 % 100000 = 3101
そのようなハッシュ関数は、入力文字列と同じ最後の2文字を持つすべての文字列に対して同じ値を生成します：a__ge __、p__age __、lar__ge、__など。
アルゴリズムの説明から、衝突から解放されていないことが簡単にわかります。 たとえば、アルゴリズムは_Java言語_および_vaJa言語_文字列__.__に対して同じハッシュ値を生成します

5. その他のテクニック

折り畳み技術は非常に一般的ですが、それだけではありません。 場合によっては、_binning_または_mid-square_の手法も役立つ場合があります。
文字列ではなく数字を使用して、そのアイデアを説明します（すでに文字列を数字に変換していると仮定します）。 それらの長所と短所については説明しませんが、アルゴリズムを見た後に意見を述べることができます。

5.1. ビニング技術

100個の整数があり、ハッシュ関数でそれらを10個の要素の配列にマッピングするとします。 次に、最初の10個の整数が1番目のビンに、2番目の10個の整数が2番目のビンになるなどの方法で、これらの100個の整数を10個のグループに配置します。
link：/uploads/binning.png []

* 5.2。 ミッドスクエアテクニック*

このアルゴリズムはJohn von Neumannによって提案されたもので、指定された数から始まる擬似乱数を生成できます。
link：/uploads/mid-square.png [] +具体例で説明しましょう。 4桁の番号_1111_があるとします。 アルゴリズムに従って、それを二乗して、_1234321â__を取得します。 ここで、中央から4桁、たとえば_2343_を抽出します。 このアルゴリズムにより、結果に満足するまでこのプロセスを繰り返すことができます。

6. 結論

このチュートリアルでは、いくつかのハッシュ手法を検討しました。 折り畳みの手法を詳細に説明し、ビニングとミッドスクエアをどのように達成できるかについて簡単に説明しました。
いつものように、https：//github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-3 [GitHub repository]で対応するコードスニペットを見つけることができます。