連鎖によるハッシュのためのC++プログラム

ハッシュは、任意の長さのデータ要素を固定サイズのキーにマップできる方法です。ハッシュはキーと値のペアとして機能します。

ハッシュ関数は、ハッシュマップでマッピングを行う関数です。ハッシュ関数への入力として指定されたデータ要素は、同じハッシュキーを取得する場合があります。この場合、要素が重複する可能性があります。同じハッシュキーを持つ要素の重複を避けるために、連鎖の概念が導入されました。

ハッシュマップの作成

ハッシュマップを作成するには、データ要素のインデックス値を定義するハッシュ関数が必要です。

n個のバケットを持つハッシュテーブルがあります。ノードをハッシュテーブルに挿入するには 、ハッシュ関数が与えられます

hashIndex =key％noOfBuckets

次に、このハッシュ関数を使用して、ハッシュマップに挿入されたすべての値のハッシュインデックスを計算します。 。

• 要素を挿入し、指定されたキー値のhashIndexを計算してから、新しいノードをリストの最後に挿入します。

• ノードを削除するには、ハッシュインデックスを計算し、ハッシュインデックスに対応するバケットで、バケット内の要素を検索して削除します。

例

#include<iostream>
#include <list>
using namespace std;
class Hash{
   int BUCKET;
   list < int >*table;
   public:
   Hash (int V);
   void insertItem (int x);
   void deleteItem (int key);
   int hashFunction (int x){
      return (x % BUCKET);
   }
   void displayHash ();
};
Hash::Hash (int b){
   this->BUCKET = b;
   table = new list < int >[BUCKET];
}
void Hash::insertItem (int key){
   int index = hashFunction (key);
   table[index].push_back (key);
}
void Hash::deleteItem (int key){
   int index = hashFunction (key);
   list < int >::iterator i;
   for (i = table[index].begin (); i != table[index].end (); i++){
   if (*i == key)
      break;
   }
   if (i != table[index].end ())
      table[index].erase (i);
}
void Hash::displayHash (){
   for (int i = 0; i < BUCKET; i++){
      cout << i;
      for (auto x:table[i])
      cout << " --> " << x;
      cout << endl;
   }
}
 int main (){
   int a[] = { 5, 12, 67, 9, 16 };
   int n = 5;
   Hash h (7);
   for (int i = 0; i < n; i++)
   h.insertItem (a[i]);
   h.deleteItem (12);
   h.displayHash ();
   return 0;
}

出力

0
1
2 --> 9 --> 16
3
4 --> 67
5 --> 5
6