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

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

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

ハッシュ

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

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

シニア番号	キー	ハッシュ	配列インデックス
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

線形プロービング

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

シニア番号	キー	ハッシュ	配列インデックス	線形プロービング後、配列インデックス
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

基本操作

以下は、ハッシュテーブルの基本的な主要な操作です。

• Search −ハッシュテーブル内の要素を検索します。

• Insert −ハッシュテーブルに要素を挿入します。

• 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プログラミング言語でのハッシュ実装については、ここをクリックしてください。