データ構造とアルゴリズム-ハッシュテーブル

ハッシュテーブルは、データを連想的に格納するデータ構造です。ハッシュテーブルでは、データは配列形式で格納され、各データ値には独自のインデックス値があります。目的のデータのインデックスがわかれば、データへのアクセスは非常に高速になります。

したがって、データのサイズに関係なく、挿入および検索操作が非常に高速なデータ構造になります。ハッシュテーブルは、記憶媒体として配列を使用し、ハッシュ手法を使用して、要素の挿入元または検索元のインデックスを生成します。

ハッシング

ハッシュは、キー値の範囲を配列のインデックスの範囲に変換する技術です。モジュロ演算子を使用して、キー値の範囲を取得します。サイズ20のハッシュテーブルの例を考えてみましょう。次のアイテムが格納されます。アイテムは（キー、値）形式です。

（1,20）
（2,70）
（42,80）
（4,25）
（12,44）
（14,32）
（17,11）
（13,78）
（37,98）

Sr.No.	Key	Hash	Array Index
1	1	1 % 20 = 1	1
2	2	2 % 20 = 2	2
3	42	42 % 20 = 2	2
4	4	4 % 20 = 4	4
5	12	12 % 20 = 12	12
6	14	14 % 20 = 14	14
7	17	17 % 20 = 17	17
8	13	13 % 20 = 13	13
9	37	37 % 20 = 17	17

線形探査

ご覧のように、配列の既に使用されているインデックスを作成するためにハッシュ手法が使用される場合があります。このような場合、空のセルが見つかるまで次のセルを調べることにより、配列内の次の空の場所を検索できます。この手法は、線形プローブと呼ばれます。

Sr.No.	Key	Hash	Array Index	After Linear Probing, Array Index
1	1	1 % 20 = 1	1	1
2	2	2 % 20 = 2	2	2
3	42	42 % 20 = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 = 17	17	18

基本操作

ハッシュテーブルの基本的な基本操作は次のとおりです。

検索-ハッシュテーブルの要素を検索します。
挿入-ハッシュテーブルに要素を挿入します。
delete -ハッシュテーブルから要素を削除します。

DataItem

検索がハッシュテーブルで実行されることに基づいて、いくつかのデータとキーを持つデータ項目を定義します。

struct DataItem {
   int data;
   int key;
};

ハッシュ法

データ項目のキーのハッシュコードを計算するハッシュメソッドを定義します。

int hashCode(int key){
   return key % SIZE;
}

検索操作

要素を検索する場合は常に、渡されたキーのハッシュコードを計算し、そのハッシュコードを配列のインデックスとして使用して要素を見つけます。計算されたハッシュコードで要素が見つからない場合は、線形プローブを使用して要素を先に取得します。

例

struct DataItem *search(int key) {
  //get the hash
   int hashIndex = hashCode(key);

  //move in array until an empty
   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

     //go to next cell
      ++hashIndex;

     //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;
}

挿入操作

要素を挿入するときは常に、渡されたキーのハッシュコードを計算し、そのハッシュコードを配列のインデックスとして使用してインデックスを見つけます。計算されたハッシュコードで要素が見つかった場合、空の場所に線形プローブを使用します。

例

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;
   item->key = key;

  //get the hash
   int hashIndex = hashCode(key);

  //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
     //go to next cell
      ++hashIndex;

     //wrap around the table
      hashIndex %= SIZE;
   }

   hashArray[hashIndex] = item;
}

削除操作

要素を削除するときは常に、渡されたキーのハッシュコードを計算し、そのハッシュコードを配列のインデックスとして使用してインデックスを見つけます。計算されたハッシュコードで要素が見つからない場合は、線形プローブを使用して要素を先に取得します。見つかったら、そこにダミーのアイテムを保存して、ハッシュテーブルのパフォーマンスを維持します。

例

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

  //get the hash
   int hashIndex = hashCode(key);

  //move in array until an empty
   while(hashArray[hashIndex] !=NULL) {

      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex];

        //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem;
         return temp;
      }

     //go to next cell
      ++hashIndex;

     //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;
}

Cプログラミング言語でのハッシュの実装については、リンク：/data_structures_algorithms/hash_table_program_in_c [ここをクリック]をご覧ください。

Data-structures-algorithms-hash-data-structure

目次