数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 哈希表链地址法程序
哈希是一种将任意长度的数据元素映射到固定大小键的方法。哈希的工作原理是键值对。
哈希函数是哈希映射中执行映射的函数。作为哈希函数输入给出的数据元素可能获得相同的哈希键。在这种情况下，元素可能会重叠。为了避免具有相同哈希键的元素重叠，引入了链地址法的概念。
创建哈希映射
为了创建哈希映射，我们需要哈希函数来定义数据元素的索引值。
我们有一个包含 n 个桶的哈希表。要将节点插入哈希表，我们给出一个哈希函数为
hashIndex = key % noOfBuckets
现在，我们将使用此哈希函数并计算每个插入到哈希映射中的值的哈希索引。
插入元素并计算给定键值的哈希索引，然后将新节点插入到列表的末尾。
要删除节点，我们将计算哈希索引，并在对应于哈希索引的桶中搜索桶中的元素并将其删除。
示例
#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
更新于: 2019年9月19日
2K+ 浏览量
广告