数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
时尚研究
法律研究使用线性探查开放定址法在 C++ 中实现自己的哈希表
哈希表是一种存储键值对的数据结构。哈希表使用哈希函数计算数组中的索引，将元素插入或搜索到该索引中。
线性探查是开放定址哈希表中一种解决冲突的技术。在此方法中，哈希表中的每个单元格都存储一个键值对。如果发生冲突，即映射一个新键到哈希表中的一个单元格，而该单元格已被另一个键占用，则该方法将搜索表中的下一个空位置并将新键插入其中。
这是一个使用线性探查来实现哈希表的 C++ 程序。
算法
Begin Declare function Insert(int k, int v) Declare hash_val, init, delindex to the integer pointer. initialize hash_val = HashFunc(k) intialize init = -1 intialize delindex = -1 while (hash_val != init and (ht[hash_val] == DelNode::getNode() or ht[hash_val] != NULL and ht[hash_val]->k != k)) if (init == -1) init = hash_val if (ht[hash_val] == DelNode::getNode()) delindex = hash_val hash_val = HashFunc(hash_val + 1) if (ht[hash_val] == NULL or hash_val == init) if(delindex != -1) ht[delindex] = new HashTable(k, v) else ht[hash_val] = new HashTable(k, v) if(init != hash_val) if (ht[hash_val] != DelNode::getNode()) if (ht[hash_val] != NULL) if (ht[hash_val]->k== k) ht[hash_val]->v = v else ht[hash_val] = new HashTable(k, v) End.
搜索键值
Begin Declare Function SearchKey(int k) Declare hash_val, init of the integer datatype. initialize hash_val = HashFunc(k) intialize init = -1 while (hash_val != init and (ht[hash_val] == DelNode::getNode() or ht[hash_val] != NULL and ht[hash_val]->k!= k if (init == -1) init = hash_val hash_val = HashFunc(hash_val + 1) if (ht[hash_val] == NULL or hash_val == init) return -1 else return ht[hash_val]->v End.
删除
Begin Declare Function Remove(int k) Declare hash_val, init of the integer datatype. initialize hash_val = HashFunc(k) initialize init = -1 while (hash_val != init and (ht[hash_val] == DelNode::getNode() or ht[hash_val] != NULL and ht[hash_val]->k!= k)) if (init == -1) init = hash_val hash_val = HashFunc(hash_val + 1) if (hash_val != init and ht[hash_val] != NULL) delete ht[hash_val] ht[hash_val] = DelNode::getNode() End.
示例代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int T_S = 5;
class HashTable {
public:
int k;
int v;
HashTable(int k, int v) {
this->k = k;
this->v = v;
}
};
class DelNode:public HashTable {
private:
static DelNode *en;
DelNode():HashTable(-1, -1) {}
public:
static DelNode *getNode() {
if (en == NULL)
en = new DelNode();
return en;
}
};
DelNode *DelNode::en = NULL;
class HashMapTable {
private:
HashTable **ht;
public:
HashMapTable() {
ht = new HashTable* [T_S];
for (int i = 0; i < T_S; i++) {
ht[i] = NULL;
}
}
int HashFunc(int k) {
return k % T_S;
}
void Insert(int k, int v) {
int hash_val = HashFunc(k);
int init = -1;
int delindex = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k != k)) {
if (init == -1)
init = hash_val;
if (ht[hash_val] == DelNode::getNode())
delindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (ht[hash_val] == NULL || hash_val == init) {
if(delindex != -1)
ht[delindex] = new HashTable(k, v);
else
ht[hash_val] = new HashTable(k, v);
}
if(init != hash_val) {
if (ht[hash_val] != DelNode::getNode()) {
if (ht[hash_val] != NULL) {
if (ht[hash_val]->k== k)
ht[hash_val]->v = v;
}
} else
ht[hash_val] = new HashTable(k, v);
}
}
int SearchKey(int k) {
int hash_val = HashFunc(k);
int init = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k!= k)) {
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (ht[hash_val] == NULL || hash_val == init)
return -1;
else
return ht[hash_val]->v;
}
void Remove(int k) {
int hash_val = HashFunc(k);
int init = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k!= k)) {
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && ht[hash_val] != NULL) {
delete ht[hash_val];
ht[hash_val] = DelNode::getNode();
}
}
~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;
if(hash.SearchKey(k) == -1) {
cout<<"No element found at key "<<k<<endl;
continue;
} else {
cout<<"Element at key "<<k<<" : ";
cout<<hash.SearchKey(k)<<endl;
}
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: 10 Enter key at which element to be inserted: 2 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: 4 Enter key at which element to be inserted: 5 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: 12 Enter key at which element to be inserted: 3 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 15 Enter correct option 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: 15 Enter key at which element to be inserted: 8 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 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: 3 Enter key of the element to be deleted: 2 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: 2 No element found at key 2 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 4
更新日期： 30-Jul-2019
921 次浏览
广告