データ構造でハッシュを計算する方法

5727 ワード
Programming-language DataStructures programming programming テキストリンク

はじめに:

ハッシュは、ハッシュ関数を使用してキーと値をハッシュテーブルにマッピングするプロセスです。これにより、要素へのアクセスが速くなります。ハッシュ関数の効率は、マッピングをどれだけうまく処理できるかを決定します。

リストに20000の番号があり、リスト内から番号を検索するように求められた場合、一致する番号が見つかるまで各番号をスキャンします。

リスト全体でその特定の番号を検索するプロセスには、多くの時間がかかります。この手動スキャンプロセスは時間がかかるだけでなく、非効率的でもあります。データ構造により、検索時間が短縮され、ハッシュ関数により数秒以内に数値を見つけることができます。

ハッシュの主要な用語

マッピングは、通常はキーと値の形式で、2つの異なるものをリンクするプロセスです。

キー–データ（エンティティ）を一意に識別する識別子。

値–保存しているデータエンティティ（および関連する詳細）。

ハッシュは2つのステップで機能します-

  1. アルゴリズムは、任意のエンティティ（キーとして）を入力として受け入れます。そのキーが整数でない場合は、entity（N）から整数値を取得するための何らかの方法をキーに提供する必要があります。
  2. 初期の整数値（N）を取得した後は、この整数をメモリアドレスとして使用してこのKey-Valueを配置することはできません。これは機能しませんが、ハッシュ関数はこの整数を、キー値をメモリに格納するために使用できる別の整数値に変換します。

ハッシュとは何ですか？

ハッシュアルゴリズムは、配列内のデータを効率的に検索して格納するという問題を解決するように設計されています。

たとえば、学生はエンティティです。各学生は、名前、住所、電話番号、一意のID（ロール番号）を持つことができます。

キーと値のペアにするために、ロール番号をキーとし、ペアは住所、名前、電話番号などの残りの属性になります。このようにして、ロール番号をキー、基本情報を値として学生のマッピングを作成しました。 。これで、生徒の詳細を知りたい場合は、生徒のロール番号を知ることができます。

ここに保存されるデータとは何ですか？

これは、オブジェクト指向用語でのオブジェクト、またはすべてが特定のものに属するプロパティのセットと考えることができます。

上に示したように、学生のデータには、ロール番号、名前、住所などの情報を含めることができます。

これらすべての詳細は、保存したい「データ」と考えることができます。ロール番号は生徒ごとに異なるため、重要です。

ロール番号=キー、および学生の詳細=値。

ハッシュの概念は、データ構造の世界で使用され、特定のデータ構造にこのキーと値のペアを格納するメモリアドレスまたはインデックスを検索します。たとえば、Key =100およびValue=特定のStudentdetailの場合、これらのデータを100またはStudentdetailに配置することはできません。

その結果、キーを入力として受け取り、メモリアドレス（またはデータ構造内のインデックス）を返すことができるハッシュ関数を使用して、キーと値のペアをに配置します。

このセクションの後半では、これが内部的にどのように機能するかを詳しく調べます。

データ構造のハッシュテーブル

基本的に、ハッシュ関数は、特定の大きなキーに対して（配列サイズ内の）小さな整数値を返す数式です。

以下は、このメソッドが内部でどのように機能するかについての3つのメソッドです。

  • 除算法-すべての方法の中で、これが最も理解しやすい方法です。配列にセルが10個しかなく、キーが15、つまり10より大きいシナリオを考えてみます。15を取り10を返すメソッドがない場合は、インデックス<10を返すメソッドが必要です。これは、モジュラス演算子によって非常に簡単に実行できます。

分割方法：HashFunction = Key％size

キーをサイズで割ると、余りはモジュラス演算子によってここに返されます。 key = 15の場合、サイズ10の配列の5番目のインデックスにこのデータを挿入できます。たとえば、15％10=5および5*10であるため、key = 15の場合、サイズ10の配列の5に挿入します。

  • 乗算方法-次の関数を使用して、除算と同様に機能します。
    h（k）= floor（n（kA mod 1））

キーkは0から1の間の定数値であり、Aは0から1の間の任意の定数値です。

kとAの両方が乗算され、モジュラス演算子を使用してそれらの小数部が分離されます。次に、これにnを掛けて、ハッシュ値を取得します。

例：

k = 123
n = 100
A = 0.618033（0から1の間でなければなりません）
h（123）= 100（123 * 0.618033 mod 1）
= 100（76.018059 mod 1）
= 100（0.018059）
= 1

キーがKの場合、値K=123はインデックス1にあります。

  • ユニバーサルハッシュ-ユニバーサルハッシュの中心は、固定ハッシュ関数を使用せず、さまざまなハッシュ関数のいずれかをランダムに選択できるという考え方です。ユニバーサルハッシュの基本原則では、キーxに* 1の衝突があると述べられているため、キーxに衝突があってはなりません。このようなハッシュ関数のファミリーができたら、実行時にこのセットから任意のハッシュ関数を選択できます。このハッシュ手法のランダム性により、その広がりが他のハッシュ手法間で最も均等に分散されることが保証されます。

  • 折りたたみ方法-折りたたみは、指定された配列サイズ内に収まるようにインデックスを見つける方法です。

折りたたまれたキーは、配列サイズが100の場合に2の部分に分割されるキーです。つまり、2桁の数字のみを含めることができます。つまり、Key = 20574の場合、20、57、および4の2つの部分に折ります。これらの部分から合計して100のインデックスを取得できます。つまり、20 + 57+4の合計は81です。この場合、81はKey=20574を配置できるインデックスを識別します。

折りたたんだ後でも、数>サイズになる場合がありますのでご注意ください。 Key = 56571次に、2 = 56 + 57 + 1=114の部分に分割します。

したがって、このデータはサイズ100の配列のインデックス114に配置できないため、アルゴリズムを再度使用するか、除算法（このようなシナリオで最も一般的に使用される）を使用して114％100=14を取得できます。

したがって、このデータはこの配列のインデックス14に配置する必要があります。

同様に、配列サイズが1000の場合、3桁の数値を挿入できるため、key=20574の値は205+74=279になります。

サイズ1000の配列では、Key=20574のデータは279番目のインデックスになります。

  • ミッドスクエア法-二乗された数のインデックスを見つけるために、私たちは数を二乗することから始めます。次に、その平方数の中間の数を選択します。上記の例で、配列サイズが100の場合、つまり数値は2桁しかできない場合は、Nを2とします（Nは何でもかまいません）。

931のハッシュは931^2 = 866761に等しくなります。指定されたN（= 2）要素から中央の要素67を選択します。

93は67のインデックスに配置できるため、67はそれを配置するための可能なインデックスになります。

ミッドスクエア法で得られたインデックスが配列サイズよりも大きい場合は、除算法を再度使用できます。

N = 2、配列サイズ= 11、および配列サイズ=12を検討してください。
この場合、hash（93）= 93 ^ 2 = 8649です。N（= 2）の中間要素を使用する場合、除算法を適用して64％11 = 9を取得できます。つまり、64これで64> 11になり、 64％11=9を取得する除算方法。
したがって、93はサイズ11の配列の9番目のインデックスに配置できます。

ハッシュの詳細については、ScalerTopicsの記事を参照してください。

結論

コンピューティングでは、ハッシュはデータセットから小さな数値を見つけるプロセスです。この番号を使用して、データを保存する場所を決定できます。データベースがメモリに保存されている場合、これはアレイ内のインデックスまたはディスク上のデータベースの場所である可能性があります。

  • 代わりに短いハッシュキーを使用できるため、ハッシュ方式を使用したアイテムのインデックス作成と取得は、元のキーを使用するよりも高速です。
  • バケット、キー、ハッシュ関数、線形プロービング、2次プロービング、ハッシュインデックス、衝突など、ハッシュで使用されるいくつかの用語があります。
  • 2つの異なる入力から取得されたインデックスが同じである場合、これは衝突と呼ばれます。
  • ハッシュ、再ハッシュ、および連鎖での衝突を回避するのに役立つ2つの方法があります。
  • 連鎖とは、両方のハッシュが同じインデックスに配置され、値が連鎖されることです。再ハッシュとは、空のインデックスが見つかるまでハッシュを続けることです。
  • 挿入と検索は、ほとんどの場合O（1）である定数時間のハッシュを使用して実行できます。
  • 要素を可能な限り均等に分散できる場合、優れたハッシュ関数は複雑さをO（1）に近づけることができます。

ハッピーラーニング！

続きを読む-

1.二重リンクリスト
2.kmpアルゴリズム
3.非線形データ構造
4.バックトラッキングアルゴリズム
5.単一リンクリスト