ハッシュ化 は、迅速なアクセスを可能にする方法でデータを効率的に保存および取得するための基本的なデータ構造です。これには、ハッシュ テーブル内の特定のインデックスにデータをマッピングすることが含まれます。 ハッシュ関数 これにより、キーに基づいて情報を高速に取得できます。この方法はデータベースでよく使用されます。 c 検索および取得操作を最適化するためのさまざまなプログラミング アプリケーション。
データ構造 - ハッシュ
目次
Javaの参照変数
使い方：
- ハッシュ関数: データ項目をハッシュ関数に指定します。
- ハッシュコード： ハッシュ関数はデータを処理し、一意のハッシュ コードを与えます。
- ハッシュ表： ハッシュ コードは、ハッシュ テーブル内の特定の場所を示します。
ハッシュ関数
の ハッシュ関数 は、 鍵 そして、 索引 に ハッシュ表 。ハッシュ関数の目標は、キーをハッシュ テーブル全体に均等に分散し、衝突 (2 つのキーが同じインデックスにマップされる場合) を最小限に抑えることです。
一般的なハッシュ関数には次のものがあります。
- 分割方法: キー % ハッシュ テーブル サイズ
- 乗算方法: (キー * 定数) % ハッシュ テーブル サイズ
- ユニバーサルハッシュ: 衝突を最小限に抑えるように設計されたハッシュ関数のファミリー
ハッシュ衝突とは何ですか?
ハッシュの衝突は、2 つの異なるキーがハッシュ テーブル内の同じインデックスにマップされる場合に発生します。これは、優れたハッシュ関数を使用していても、特にハッシュ テーブルがいっぱいであるか、キーが類似している場合に発生する可能性があります。
ハッシュ衝突の原因:
Java intから文字列へ
- 貧弱なハッシュ関数: ハッシュ関数がハッシュ テーブル全体にキーを均等に分散しないと、さらに多くの衝突が発生する可能性があります。
- 高負荷率: 負荷率 (ハッシュ テーブル サイズに対するキーの比率) が高いと、衝突の可能性が高くなります。
- 類似のキー: 値または構造が似ているキーは、衝突する可能性が高くなります。
衝突解決テクニック
衝突解決手法には次の 2 種類があります。
- オープンアドレッシング:
- リニアプロービング: 空きスロットを順番に探します
- 二次プロービング: 二次関数を使用して空きスロットを検索します。
- 非公開アドレス:
- 連鎖: 各インデックスのリンク リストまたは二分探索ツリーに衝突するキーを保存します。
- カッコーハッシュ: 複数のハッシュ関数を使用してキーを配布する
ハッシュの応用
ハッシュ テーブルは、次のようなさまざまなアプリケーションで使用されます。
- データベース: 一意のキーに基づいてデータを保存および取得する
- キャッシング： 頻繁にアクセスされるデータを保存して、より迅速に取得できるようにする
- シンボルテーブル: プログラミング言語での識別子とその値のマッピング
- ネットワークルーティング: データパケットの最適なパスの決定
ハッシュ化とは何ですか?
ハッシュに関する簡単な問題
- 配列が別の配列のサブセットであるかどうかを調べる
- 2 つのリンクされたリストの結合と交差
- 配列 A[] と数値 x が与えられた場合、合計が x である A[] 内のペアをチェックします。
- 配列内の同じ要素の 2 つの出現間の最大距離
- 同一線上の最大点を数える
- 配列内の最も頻繁に使用される要素
- 1 から n-1 までの唯一の繰り返し要素を検索します
- 指定された 2 つのセットが素であるかどうかを確認するにはどうすればよいですか?
- 2 つのセットの重複しない合計
- 2 つの配列が等しいかどうかを確認する
- 範囲内の欠落している要素を検索する
- 個別の要素を持つサブセットの最小数
- 両方の配列に共通の要素が存在しないように、最小限の数の要素を削除します。
- ペアの要素が異なる行にあるような、指定された合計を持つペアを検索します。
- 指定された合計を持つペアを数える
- 合計が指定された値 x に等しい 4 つの並べ替えられた配列から 4 倍を数えます。
- 要素を頻度で並べ替える
- a % b = k となる配列内のすべてのペア (a, b) を検索します。
- 同じ文字セットを持つ単語をグループ化する
- 配列内の k 番目の個別の (または非繰り返しの) 要素。
ハッシュに関する中の問題
- 指定されたチケットのリストから旅程を検索
- 各従業員の下にある従業員の数を検索する
- 合計が k で割り切れる最長の部分配列
- 和が0の最大の部分配列を見つける
- 最長の連続した増加サブシーケンス
- サイズ k のすべてのウィンドウ内の個別の要素を数える
- 指定された合計を持つ部分配列を検索します |セット 2 (負の数を処理)
- Java で個別のチェーンを使用した独自のハッシュ テーブルを実装する
- C++ でのオープン アドレッシング線形プローブを使用した独自のハッシュ テーブルの実装
- 順列が許可された回文を形成するための最小挿入数
- 配列の 2 つのサブセットの最大可能差
- 自明なハッシュ関数を使用したソート
- k 個の異なる数値を持つ最小の部分配列
ハッシュに関する難しい問題
- ランダムなポインタを使用してバイナリ ツリーのクローンを作成する
- 同数の 0 と 1 を持つ最大のサブ配列
- 合計すると指定の値になるすべての一意のトリプレット
- 回文部分文字列クエリ
- 配列要素の頻度の範囲クエリ
- 範囲のすべての要素が配列内に存在するように追加される要素
- カッコーハッシュ – 最悪の場合 O(1) ルックアップ!
- 元の配列と同じ異なる要素の合計を持つサブ配列をカウントします。
- 同じ順序を維持した 2 つの指定された配列からの最大の配列
- 指定された配列の一意のすべてのサブ配列の合計の合計を求めます。
- レカマンのシーケンス
- 最長の厳密なビットニック部分列の長さ
- 重複するサブツリーをすべて検索
- バイナリ行列に角が 1 の長方形があるかどうかを調べます
クイックリンク ：
- ハッシュに関する「練習問題」
- ハッシュ技術に基づく面接の質問トップ 20
- ハッシュに関する「ビデオ」
推奨：
- データ構造とアルゴリズムを学ぶ | DSA チュートリアル