C语言哈希表概念超详细讲解
动名词 人气:01. 哈希概念
哈希其实在学排序时已经用过了，就是计数排序。计数排序也是用的一种映射关系。
比如对此数组进行 计数排序 ：1 1 9 9 9 3 3 8 8
我用的是绝对映射 ，所以开辟的数组空间 它的大小 必须 能映射到 最大的元素。
但是 对于哈希来讲，可以用决定映射嘛？当然不可以，如果是绝对映射会造成很大的空间浪费。所以 哈希 用的是 取模的方式来存 数据。
比如 ： 哈希表 的空间 我给定 只能存放 10个元素
存进来的数 对10进行取模 ，那么必定可以存方到 这个哈希表中。
比如：存 100 ，它对10取模得 0，那它就存在第一个位置；存 52 ，它对10进行取模得 2，那它就存到 下标为 2的位置。
也就是说 无论多大的数据，都可以存到哈希表中。但是 有两个 问题：
- 数据都能进行取模吗？假如我要求哈希表中存的是一个字符串，字符串不能进行取模运算，该怎么办？这就是数据可否哈希的问题，我们要把存进哈希表的数据，变为可哈希数据。
- 如果我存的是 4，下一次我要存的是 14。由于 4的位置已经被占了，我存的 14 该存放到何处？要是直接存，就意味着前面存的 4 会被覆盖，造成数据丢失。这就是哈希冲突问题。
2. 哈希冲突
造成了哈希冲突，得解决哈希冲突问题。
这里给出两种解决手段：
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
它相当于 如果我本来要存的位置，已经被占了，那么我就要在哈希表中找一个空位置存放。开散列：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
这种办法是常用的，它相当于 哈希表 每个位置 都存的是一个哈希桶，如果发送哈希冲突，直接就放在哈希桶里就行了。
3. 哈希实现
哈希表其实就是一个数组，数组中存的是节点数据，发生哈希冲突后，采用的是往后找空位置的方法。
图解：
(1) 10 % 6 == 4,所以插入到下标为4的位置
(2) 20%6==2,插入到下标为2的位置
(3)12%6 == 0,插入到下标为0的位置。
(4)22%6 == 4，插入到下标为4的位置，发现已经有数据了，所以向后找空位置。
(5)44%6 == 2，插入到下标为2的位置，发现已经有数据了，所以向后找空位置。
哈希桶其实就是一个数组，数组中存的是节点链表，发生哈希冲突后，是直接插入到节点链表中。
如果是哈希桶，存放上面的数据，是什么样的呢？
图解：
它相当于把发生冲突的数据 挂在了 冲突位置的下面。
3.1 闭散列(哈希表)
#include<vector>
#include<iostream>
using namespace std;
namespace hash_table
{
enum status
{
Empty,
Exist,
Delete
};
template<class K,class V>
struct hashdate
{
pair<K, V> _kv;
status _status = Empty;
};
template<class K,class V>
class close_hashtable
{
typedef hashdate<K, V> Node;
private:
vector<Node> _tables;
size_t _n = 0;
public:
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
size_t start = key % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status != Empty)
{
if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
return &_tables[index];
i++;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
return false;
ret->_status = Delete;
_n -= 1;
return true;
}
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
close_hashtable<K, V> tmp;
tmp._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
tmp.insert(_tables[i]._kv);
}
_tables.swap(tmp._tables);
}
size_t start = kv.first % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status == Exist)
{
i++;
index = start + i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._status = Exist;
_n += 1;
return true;
}
};
}以上就是闭散列的实现。我们来一步一步的解析以上代码。
(1) 用枚举常量来 标记 哈希表中 每个位置的状态，状态有 空，不为空，被删除。
大家可能会对 被删除这个状态产生疑问，一个位置 不就是 有数据和没数据吗？主要是大家想 如果 直接物理上删除，把位置 状态设置为 空，那么 就会影响后面的数据。
比如：删除 5 这个数据、
直接将 5 的位置 设置为空，那么 15 这个数据 会受到影响。因为 对 哈希表大小取模后，等于 5 的 不一定只有 5，还有 15，25，35。如果 将 5位置直接设置 为 空，就相当于 后面的数据中 已经没有 15，25，35 了。具体我们往下看查找的实现。
enum status
{
Empty,
Exist,
Delete
};
(2) 哈希表中的数据类型，以及哈希表的底层结构
哈希表中的数据类型，是一个结构体 ，包括了 一个键值对和状态：
template<class K,class V>
struct hashdate
{
pair<K, V> _kv;
// 默认状态为空
status _status = Empty;
};
哈希表的底层结构，可以是一个数组，还得有一个 无符号整数用来处理 哈希表中数据的个数：
typedef hashdate<K, V> Node; private: vector<Node> _tables; size_t _n = 0;
(3) 哈希表的查找
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
size_t start = key % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status != Empty)
{
if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
return &_tables[index];
i++;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
注意： while循环中，它的条件是 _tables[index]._status != Empty 说明 即使当下位置状态是 Delete 也会往后找 要查找的数据。这也解释了上文中所述。
找到了的条件是 (_tables[index]._kv.first == key && _tables[index]._status == Exist)
找到了返回 数据的地址，找不到 返回 空。
(4) 哈希表的插入
bool insert(const pair<K,V>& kv)
{
// 去重
Node* ret = find(kv.first);
if (ret)
{
return false;
}
// 扩容，后面讲，大家可能对这个条件有疑问
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
close_hashtable<K, V> tmp;
tmp._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
tmp.insert(_tables[i]._kv);
}
_tables.swap(tmp._tables);
}
size_t start = kv.first % _tables.size();
size_t i = 0;
size_t index = start + i;
// 找空的位置
while (_tables[index]._status == Exist)
{
i++;
index = start + i;
index %= _tables.size();
}
// 插入操作
_tables[index]._kv = kv;
_tables[index]._status = Exist;
_n += 1;
return true;
}
扩容是有说法的，首先我们要知道什么时候需要扩容？
- 如果为空，必然需要扩容，默认给 10 个大小即可。
- 当有效数据个数 除以 数组大小 大于等于 0.7 时，需要扩容
其实 有效数据个数 除以 数组大小 被称为 载荷因子，当载荷因子 大于 0.7时，就说明需要扩容了。这是大佬们搞出来的，我们还需要知道，载荷因子 越大就说明 填入哈希表的元素越多，越可能发送哈希冲突。
扩容的操作，我是 创建了一个新的哈希表，然后把原表中的数据插入到新表中。这里还有一个坑，就是，可不可以 直接将旧表的数据拷贝到新表中，答案是 不行。
举个例子：
原表是 ：
新表是：
直接拷贝的话是这样的：
看图也懂了哈，扩容后的表 是需要重新插入数据，因为 位置 可能会发送改变。
扩容完了，就是插入了，如果当下的位置是 Delete 或者 Eempty 那么就可以直接插入；否则就需要向后面查找空的位置，进行插入。
(5) 哈希表的删除
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
return false;
ret->_status = Delete;
_n -= 1;
return true;
}
删除很简单，就是将那个位置的状态改为 Delete，然后有效数据个数 减一 就行了。
3.1.1 闭散列的细节
首先，上面的哈希表其实还有问题。
比如： 不是所有的数据都可以取模，这个问题，并没有解决，上面实现是 直接取模。
所以还需要实现一个 将数据转为可哈希数据的仿函数。为什么是仿函数呢？因为 数据类型较多，情况不一，这里还用到了模板特化的知识，大家坐稳扶好。
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string& key)
{
size_t value = 0;
for (auto ch : key)
{
value *= 31;
value += ch;
}
return value;
}
};
第二个就是模板的特化， 它的作用就是 将string对象 可以转换 成 整型(可哈希)。至于为什么每次都乘以 31 ，这也是大佬的手法，因为多次测试后发现，乘以 31 会使 哈希冲突少一些。
默认情况下，就是直接返回 key，也就是默认情况下都是可哈希的。
如果 你要哈希一个自定义对象，那么还得是用模板的特化，自己处理。
所以有了仿函数之后，我们就不必担心，传过去的数据是否能够 被哈希了，靠仿函数去处理。具体怎么用，后面会给出完整代码。
其次，还有一个问题，就是 线性探索和二次探索：
大家可能对这俩词不陌生，也就是哈希表中，发生哈希冲突后，查找空位置时，是连续的查找空位置还是 平方次的跳跃的查找。
当然是二次查找更优秀一些，上面的程序用的是线性探索，也就是 那个 i++，它就是连续的往后查找。为什么呢？因为 如果是线性探索，它会比较拥挤，连续位置太多，从而引发踩踏效应，也就导致，每次来的数据，都需要去找空位置。
二次探索很简单，把 i++ 变成 i =i *i。
3.1.2 优化后的闭散列
enum status
{
Empty,
Exist,
Delete
};
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string& key)
{
size_t value = 0;
for (auto ch : key)
{
value *= 31;
value += ch;
}
return value;
}
};
template<class K,class V>
struct hashdate
{
pair<K, V> _kv;
status _status = Empty;
};
template<class K,class V,class Hashfunc = hash<K>>
class close_hashtable
{
typedef hashdate<K, V> Node;
private:
vector<Node> _tables;
size_t _n = 0;
public:
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hashfunc hf;
size_t start = hf(key)% _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status != Empty)
{
if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
return &_tables[index];
i = i*i;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
return false;
ret->_status = Delete;
_n -= 1;
return true;
}
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
close_hashtable<K, V> tmp;
tmp._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
tmp.insert(_tables[i]._kv);
}
_tables.swap(tmp._tables);
}
Hashfunc hf;
size_t start = hf(kv.first) % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status == Exist)
{
i = i*i;
index = start + i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._status = Exist;
_n += 1;
return true;
}
};3.2 扩散列(哈希桶)
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K,V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv),
_next(nullptr)
{
}
};
template<class K,class V,class Hashfunc = Hash<K>>
class link_hashtable
{
typedef HashNode<K, V> Node;
private:
vector<Node*> _tables;
size_t _n = 0;
public:
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hashfunc hf;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == key)
return cur;
else
cur = cur->_next;
}
return nullptr;
}
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
{
return false;
}
Hashfunc hf;
size_t index = hf(key) % _tables.size();
Node* pre = nullptr;
Node* cur = _tables[index];
while (cur)
{
Node* next = cur->_next;
if (cur->_kv.first == key)
{
if (pre == nullptr)
{
_tables[index] = next;
}
else
{
pre->_next = next;
}
delete cur;
_n -= 1;
return true;
}
else
{
pre = cur;
cur = next;
}
}
return false;
}
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
Hashfunc hf;
if (_n == _tables.size())
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(cur->_kv.first) % newTables.size();
// 头插
cur->_next = newTables[index];
newTables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t index = hf(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[index];
_tables[index] = newnode;
}
};
}(1) 哈希桶的节点以及底层结构
哈希桶的节点是一个单向链表，它得有数据，是一个键值对，还得有 下一个节点的指针。
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K,V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv),
_next(nullptr)
{
}
};
哈希桶的底层，是一个数组，数组中存的是节点的指针，当然还得有一个有效数据的个数，它是用于判断是否需要扩容的。
template<class K,class V,class Hashfunc = Hash<K>>
class link_hashtable
{
typedef HashNode<K, V> Node;
private:
vector<Node*> _tables;
size_t _n = 0;
public:
}
(2) 哈希桶的查找
查找也简单呢，就是迭代往下查找，如果找到就返回，位置的指针，找不到就返回空。
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hashfunc hf;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == key)
return cur;
else
cur = cur->_next;
}
return nullptr;
}
(3) 哈希桶的插入
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
Hashfunc hf;
if (_n == _tables.size())
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(cur->_kv.first) % newTables.size();
// 头插
cur->_next = newTables[index];
newTables[index] = cur;
cur = next;
}
// 将旧桶置空
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t index = hf(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[index];
_tables[index] = newnode;
}
先考虑插入的数据的key有没有重复，如果重复了那就直接返回。其实就是个头插，中间代码很多是扩容，我们先不考虑扩容，其实 插入的代码就是：
size_t index = hf(kv.first) % _tables.size(); Node* newnode = new Node(kv); newnode->_next = _tables[index]; _tables[index] = newnode;
扩容的话，和哈希表同理，扩完容之后，哈希桶的位置可能会变化，所以要自己完成重新插入工作，不过扩容的条件不再是 载荷因子 >=0.7，而是 载荷因子等于 1时才扩容。
(4) 哈希桶的删除
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
{
return false;
}
Hashfunc hf;
size_t index = hf(key) % _tables.size();
// 前一个节点
Node* pre = nullptr;
//桶的第一个节点
Node* cur = _tables[index];
while (cur)
{
// 桶的下一个节点
Node* next = cur->_next;
// 找到要删除的节点
if (cur->_kv.first == key)
{
// 头删
if (pre == nullptr)
{
_tables[index] = next;
}
// 中间删或者尾删
else
{
pre->_next = next;
}
delete cur;
_n -= 1;
return true;
}
else
{
// 往桶下面迭代
pre = cur;
cur = next;
}
}
}
一上来 先检查要删除的数据是否存在，存在就往下走，不存在直接返回。
然后就是 找要删除的数据在那个桶中：
Hashfunc hf; size_t index = hf(key) % _tables.size();
再就是 在这个桶中 删除，我们需要考虑几件事:
- 桶中是单向链表，删除的话我需要维护链表的关系，所以需要记录删除数据的前一个数据
- 要删除的节点如果是头节点，就不需要维护和前一个数据的关系，因为它就是第一个
- 要删除的节点在中间或者最后，那就需要维护和前一个的关系
3.2.1 扩散列的细节
扩散列是有极端情况的，比如 我开辟的数组大小是 10 ，插入的数据是 10，20，30，40，50，60 …… 10000000000，这些数据都插入到了一个桶里面。
会导致哈希桶变成这样：
会发现，效率退化了，哈希的查找一般情况是O(1) ，但是这种情况下，退化成O(n)了。所以应该怎么办？大佬其实是给出解决方案的，就是一个桶中的元素超过了某一个量，那么就会将这个桶中的数据用红黑树组织起来，对于这个量jave和C++还不一样。
这就是所谓的桶中种树。
但是上面的哈希桶，我没有支持这种高级操作，我觉得只要了解这个事情就行了，至于实现，也是可以的，但是对于我们要学习哈希，没太大帮助。
4. 哈希表和哈希桶的比较
哈希桶处理溢出，需要增设链接指针，似乎增加了存储开销。
事实上： 由于哈希表必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。
哈希表处理哈希冲突用的是抢占别的位置，可能会导致数据比较阻塞，也就是每进来一个数据都需要去抢占别人的位置。
哈希桶处理哈希冲突用的是在冲突位置，增加链节点的方法，但是有可能造成，单向链表太长从而影响效率，所以需要将单向链表变为红黑树管理起来。
5. 结尾语
学完哈希，能干什么？说实话哈希很重要，学数据结构，你说你不会哈希，那么就相当于你白学数据结构了，就是这么夸张哈，以后工作也会大量用到哈希的。所以大家加油。在我的下一篇文章中，会利用哈希桶去实现unordered_map和unordered_set，也算是用上了哈希。当然位图呀，布隆过滤器呀，海量处理数据等 都会用到哈希。
加载全部内容