Hash Tables(chaining)
程序员文章站
2022-04-24 12:45:06
...
Hash Table,叫做哈希表,也叫做散列表。
概念:通过某种对应关系h,使得每一个元素和储存位置一一对应。这种对应关系称为哈希函数。它最大的优点就是插入、搜索和删除得很快(O(1))。
碰撞(Collision):不同的关键字对应同一个哈希地址
本文主要介绍的是解决碰撞的方法之一:chaining
原理:
In chainning,wo palce all the elements that hash to the same plot into the same list.
如果不同的key通过hash function得到的相同结果,那么就将他们放在同一个list中。如下图:
操作:
1.查找:
先找到key的索引:index=hashFunction(key)
然后遍历这个链表:
// get the hash index of key
int index = hashFunction(key);
// find the key in (inex)th list
list <int> :: iterator i;
for (i = table[index].begin();
i != table[index].end(); i++) {
if (*i == key)
break;
}
2.插入:
void Hash::insertItem(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
3.删除:
首先先查找这个元素,如果找到的话,则删除
void Hash::deleteItem(int key)
{
// get the hash index of key
int index = hashFunction(key);
// find the key in (inex)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);
}
完整代码:
// CPP program to implement hashing with chaining
#include<iostream>
#include <list>
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 (inex)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;
}
推荐阅读
-
vue vue-Router默认hash模式修改为history需要做的修改详解
-
php的hash算法介绍
-
Nginx could not build the server_names_hash 错误的解决办法
-
[20180914]oracle 12c 表 full_hash_value如何计算.txt
-
oracle分区表之hash分区表的使用及扩展
-
php操作redis中的hash和zset类型数据的方法和代码例子
-
PHP中对各种加密算法、Hash算法的速度测试对比代码
-
PHP的password_hash()使用实例
-
BZOJ4650: [Noi2016]优秀的拆分(hash 调和级数)
-
BZOJ4598: [Sdoi2016]模式字符串(点分治 hash)