ハッシュテーブルを理解する
1. 序章
データを効率的に管理する技術は、コンピュータサイエンスの伝統的なホットトピックです。データを保存することに加えて、効率的にストレージからデータを回復することも、関連するもう1つの懸念事項です。
特定のデータ処理を行う最高のアルゴリズムを使用しても、データ管理が最適化されていないと、パフォーマンスが低下します。 したがって、データを回復してアルゴリズムに提供し、その出力を保存することは、パフォーマンスのボトルネックになります。
データを保持および管理するためのいくつかの手法が、時間の経過とともに提案されてきました。 例は次のとおりです 配列, リンクリスト, 木、 と グラフ。 これらのデータ構造は、複数の目的に最適です。 ただし、それらに格納されているデータを見つけて回復するための時間の複雑さは、通常、別のデータ構造であるハッシュテーブルよりも高くなります。
したがって、このチュートリアルでは、ハッシュテーブルに関して最も関連性の高い概念について説明します。 まず、ハッシュについて簡単に説明します。 したがって、ハッシュテーブルとその機能について学習します。 次に、ハッシュ衝突に関するいくつかの潜在的な問題を解決する方法を見ていきます。 最後に、データ管理の複雑さに関して、ハッシュテーブルを他のデータ構造と比較します。
2. ハッシュの基本
ハッシュテーブルを具体的に研究する前に、理解する必要があります ハッシュ. 要約すると、ハッシュは、可変長の入力を受け取り、ハッシュコードまたは単にハッシュと呼ばれる固定長の出力値を生成するプロセスです。
ハッシュ関数は、可変長入力をハッシュに変換する役割を果たします。 標準のハッシュ関数はありません。 これは、データ入力の一般的な期待される特性に従ってハッシュ関数を開発できることを意味します。
次の画像は、ハッシュメカニズムがどのように機能するかを大まかに示しています。
ハッシュ関数は、可変長入力のバイト数を増減できることに注意してください。
要するに、ハッシュには、パスワードの保存と検証、メッセージ署名の作成、データ管理構造の提供（このチュートリアルのメイントピック）など、コンピューターサイエンスのいくつかのアプリケーションがあります。
3. ハッシュテーブル
したがって、ハッシュテーブルをキー値ルックアップとして理解できます。 したがって、値（データ）に関連付けられたキーが与えられると、テーブルをすばやく検索することで、対応する値を回復できます。
たとえば、ハッシュテーブルを使用して、人の名前と個人情報を関連付けることができます。 このように、人々の名前は私たちの生の鍵です。 ハッシュ関数は、これらの生のキーを処理して、ハッシュテーブル内の対応するインデックスを決定し、個人情報への直接アクセスを提供します。
次の画像は、最後の段落で説明したハッシュテーブルとそのプロセスを示しています。
時間の経過とともに、ハッシュテーブルはコンピューティングシナリオで非常に人気がありました。 したがって、さまざまなプログラミング言語が、この種のデータ構造をネイティブに、または組み込みライブラリを介して提供するための取り組みを動かしました。
開発された構造の例は、JavaのHashMaps、Pythonのdictクラス（辞書）、c ++のmapクラス、Lispのalistです。
ハッシュテーブルは、時間と空間のトレードオフの良い例です。 利用可能な時間が無限である場合、同じインデックスにリンクされたすべてのキーを保持し、特定のデータを回復するためにバイナリ検索を実行することしかできません。
一方、スペースが無限である場合は、キーに対応するデータを格納するために必要な数の個別のメモリバケットを使用して、完全なキーをインデックス自体として使用できます。
ただし、現実の世界には無限の時間や空間はありません。したがって、次のサブセクションで説明するように、最終的にはハッシュ衝突とインデックス共有に対処します。
3.1. ハッシュテーブルでの衝突
ハッシュ関数は可変長キーを固定長インデックスにマップするため、実際には無限セットを有限セットにマップします。 このようにして、最終的に衝突が発生します。
ハッシュテーブルでは、衝突とは、ハッシュ関数が複数の必要なキーを同じインデックスにマップし、その結果、テーブルの同じメモリバケットにマップしたことを意味します。
そのため、衝突に対処するために多くの手法が提案されました。 最も関連性の高いものについて簡単に説明します。
- 個別の連鎖：個別の連鎖手法は、ハッシュテーブルのメモリバケット内のリンクリストをサポートすることで衝突に対処します。 したがって、同じメモリバケットにマップされたデータ（キーは同じインデックスを生成します）がリンクリストに追加されます
- 線形プロービング：オープンアドレッシングとも呼ばれるこの手法は、データを挿入するための空きメモリバケットを持つ決定されたインデックスの最初の次のインデックスを見つける衝突を処理します
- サイズ変更とコピー：衝突が発生したときにハッシュテーブルのサイズを変更し、そのデータを再配布する簡単な手法。 このプロセスは、当面の衝突の問題を解決し、近い将来に他の衝突を回避することを目的としています
4. データ管理の複雑さ
ハッシュテーブルは、データ管理の観点から優れた構造です。 このデータ構造で採用されているキー値スキームは直感的であり、さまざまなシナリオの複数のデータにうまく適合します。
さらに、ハッシュテーブル内のデータを検索、挿入、および削除するための平均的な複雑さはO（1）であり、定数時間です。 これは、平均して、目的の操作に関係なく、目的のメモリバケットを見つけるには単一のハッシュテーブルルックアップで十分であることを意味します。
ただし、これらの操作の最悪のケースは、通常、O（n）—線形時間です。 このケースは、ハッシュテーブル内のすべてのデータに同じインデックスにマップされるキーがある場合に発生します。
このシナリオでは、ハッシュテーブルは常に衝突を解決するための手法を実行します。 個別のチェーンや線形プロービングなど、これらの手法の一部は、リストまたはテーブル自体をスキャンするために余分な時間を必要とするため、時間計算量の最悪のケースが増加します。
ただし、適切に設計されたハッシュテーブルでは、通常、衝突はほとんど発生しません。 したがって、このデータ構造は、データを保持および提供するための多用途で機敏なオプションです。
4.1. ハッシュテーブルを他のデータ構造と比較する
当然、ハッシュテーブルに加えて、データを管理するための他のデータ構造があります。 従来の例は、順序付けされていないリンクリストです。 私たちの議論のために、二重リンクされた循環リストの実装を考えてみましょう。
リンクリストでは、特定の要素の挿入と削除は非常に簡単です。 最も簡単な挿入は、追加操作です。 定義された操作数で、新しい要素を一定時間でリストに追加できます— O（1）。 同様に、削除する要素が与えられると、一定時間で操作を実行できます— O（1）。
ここで、要素へのポインタがリストに追加または削除するためにすでに使用可能であると見なしていることを強調することは重要です。
ただし、リンクリストで最も難しいのは、特定の要素を検索することです。 このような場合、平均の複雑さはO（n）です。特定のリスト要素が見つかるまで各リスト要素をチェックする必要があるために発生します。
二分探索などの他の手法を採用することで、検索の複雑さを軽減できます。 ただし、このようなシナリオでは、順序付けられたリンクリストが必要になります。これにより、リストへの要素の挿入が複雑になります。
順序付けられた二重リンクの循環リストについて考えてみましょう。 挿入ソートアルゴリズムを使用してリストを並べ替えると、挿入の複雑さはO（n）になります。 削除の複雑さは依然としてO（1）です。 また、要素を見つけるために二分探索を使用すると、検索の複雑さはO（log n）になります。
次の表は、挿入、削除、および検索操作の順序なしリスト、順序付きリスト、およびハッシュテーブルの平均時間計算量を比較しています。
5. 結論
ハッシュテーブルには、考慮されるすべてのデータ管理操作の平均時間計算量が魅力的であることがわかります。 特に、データを検索するための一定の時間計算量は、ハッシュテーブルをアルゴリズムのループ数を減らすための優れたリソースにします。
最後に、最悪の場合、線形の時間計算量がありますが、バランスの取れたハッシュ関数と適切な次元のハッシュテーブルは、当然、衝突を回避します。 したがって、最悪の場合の時間計算量は発生しない傾向があります。
