ハッシュ化 ハッシュ関数として知られる数式を使用して、可変サイズの入力から固定サイズの出力を生成するプロセスを指します。この技術は、データ構造内の項目を格納するためのインデックスまたは場所を決定します。
カット・ティンフの妹
ハッシュデータ構造の必要性
インターネット上のデータ量は毎日急激に増加しており、すべてを効果的に保存することが困難になっています。日常的なプログラミングでは、このデータ量はそれほど大きくないかもしれませんが、それでも、簡単かつ効率的に保存、アクセス、処理する必要があります。このような目的に使用される非常に一般的なデータ構造は、Array データ構造です。
ここで、Array がすでに存在していたとしたら、新しいデータ構造が必要だったのかという疑問が生じます。これに対する答えは効率という言葉にあります。配列に保存するには時間がかかりますが、 ○(1) 時間、検索には少なくともかかります O(log n) 時間。この時間は短いように見えますが、大規模なデータ セットの場合、多くの問題が発生する可能性があり、その結果、配列データ構造が非効率になります。
そこで今、データを保存し、一定時間で検索できるデータ構造を探しています。 ○(1) 時間。これが、ハッシュ データ構造の登場です。ハッシュ データ構造の導入により、データを一定時間で保存し、一定時間で取得することも簡単にできるようになりました。
ハッシュの構成要素
ハッシュには主に 3 つのコンポーネントがあります。
- 鍵： あ 鍵 ハッシュ関数への入力として供給される任意の文字列または整数を指定できます。ハッシュ関数は、データ構造内の項目の格納のためのインデックスまたは場所を決定する手法です。
- ハッシュ関数: の ハッシュ関数 入力キーを受け取り、ハッシュ テーブルと呼ばれる配列内の要素のインデックスを返します。インデックスはとして知られています ハッシュインデックス 。
- ハッシュ表： ハッシュ テーブルは、ハッシュ関数と呼ばれる特別な関数を使用してキーを値にマッピングするデータ構造です。ハッシュは、各データ値が独自の一意のインデックスを持つ配列にデータを連想方式で保存します。
ハッシュの構成要素
衝突とは何ですか?
ハッシュ プロセスでは大きなキーに対して小さな数値が生成されるため、2 つのキーが同じ値を生成する可能性があります。新しく挿入されたキーがすでに占有されているキーにマッピングされ、何らかの衝突処理テクノロジを使用して処理する必要がある状況。
ハッシュでの衝突
jframe
データ構造におけるハッシュの利点
- キーと値のサポート: ハッシュは、キーと値のデータ構造を実装するのに最適です。
- 高速なデータ取得: ハッシュを使用すると、一定時間の複雑さを持つ要素にすばやくアクセスできます。
- 効率： 挿入、削除、検索操作は非常に効率的です。
- メモリ使用量の削減: ハッシュでは、要素を格納するために固定スペースが割り当てられるため、必要なメモリが少なくなります。
- スケーラビリティ: ハッシュは大規模なデータ セットでも適切に実行され、一定のアクセス時間を維持します。
- セキュリティと暗号化: ハッシュは、安全なデータの保存と整合性の検証に不可欠です。
ハッシュの詳細については、を参照してください。 ハッシュの概要 – データ構造とアルゴリズムのチュートリアル