C语言哈希表概念超详细讲解

Anna ·

更新时间:2024-11-10

· 1203 次阅读

1. 哈希概念

2. 哈希冲突

3. 哈希实现

3.1 闭散列(哈希表)

3.1.1 闭散列的细节

3.1.2 优化后的闭散列

3.2 扩散列(哈希桶)

3.2.1 扩散列的细节

4. 哈希表和哈希桶的比较

5. 结尾语

1. 哈希概念

哈希其实在学排序时已经用过了，就是计数排序。计数排序也是用的一种映射关系。

比如对此数组进行计数排序：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，也算是用上了哈希。当然位图呀，布隆过滤器呀，海量处理数据等都会用到哈希。

到此这篇关于C语言哈希表概念超详细讲解的文章就介绍到这了,更多相关C语言哈希表内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！

哈希表哈希 C语言

1024 个赞