ハッシュとは何ですか?ハッシュコードのしくみ-例を挙げて

ハッシュの概要

ハッシュは、コレクション内のアイテムを効率的に検索または保存する必要があるという問題を解決するように設計されています。

たとえば、10,000語の英語のリストがあり、特定の単語がリストに含まれているかどうかを確認する場合、一致するものが見つかるまで、その単語を10,000項目すべてと連続して比較するのは非効率的です。辞書のように単語のリストが辞書式に並べ替えられている場合でも、探している単語を見つけるのに時間がかかります。

ハッシュは、最初に検索を効果的に絞り込むことによって、物事をより効率的にするための手法です。

ハッシュとは何ですか?

ハッシュとは、関数またはアルゴリズムを使用して、オブジェクトデータを代表的な整数値にマッピングすることを意味します。

このいわゆるハッシュコード(または単にハッシュ)は、マップ内のアイテムを検索するときに検索を絞り込む方法として使用できます。

通常、これらのハッシュコードは、値が格納されるインデックスを生成するために使用されます。

ハッシュのしくみ

ハッシュテーブルでは、キーと値のペアの形式でデータを格納します。データを識別するために使用されるキーは、ハッシュ関数への入力として与えられます。次に、整数であるハッシュコードが、固定サイズにマップされます。

ハッシュテーブルは3つの機能をサポートする必要があります。

  • 挿入(キー、値)
  • get(キー)
  • 削除(キー)

純粋に概念を理解するのに役立つ例として、文字列キーのリストを文字列値にマップするとします(たとえば、国のリストを首都にマップします)。

それで、マップのテーブルにデータを保存したいとしましょう。

そして、ハッシュ関数が単に文字列の長さを取ることであると仮定しましょう。

簡単にするために、2つの配列を用意します。1つはキー用、もう1つは値用です。

したがって、アイテムをハッシュテーブルに配置するには、そのハッシュコードを計算し(この場合は、単に文字数を数えます)、対応するインデックスの配列にキーと値を配置します。

たとえば、キュ​​ーバのハッシュコード(長さ)は4です。したがって、キューバをキー配列の4番目の位置に格納し、ハバナを値配列の4番目のインデックスなどに格納します。結果として次のようになります。

さて、この特定の例では、物事は非常にうまく機能します。アレイは最長の文字列を収容するのに十分な大きさである必要がありますが、この場合は11スロットのみです。

たとえば、データに1文字のキーがなく、8〜10文字のキーもないため、スペースを少し無駄にします。

しかし、この場合、無駄なスペースもそれほど悪くはありません。文字列の長さを取得することは素晴らしく、高速であり、特定のキーに関連付けられた値を見つけるプロセスも同様です(最大5つの文字列比較を実行するよりも確実に高速です)。

しかし、データセットに11文字を超える文字列がある場合はどうすればよいでしょうか。

「インド」という5文字の単語がもう1つあり、ハッシュ関数を使用してそれをインデックスに割り当ててみるとどうなりますか。インデックス5はすでに占有されているので、それをどうするかを呼び出す必要があります。これは衝突と呼ばれます。

データセットに1,000文字の文字列があり、データを格納するために1,000のインデックスの配列を作成すると、スペースが無駄になります。キーが英語のランダムな単語であり、同じ長さの単語が非常に多い場合、ハッシュ関数として長さを使用することはかなり役に立ちません。

衝突処理

衝突の処理には、2つの基本的な方法が使用されます。

  1. 個別の連鎖
  2. オープンアドレス法

個別の連鎖

個別のチェーンによるハッシュ衝突処理は、追加のデータ構造、できれば動的割り当て用のリンクリストをバケットに使用します。この例では、インドをデータセットに追加すると、インデックス5に格納されているリンクリストに追加され、テーブルは次のようになります。

アイテムを見つけるには、最初にバケットに移動し、次にキーを比較します。これは一般的な方法であり、リンクのリストが使用されている場合、ハッシュがいっぱいになることはありません。のコストget(k)は平均です。O(n)ここで、nはバケット内のキーの数、キーの総数はNです。

個別のチェーンの問題は、データ構造が際限なく大きくなる可能性があることです。

オープンアドレス法

Open addressing does not introduce any new data structure. If a collision occurs then we look for availability in the next spot generated by an algorithm. Open Addressing is generally used where storage space is a restricted, i.e. embedded processors. Open addressing not necessarily faster then separate chaining.

Methods for Open Addressing

  • [Linear Probing
  • Quadratic Probing
  • Double Hashing

How to use hashing in your code.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
:rocket:

Run Code

Java

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
:rocket:

Run Code

More info on hashing

  • The codeless guide to hashing and hash tables
  • How to implement a simple hash table in JavaScript
  • Hash tables explained