C++：哈希表的实现

🕗 发布于 2024-11-07 05:50 散列表 c++ 哈希算法

一、哈希表的基本概念

1、负载因子：假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子 = N / M，负载因子有些地⽅也翻译为载荷因子/装载因子等，他的英文为load/factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低

2、哈希函数：这是哈希表的核心，它将键（Key）映射为一个数组索引（通常称为哈希值或哈希码）。哈希函数的设计至关重要，因为它直接影响到哈希表的性能。一个好的哈希函数应该能够均匀地分布键的哈希值，以减少哈希冲突。

3、哈希表（数组）：哈希表本质上是一个数组，它的大小（即数组的长度）是预先确定的。数组的每个位置都对应一个哈希值，该位置用于存储键和值的映射关系。

4、哈希冲突：由于哈希函数可能会将不同的键映射到相同的哈希值，因此需要一种机制来处理这种情况。常见的处理哈希冲突的方法有开放寻址法（如线性探测、二次探测等）和链地址法（也称为哈希链法）

二、开放定址法代码实现一个哈希表

总代码

template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131;
}

return hash;
}
};

struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
    return kv.first;
}
};

template<class K, class V, class MapKeyOfT, class HashFunc>
class Hashtable
{
public:
Hashtable()
:_table(__stl_next_prime(0))
,_n(0)
{}

inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}

bool Insert(const pair<K, V>& kv)
{
if (_n * 10 / _table.size() >= 7)
{
Hashtable<K, V> newt;
newt._table.resize(__stl_next_prime(_table.size() + 1));
for (auto e : _table)
{
if (e._state == EXIST)
{
newt.Insert(e._kv);
}
}

_table.swap(newt._table);
}

        MapKeyOfT kot;
        HashFunc hash;
size_t hash0 = hash(kot(kv) % _table.size();
size_t hash1 = hash0;
size_t i = 1;
while (_table[hash1]._state != EMPTY)
{
hash1 = (hash0 + i) % _table.size();
i++;
}

_table[hash1]._kv = kv;
_table[hash1]._state = EXIST;
_n++;

return true;
}

bool Erase(const K& key)
{
Hashtable<K, V, MapKeyOfT, HashFunc>* pos = Find(key);

if (pos)
{
pos->_state = DELETE;
_n--;
return true;
}
else
return false;
}

    Hashtable<K, V>* Find(const K& key)
{
        MapKeyOfT kot;
        HashFunc hash; 
size_t hash0 = hash(kot(key)) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}

// 线性探测
hashi = (hash0 + i) % _tables.size();
++i;
}

return nullptr;
}

private:
vector<HashtableDate<K, V>> _table;
size_t _n;
};

其基本思想是，当发生哈希冲突（即两个不同的键被映射到哈希表的同一位置）时，通过一定的探测方法找到下一个可用的哈希地址。

原理

哈希函数：首先，需要一个哈希函数将键映射到哈希表的索引。常见的哈希函数包括取模运算（例如，hash_value = key % _table.size（）），其中_table.size（）是哈希表的大小。

冲突处理：当发生冲突时，开放定址法通过探测序列来找到下一个可用的位置。探测序列可以是线性的、二次的或基于另一个哈希函数的。

线性探测：每次冲突时，按顺序检查下一个位置，直到找到一个空位置或回到起始位置。

开放定址法的哈希表结构里应有一个枚举类型来记录每个位置的状态（存在、空和删除）

用一个 HashData 结构体来存放节点的数据和状态，最后用 HashTable 类里用一个vector对象来存放一个一个的节点。

开放定址法的哈希表结构：

enum State
{
    EXIST,
    EMPTY,
    DELETE
};

template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    State _state = EMPTY;
};

template<class K, class V，class>
class HashTable
{ 
private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0; // 表中存储数据个数
};

哈希表的插入

如果我们vector开11个空间，当我们要插入数据的时候，将插入的值 % 容器的容量得到要映射的位置，然后将值插入在这个位置上。

例如：插入{19 , 30 , 52 , 63 , 11 , 22}，当插入 19 的时候，先用 19 % 11 得到 8，将 19 插入在 8这个位置上，但当插入 30 的时候，映射的位置也是 8 ，这时候就发生了哈希冲突，我们需要判断一下下一个位置能否插入，遇到状态为空的时候就可以插入了，重复存在，直至负载因子 >= 0.7。

bool Insert(const pair<K, V>& kv)
{
size_t hash0 = kv.first % _table.size();
size_t hash1 = hash0;
size_t i = 1;
while (_table[hash1]._state != EMPTY)
{
hash1 = (hash0 + i) % _table.size();
i++;
}
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
    return true;
}

为了方便取到 pair <K, V> 里的K的数据或类型，我们可以写一个仿函数来得到。

struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
    return kv.first;
}
};

但这里的类型刚刚好是整形，可以用 % ，如果我们要插入字符类型的数据怎么办，它不能映射到对应的值，这时候我们可以写一个仿函数来使得 字符类型的数据变为整形类型。

template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131;
}

return hash;
}
};

这时候我们的插入代码就变成这样了

bool Insert(const pair<K, V>& kv)
{
    HashFunc hash;
    MapKeyOfT kot;
size_t hash0 = hash(kot(kv) % _table.size();
size_t hash1 = hash0;
size_t i = 1;
while (_table[hash1]._state != EMPTY)
{
hash1 = (hash0 + i) % _table.size();
i++;
}
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
    return true;
}

但当 负载因子 >= 0.7 的时候，我们需要扩容，确保 负载因子 <= 0.7。

bool Insert(const pair<K, V>& kv)
{
if (_n * 10 / _table.size() >= 7)
{
Hashtable<K, V> newt;
newt._table.resize(__stl_next_prime(_table.size() + 1));
for (auto e : _table)
{
if (e._state == EXIST)
{
newt.Insert(e._kv);
}
}

_table.swap(newt._table);
}

        MapKeyOfT kot;
        HashFunc hash;
size_t hash0 = hash(kot(kv) % _table.size();
size_t hash1 = hash0;
size_t i = 1;
while (_table[hash1]._state != EMPTY)
{
hash1 = (hash0 + i) % _table.size();
i++;
}

_table[hash1]._kv = kv;
_table[hash1]._state = EXIST;
_n++;

return true;
}
}

哈希表的查找

我们从要查找的值的映射开始寻找，一个接一个的寻找，若都找到状态为空的位置都没有找到，那就查找失败，返回nullptr。

Hashtable<K, V>* Find(const K& key)
{
    MapKeyOfT kot;
    HashFunc hash; 
size_t hash0 = hash(kot(key)) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
// 线性探测
hashi = (hash0 + i) % _tables.size();
++i;
}
return nullptr;
}

哈希表的删除

哈希表的删除，我们只需要将找到位置的状态设为空状态即可。


bool Erase(const K& key)
{
Hashtable<K, V, MapKeyOfT, HashFunc>* pos = Find(key);

if (pos)
{
pos->_state = DELETE;
_n--;
return true;
}
else
return false;
}

原文地址：https://blog.csdn.net/Another_Shi/article/details/143509630

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：通过 SSH 连接远程 Ubuntu 服务器
下一篇：Webserver(4.4)多进程/多线程实现并发服务器

【无标题】
在 Android 中使用单例模式时，生命周期和内存管理需要格外注意，因为 Android 应用的生命周期受到系统的严格管理。单例对象持有短生命周期 Context 或其他 UI 元素的引用（如 Ac
阅读更多2024-11-07
Java 中的 try-with-resources 详解
在 Java 7 之前，处理资源关闭通常使用 `try-catch-finally` 块。虽然这种方式可以确保资源被正确关闭，但代码显得冗长且容易出错。Java 7 引入了 `try-with-res
阅读更多2024-11-07
FTP、ISCSI、CHRONY、DNS、NFS、DOCKER、MARIADB、NGINX、PHP、CA各服务开启方法
SCSI 配置通常涉及磁盘管理和硬件设备设置。如果有特定的 SCSI 配置需求，可以编辑 /etc/fstab 来挂载 SCSI 磁盘，或者根据需求安装相关驱动程序。配置文件位于 /etc/named
阅读更多2024-11-07
服务器开放了mongodb数据库的外网端口，但是用mongodbCompass还是无法连接。
数据库的配置文件中有个bingIp也就是绑定固定的ip才能访问数据库，默认是127.0.0.1也就是只能本地访问，所以无法连接。设置为0.0.0.0则表示所有地址都能访问。最后再确定一下防火墙的端口是
阅读更多2024-11-07
rclone 挂载是否会占用服务器的存储
直接挂载：不会占用服务器的存储空间。使用缓存：会占用服务器的存储空间，具体占用量取决于缓存配置。使用缓冲：会占用服务器的存储空间，具体占用量取决于缓冲配置。日志和临时文件：会占用少量的存储空间。文件系
阅读更多2024-11-07
HarmonyOS Next（鸿蒙星河版）侧载应用
仅需登录华为账号, 开启手机开发者模式和usb调试，即可安装任意hap应用 (tip: 必须保持开发者模式才能正常使用哦)这个版本支持无线安装哦！github找到了个项目。
阅读更多2024-11-07
MyBatis-Plus条件构造器：构建安全、高效的数据库查询
MyBatis-Plus 提供了一套强大的条件构造器（Wrapper），用于构建复杂的数据库查询条件。
阅读更多2024-11-07
反射一般在哪些场景中使用
反射机制在Java等语言中允许在运行时动态地获取类的信息、调用方法、访问属性等，主要用于以下场景
阅读更多2024-11-07
Mybatis基于注解的关系查询
以案例说明基于注解的关系查询。
阅读更多2024-11-07
马斯克押宝特朗普连任后的AI技术新格局猜想
马斯克助力特朗普连任后的AI技术格局,呈现出深度整合、跨领域创新、国际竞争加剧的特点。既抱着期待的心情希望AI的发展越来越好，同时作为老美最大的竞争者，咱们也得咬牙跟进。不过我想咱们的国家队也会大力扶
阅读更多2024-11-07