用链式散列的C++程序-yiteyi-C++库

在里面散列有一个哈希函数可以将键映射到某些值。但这些散列函数可能会导致冲突，即两个或多个键映射到同一个值。 链式散列 避免碰撞。其思想是使哈希表的每个单元格指向具有相同哈希函数值的记录的链表。让我们创建一个散列函数，这样我们的散列表就有N个存储桶。要将节点插入哈希表，我们需要找到给定键的哈希索引。它可以用散列函数来计算。 示例：hashIndex=key%noOfBuckets 插入：移动到与上面计算的哈希索引相对应的bucket，并在列表末尾插入新节点。删去：要从哈希表中删除节点，请计算键的哈希索引，移动到与计算出的哈希索引相对应的bucket，搜索当前bucket中的列表以查找并删除具有给定键（如果找到）的节点。

null

图片[1]-用链式散列的C++程序-yiteyi-C++库

请参考 散列|集2（单独链接） 详细信息。我们使用 C++列表在内部实现为链表（更快的插入和删除）。

CPP

                         // CPP program to implement hashing with chaining                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         class                                     Hash                       
                         {                       
                                                 int                                     BUCKET;                                     // No. of buckets                       
           
                                                 // Pointer to an array containing buckets                       
                                                 list<                                     int                                     > *table;                       
                         public                                     :                       
                                                 Hash(                                     int                                     V);                                     // Constructor                       
           
                                                 // inserts a key into hash table                       
                                                 void                                     insertItem(                                     int                                     x);                       
           
                                                 // deletes a key from hash table                       
                                                 void                                     deleteItem(                                     int                                     key);                       
           
                                                 // hash function to map values to 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)                       
                         {                       
                                                 // get the hash index of key                       
                                                 int                                     index = hashFunction(key);                       
           
                                                 // find the key in (index)th list                       
                                                 list <                                     int                                     > :: iterator i;                       
                                                 for                                     (i = table[index].begin();                       
                                                 i != table[index].end(); i++) {                       
                                                 if                                     (*i == key)                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // if key is found in hash table, remove it                       
                                                 if                                     (i != table[index].end())                       
                                                 table[index].erase(i);                       
                         }                       
           
                         // function to display hash table                       
                         void                                     Hash::displayHash() {                       
                                                 for                                     (                                     int                                     i = 0; i < BUCKET; i++) {                       
                                                 cout << i;                       
                                                 for                                     (                                     auto                                     x : table[i])                       
                                                 cout <<                                     " --> "                                     << x;                       
                                                 cout << endl;                       
                                                 }                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 // array that contains keys to be mapped                       
                                                 int                                     a[] = {15, 11, 27, 8, 12};                       
                                                 int                                     n =                                     sizeof                                     (a)/                                     sizeof                                     (a[0]);                       
           
                                                 // insert the keys into the hash table                       
                                                 Hash h(7);                                     // 7 is count of buckets in                       
                                                 // hash table                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 h.insertItem(a[i]);                       
           
                                                 // delete 12 from hash table                       
                                                 h.deleteItem(12);                       
           
                                                 // display the Hash table                       
                                                 h.displayHash();                       
           
                                                 return                                     0;                       
                         }                       