C++ 链式哈希程序

17 Mar 2025 | 5 分钟阅读

哈希表链表法究竟是什么？

链表法是一种哈希表冲突避免技术。

当哈希表中的两个键哈希到同一个索引时，就会发生冲突。冲突是一个问题，因为哈希表中的每个槽位只应该容纳一个元素。

链表法

链表法中的哈希表是一个链表数组，每个索引都有自己的链表。

所有映射到相同索引的键值对都将存储在该索引的链表中。

链表法的优点

通过链表法，哈希表中的插入始终以 O(1) 的时间复杂度进行，因为链表允许在常数时间内插入。
只要有足够的空间，链式哈希表理论上可以无限增长。
链式哈希表永远不需要调整大小。

链表法的实现

让我们编写一个哈希函数，以确保我们的哈希表有 'N' 个桶。

要将节点添加到哈希表，我们必须首先确定给定键的哈希索引。它也可以使用哈希函数计算。

示例：哈希索引 = 键 % 桶数

插入： 移动到与上面计算的哈希索引对应的桶，并将新节点插入到列表的末尾。

删除： 要从哈希表中删除一个节点，计算键的哈希索引，移动到与计算的哈希索引对应的桶，在当前桶中的列表中搜索具有给定键的节点，并将其删除（如果找到）。

算法

对于插入

Begin
   Declare Function Insert(int k, int v)
      int hash_v = HashFunc(k)
      HashTableEntry* p = NULL
      HashTableEntry* en = ht[hash_v]
      while (en!= NULL)
         p = en
         en= en->n
      if (en == NULL)
         en = new HashTableEntry(k, v)
         if (p == NULL)
            ht[hash_v] = en
         else
            p->n= en
      else
         en->v = v
End.

对于删除

Begin
   Declare Function Remove(int k)
      int hash_v = HashFunc(k)
      HashTableEntry* en = ht[hash_v]
      HashTableEntry* p= NULL
      if (en == NULL or en->k != k)
         Print "No Element found at key"
         return
      while (en->n != NULL)
         p = en
         en = en->n
      if (p != NULL)
         p->n = en->n
      delete en
         Print "Element Deleted"
End.

对于搜索

Begin
   Declare function SearchKey(int k)
      int hash_v = HashFunc(k)
      bool flag = false
      HashTableEntry* en = ht[hash_v]
      if (en != NULL)
         while (en != NULL)
            if (en->k == k)
               flag = true
            if (flag)
               Print "Element found at key"
               Print en->v
            en = en->n
      if (!flag)
         Print "No Element found at key"
End.

编码

#include <iostream>
const int T_S = 200;
using namespace std;
struct HashTableEntry {
   int v, k;
   HashTableEntry *n;
   HashTableEntry *p;
   HashTableEntry(int k, int v) {
      this->k = k;
      this->v = v;
      this->n = NULL;
   }
};
class HashMapTable {
   public:
      HashTableEntry **ht, **top;
      HashMapTable() {
         ht = new HashTableEntry*[T_S];
         for (int i = 0; i < T_S; i++)
            ht[i] = NULL;
      }
      int HashFunc(int key) {
         return key % T_S;
      }
      void Insert(int k, int v) {
         int hash_v = HashFunc(k);
         HashTableEntry* p = NULL;
         HashTableEntry* en = ht[hash_v];
         while (en!= NULL) {
            p = en;
            en = en->n;
         }
         if (en == NULL) {
            en = new HashTableEntry(k, v);
            if (p == NULL) {
               ht[hash_v] = en;
            } else {
               p->n = en;
            }
         } else {
            en->v = v;
         }
      }
      void Remove(int k) {
         int hash_v = HashFunc(k);
         HashTableEntry* en = ht[hash_v];
         HashTableEntry* p = NULL;
         if (en == NULL || en->k != k) {
            cout<<"No Element found at key "<<k<<endl;
            return;
         }
         while (en->n != NULL) {
            p = en;
            en = en->n;
         }
         if (p != NULL) {
            p->n = en->n;
         }
         delete en;
         cout<<"Element Deleted"<<endl;
      }
      void SearchKey(int k) {
         int hash_v = HashFunc(k);
         bool flag = false;
         HashTableEntry* en = ht[hash_v];
         if (en != NULL) {
            while (en != NULL) {
               if (en->k == k) {
                  flag = true;
               }
               if (flag) {
                  cout<<"Element found at key "<<k<<": ";
                  cout<<en->v<<endl;
               }
               en = en->n;
            }
         }
         if (!flag)
            cout<<"No Element found at key "<<k<<endl;
      }
      ~HashMapTable() {
         delete [] ht;
      }
};
int main() {
   HashMapTable hash;
   int k, v;
   int c;
   while (1) {
      cout<<"1.Insert element into the table"<<endl;
      cout<<"2.Search element from the key"<<endl;
      cout<<"3.Delete element at a key"<<endl;
      cout<<"4.Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter element to be inserted: ";
            cin>>v;
            cout<<"Enter key at which element to be inserted: ";
            cin>>k;
            hash.Insert(k, v);
         break;
         case 2:
            cout<<"Enter key of the element to be searched: ";
            cin>>k;
            hash.SearchKey(k);
         break;
         case 3:
            cout<<"Enter key of the element to be deleted: ";
            cin>>k;
            hash.Remove(k);
         break;
         case 4:
            exit(1);
         default:
            cout<<"\nEnter correct option\n";
      }
   }
   return 0;
}

输出

1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 2
Enter key at which element to be inserted: 1
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 3
Enter key at which element to be inserted: 4
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 7
Enter key at which element to be inserted: 6
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 8
Enter key at which element to be inserted: 9
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 2
Enter key of the element to be searched: 6
Element found at key 6: 7
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 2
Enter key of the element to be searched: 7
No Element found at key 7
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 3
Enter key of the element to be deleted: 9
Element Deleted
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. ExitC
Enter your choice: 4

时间复杂度

搜索： O (1+(n/m))
删除： O (1+(n/m))
其中 n = 哈希表中的槽位数量
m = 要插入的键的数量
这里的 n/m 是负载因子。
负载因子必须尽可能小。

下一个主题所有元素都是斐波那契数的最大子集

← 上一个下一个 →

C++ 链式哈希程序

哈希表链表法究竟是什么？

链表法

链表法的优点

链表法的实现

算法

编码

时间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 链式哈希程序

哈希表链表法究竟是什么？

链表法

链表法的优点

链表法的实现

算法

编码

时间复杂度

相关帖子

C++ 和 JAVA 的相似与区别

C++ DSA

C++ 运算符重载规则

C++ 自定义排序字符串

C++ - 函子与函数的区别

C++ basic_istream::peek() 方法

C++ std::allocator()

C++ multimap get_allocator() 函数

std::swap 和 std::vector::swap 的区别

C++ 中心二十面体数程序

订阅 Tpoint Tech

联系信息

关注我们