用双链表链接的哈希表-yiteyi-C++库

先决条件—— 哈希简介 , 使用单链表的哈希表 & 用Java实现我们自己的哈希表

null

使用双链表链接实现哈希表与实现使用单链表的哈希表唯一的区别是链表的每个节点都有下一个和上一个节点的地址。这将加快从列表中添加和删除元素的过程，因此时间复杂度将大大降低。 例子：

如果我们有一个单链表：
1->2->3->4
如果我们是3，并且需要删除它，那么2需要与4链接，而从3开始，2不能被访问，因为它是单链接列表。所以，必须再次遍历这个列表，即O（n），但是如果我们有双链表，即。
1234
2和4可以从3访问，因此在O（1）中，3可以被删除。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

以下是上述方法的实施情况：

                     // C++ implementation of Hashtable                   
                     // using doubly linked list                   
                     #include <bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     const                               int                               tablesize = 25;                   
                             
                     // declaration of node                   
                     struct                               hash_node {                   
                                         int                               val, key;                   
                                         hash_node* next;                   
                                         hash_node* prev;                   
                     };                   
                             
                     // hashmap's declaration                   
                     class                               HashMap {                   
                     public                               :                   
                                         hash_node **hashtable, **top;                   
                             
                                         // constructor                   
                                         HashMap()                   
                                         {                   
                                         // create a empty hashtable                   
                                         hashtable =                               new                               hash_node*[tablesize];                   
                                         top =                               new                               hash_node*[tablesize];                   
                                         for                               (                               int                               i = 0; i < tablesize; i++) {                   
                                         hashtable[i] = NULL;                   
                                         top[i] = NULL;                   
                                         }                   
                                         }                   
                             
                                         // destructor                   
                                         ~HashMap()                   
                                         {                   
                                         delete                               [] hashtable;                   
                                         }                   
                             
                                         // hash function definition                   
                                         int                               HashFunc(                               int                               key)                   
                                         {                   
                                         return                               key % tablesize;                   
                                         }                   
                             
                                         // searching method                   
                                         void                               find(                               int                               key)                   
                                         {                   
                                         // Applying hashFunc to find                   
                                         // index for given key                   
                                         int                               hash_val = HashFunc(key);                   
                                         bool                               flag =                               false                               ;                   
                                         hash_node* entry = hashtable[hash_val];                   
                             
                                         // if hashtable at that index has some                   
                                         // values stored                   
                                         if                               (entry != NULL) {                   
                                         while                               (entry != NULL) {                   
                                         if                               (entry->key == key) {                   
                                         flag =                               true                               ;                   
                                         }                   
                                         if                               (flag) {                   
                                         cout <<                               "Element found at key "                   
                                         << key <<                               ": "                               ;                   
                                         cout << entry->val << endl;                   
                                         }                   
                                         entry = entry->next;                   
                                         }                   
                                         }                   
                                         if                               (!flag)                   
                                         cout <<                               "No Element found at key "                   
                                         << key << endl;                   
                                         }                   
                             
                                         // removing an element                   
                                         void                               remove                               (                               int                               key)                   
                                         {                   
                                         // Applying hashFunc to find                   
                                         // index for given key                   
                                         int                               hash_val = HashFunc(key);                   
                                         hash_node* entry = hashtable[hash_val];                   
                                         if                               (entry->key != key || entry == NULL) {                   
                                         cout <<                               "Couldn't find any element at this key "                   
                                         << key << endl;                   
                                         return                               ;                   
                                         }                   
                             
                                         // if some values are present at that key &                   
                                         // traversing the list and removing all values                   
                                         while                               (entry != NULL) {                   
                                         if                               (entry->next == NULL) {                   
                                         if                               (entry->prev == NULL) {                   
                                         hashtable[hash_val] = NULL;                   
                                         top[hash_val] = NULL;                   
                                         delete                               entry;                   
                                         break                               ;                   
                                         }                   
                                         else                               {                   
                                         top[hash_val] = entry->prev;                   
                                         top[hash_val]->next = NULL;                   
                                         delete                               entry;                   
                                         entry = top[hash_val];                   
                                         }                   
                                         }                   
                                         entry = entry->next;                   
                                         }                   
                                         cout <<                               "Element was successfully removed at the key "                   
                                         << key << endl;                   
                                         }                   
                             
                                         // inserting method                   
                                         void                               add(                               int                               key,                               int                               value)                   
                                         {                   
                                         // Applying hashFunc to find                   
                                         // index for given key                   
                                         int                               hash_val = HashFunc(key);                   
                                         hash_node* entry = hashtable[hash_val];                   
                             
                                         // if key has no value stored                   
                                         if                               (entry == NULL) {                   
                                         // creating new node                   
                                         entry =                               new                               hash_node;                   
                                         entry->val = value;                   
                                         entry->key = key;                   
                                         entry->next = NULL;                   
                                         entry->prev = NULL;                   
                                         hashtable[hash_val] = entry;                   
                                         top[hash_val] = entry;                   
                                         }                   
                             
                                         // if some values are present                   
                                         else                               {                   
                                         // traversing till the end of                   
                                         // the list                   
                                         while                               (entry != NULL)                   
                                         entry = entry->next;                   
                             
                                         // creating the new node                   
                                         entry =                               new                               hash_node;                   
                                         entry->val = value;                   
                                         entry->key = key;                   
                                         entry->next = NULL;                   
                                         entry->prev = top[hash_val];                   
                                         top[hash_val]->next = entry;                   
                                         top[hash_val] = entry;                   
                                         }                   
                                         cout <<                               "Value "                               << value <<                               " was successfully"                   
                                         " added at key "                               << key << endl;                   
                                         }                   
                     };                   
                             
                     // Driver Code                   
                     int                               main()                   
                     {                   
                                         HashMap hash;                   
                                         hash.add(4, 5);                   
                                         hash.find(4);                   
                                         hash.                               remove                               (4);                   
                                         return                               0;                   
                     }                   

输出：

Value 5 was successfully added at key 4
Element found at key 4: 5
Element was successfully removed at the key 4

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章