用于链式哈希的C ++程序

散列是一种可以将任何长度的数据元素映射到固定大小的键的方法。散列用作键值对。

散列函数是在散列图中执行映射的函数。用作哈希函数输入的数据元素可能会获得相同的哈希键。在这种情况下，元素可能会重叠。为了避免具有相同哈希键的元素重叠，引入了链接的概念。

创建一个哈希映射

为了创建哈希映射，我们需要哈希函数，该函数将定义数据元素的索引值。

我们有一个带有n个存储桶的哈希表。要将节点插入到哈希表中，我们可以使用以下哈希函数：

hashIndex =键％noOfBuckets

现在，我们将使用此哈希函数并计算每个插入值到hashmap的hashindex 。

• 插入元素并计算给定键值的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