【C++】unordered_map（set）

🕗 发布于 2024-09-28 02:38 c++ 哈希算法散列表

前言

C++中的unordered容器（例如std::unordered_set、std::unordered_map等）底层是基于**哈希表（Hash Table）**实现的。哈希表是一种通过哈希函数将元素映射到特定“桶（bucket）”的容器，提供快速的查找、插入和删除操作。

unordered系列的实现（基哈希桶）

哈希表的基本结构

哈希表的核心思想是**将元素的值（或键）通过哈希函数（Hash Function）映射到哈希表中的某个桶（bucket）。每个桶通常是一个链表或其他数据结构，用来处理冲突。当不同的元素通过哈希函数得到相同的哈希值时，会出现哈希冲突（Hash Collision），**冲突的元素会被存储在同一个桶内。

哈希表的关键组成部分有：

哈希表（Hash Table）
unordered_map 和 unordered_set 底层使用哈希表来存储元素。
哈希表的核心是一个数组，这个数组的每个位置被称为一个“桶”（bucket）。
每个桶可以存储一个或多个元素，这些元素的键通过哈希函数映射到该桶中。
哈希函数（Hash Function）
哈希函数负责将键值映射到哈希表中的某个桶。
C++ 标准库允许用户提供自定义的哈希函数，默认情况下使用 std::hash 提供的哈希函数。
哈希函数的好坏直接影响到哈希表的性能：一个好的哈希函数应当均匀分布键值，减少冲突。
冲突处理（Collision Handling）
哈希冲突发生在不同的键被映射到同一个桶时。
C++ 的 unordered_map 和 unordered_set 使用开链法（Chaining）处理冲突。
在开链法中，每个桶内部实际上是一个链表或类似的结构，用于存储多个哈希冲突的元素。
这意味着即使有冲突发生，元素也不会丢失，而是通过链表来管理这些冲突的元素。
负载因子和扩展（Load Factor and Rehashing）
负载因子（Load Factor）定义为元素数量与桶数量的比值。当负载因子超过一个预设的阈值时，哈希表会进行扩展（即再散列 rehashing）。
扩展通常意味着分配一个更大的桶数组，并重新计算每个元素的哈希值，然后将它们放入新的桶中。
再散列的过程可以确保在负载因子较高时，哈希表的操作仍然是高效的。
迭代顺序
因为哈希表的存储结构无序，unordered_map 和 unordered_set 的迭代顺序是未定义的。
迭代顺序依赖于哈希函数和元素的插入顺序，以及哈希表的大小和当前负载因子。
时间复杂度
在理想情况下（即哈希冲突少），unordered_map 和 unordered_set 的插入、查找、删除操作的时间复杂度是 O(1)。
但在最坏情况下（大量冲突），这些操作的时间复杂度可能退化为 O(n)。

存储结构

类似于链表，在顺序表中存储一个一个节点。

template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;

HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};

table：使用 std::vector 存储多个链表，每个链表代表一个桶，链表中的元素是映射到这个桶的所有元素。
记录_n进行负载因子的储存
class KeyofT是作为仿函数是为了配合K型和KV结构适应的

template<class K,class T,class KeyofT,class HashFunc = defaultHashfunc<K>>
class HashTable
{
    public:
    ...
    private:
vector<Node*> _table;
size_t _n = 0;
};

哈希函数

在函数的内容的不确定的时候进行返回。
针对string字符串的直接进行特模板化。
针对26字母有不同的组合，要进行字符串的哈希化处理，目的是针对哈希冲突（本次采用 BKDR算法）参考：字符串哈希算法

template<class T>
struct defaultHashfunc
{
size_t operator()(const T& data)
{
return (size_t)data;
}
};
//模板特化
template<>
struct defaultHashfunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto& ch : str)
{
hash *= 131;

hash += ch;
}
return hash;
}
};

unordered插入操作

哈希计算
当你插入一个元素（比如在unordered_map中插入一个键值对），首先会调用哈希函数对键（key）进行哈希计算。这个哈希函数返回一个哈希值（通常是一个无符号整数类型，如std::size_t）。
这个哈希值会被用来确定元素应该存储在哪个桶（bucket）中。桶的数量通常是哈希表当前容量的一个因子。
桶的选择
哈希表根据哈希值和桶的数量来确定目标桶的位置。通常这是通过取模运算来完成的，即 hf(kot(data)) % _table.size()
在这个位置上，哈希表要检查这个桶是否已经存在元素，如果存在，则进行冲突处理。
冲突处理
如果目标桶已经有其他元素（即发生了哈希冲突），unordered_map 和 unordered_set 通过开链法（chaining）进行处理。
开链法意味着每个桶实际上包含一个链表或链表的类似结构。新元素将被添加到这个链表中。
元素存储
如果目标桶为空，则直接将新元素存储在该桶中。
如果目标桶不为空（发生冲突），则将元素追加到该桶的链表中。
在 unordered_map 中，如果插入的键已经存在，则插入操作不会改变哈希表，而是更新该键对应的值。
负载因子与再散列（Rehashing）
每次插入操作都会检查哈希表的负载因子（即元素数量与桶数量的比值）。
如果负载因子超过了哈希表的最大负载因子（max_load_factor()），哈希表会自动扩展，增加桶的数量并重新分配所有元素到新的桶中。这就是所谓的再散列（rehashing）。
再散列过程中，所有元素都将被重新哈希和插入新的桶中，这样可以保证哈希表的高效性

pair<iterator,bool> insert(const T& data)
{
KeyofT kot;
HashFunc hf;

iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it,false);
}

if (_n == _table.size())
{
size_t newsize = _table.size() * 2;
vector<Node*> newtable;
newtable.resize(newsize,nullptr);
for (int i = 0; i < _table.size() ;i++)
{
HashFunc hf;
size_t hashi = 0;

Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
hashi = hf(kot(cur->_data)) % newtable.size();
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);

}
size_t hashi = hf(kot(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode,this),true);
}

unordered删除操作

删除操作的底层流程：

哈希计算
对于基于键删除的操作（如 erase(const key_type& k)），首先会对给定的键 k 进行哈希计算，计算出哈希值。
根据哈希值确定该键可能存储在哪个桶中。
查找元素
哈希表在确定了桶的位置后，会在对应的桶（链表）中查找目标元素。
如果找到匹配的元素，哈希表会进行删除操作；如果未找到，erase 返回 0，表示没有元素被删除。
删除元素
删除元素时，需要从桶的链表中移除该元素，并处理相应的链表指针调整，以确保链表结构的完整性。
如果该桶中的链表只有一个元素，删除该元素后，该桶变为空。
如果链表中有多个元素，删除操作只影响指定元素，并将链表的前后元素连接起来。

bool Erase(const K& key)
{
    HashFunc hf;
    KeyofT kot;
    size_t hashi = hf(kot(key)) % _table.szie();
    Node* cur = _table[hashi];
    Node* prev = nullptr;
    while (cur)
    {
        if (kot(cur->_data) == key)
        {
            if (prev == nullptr)
            {
                _table[hashi] = cur->_next;
            }
            else
            {
                prev->_next = cur->_next;
            }

            delete cur;
            --_n;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

unordered查找操作

桶的选择
根据哈希值确定桶的位置（索引），通常通过哈希值对桶的数量取模来实现，即 bucket_index = hash_value % bucket_count。
定位到桶之后，开始在该桶的链表中查找目标元素。
遍历桶的链表
如果目标桶不为空，查找操作会遍历桶中的链表，比较每个元素的键与目标键 k 是否相同。
如果找到匹配的键，find() 方法返回指向该元素的迭代器。如果未找到，返回 end()。

iterator Find(const K& key)
{
    HashFunc hf;
    KeyofT kot;
    size_t hashi = hf(key) % _table.size();
    Node* cur = _table[hashi];
    while (cur)
    {
        if (kot(cur->_data) == key)
        {
            return iterator(cur,this);
        }
        cur = cur->_next;
    }
    return iterator(nullptr, this);
}

unordered迭代器

迭代器的结构

迭代器的构建需要_node的节点和哈希表的指针。
节点的指针是进行返回当前节点的值。

template<class K,class T,class Ptr,class Ref,class KeyofT, class HashFunc>
struct HashIterator
{
typedef HashNode<T> Node;
typedef HashIterator<K, T, Ptr, Ref ,KeyofT, HashFunc> Self;
typedef HashIterator<K, T, T*, T&, KeyofT, HashFunc> iterator;
    
    Node* _node;
const HashTable<K, T, KeyofT, HashFunc>* _pht;

};

迭代器的特点

在迭代器内需要写普通迭代器的拷贝构造（const迭代器的构造函数）
在迭代器实例化不同的类型，这个函数作用是不一样的。
这个的目的是为了解决set的insert返回值的需求，map返回pair<iterator，bool>，由于利用同于一个适配器，需要适应不同的容器。

HashIterator(const iterator& it)
:_node(it._node)
,_pht(it._pht)
{

迭代器自增

if判断当前桶的是否还存在剩余节点，存在返回下一个，不存在调整至下一个不为空的桶。

Self& operator++()
{
    if (_node->_next)
    {
        _node = _node->_next;
    }
    else
    {
        KeyofT kot;
        HashFunc hf;
        size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
        ++hashi;
        while (hashi < _pht->_table.size())
        {
            if (_pht->_table[hashi])
            {
                _node = _pht->_table[hashi];
                return *this;
            }
            else
            {
                ++hashi;
            }
        }
        _node = nullptr;
    }
    return *this;
}

迭代器其余结构

重载 * 、重载 -> 、重载== !=

Ref operator*()
{
    return _node->_data;
}

Ptr operator->()
{
    return &_node->_data;
}
bool operator!=(const Self& s)
{
    return _node != s._node;
}
bool operator==(const Self& s)
{
    return _node->_data == s._node;
}

迭代器的封装

begin（）返回第一个储存数据的节点
end（）返回空指针

iterator begin()
{ 
    for (int i = 0; i < _table.size(); i++)
    {
        Node* cur = _table[i];
        while (cur)
        {
            if (cur)

            {
                return iterator(cur, this);
            }
        }
    }
    return iterator(nullptr, this);
}
iterator end()
{
    return iterator(nullptr, this);
}

map和set的封装

map的set的仿函数

仿函数传过去是在实例化的时候为了取到不同的结构下的值

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

struct setofT
{
const K& operator()(const K& key)
{
return key;
}
};

map的set的插入

由于map储存键值对，返回pair，set为了适应结构返回也是pair
set的返回进行再次接受，哈希桶底层利用iterator，在这里返回const需要进行构造

pair<iterator,bool> insert(const pair<K, T>& kv)
{
    return _ht.insert(kv);
}

pair<const_iterator,bool> insert(const K& data)
{
    pair<typename HashTable<K, K, setofT>::const_iterator, bool> ret = _ht.insert(data);
    return make_pair(ret.first, ret.second);
}

map的operator[]

采用insert进行返回，存在key返回当前迭代器，不存在插入这个值。
整体这个函数放回该值的pair的second。

T& operator[](const K& key)
{
    pair<iterator, bool> ret = insert(make_pair(key, T()));
    return ret.first->second;
}

原文地址：https://blog.csdn.net/Cayyyy/article/details/142603406

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

上一篇：Comfyui 学习笔记1
下一篇：windows通过文件系统访问ftp传输中文乱码

PHP 中，将 JSON 数据与二进制数据之间进行相互转化主要涉及两个步骤：
要将 JSON 数据转换为二进制数据，首先需要将 JSON 数据解析成 PHP 数组或对象，然后使用 PHP 的。函数将二进制字符串转换为 PHP 数组或对象，然后将其编码为 JSON 数据。如果你只
阅读更多2024-09-28
JavaEE: 探索网络世界的核心-IP协议
13位分片偏移: 是分片相对于原始IP报文开始处的偏移.其实就是在表示当前分片在原报文中处在哪个位置.实际偏移的字节数是这个值 * 8 得到的.因此,除了最后一个报文之外,其他报文的长度必须是8的整数
阅读更多2024-09-28
数据库常见概念
PostgreSQL 支持联合索引和聚簇索引，联合索引可以加速多列条件的查询，而聚簇索引控制数据在磁盘上的排列。适当地使用这些索引可以提高查询性能。
阅读更多2024-09-28
BEV学习---LSS4-模型训练
LSS训练测试
阅读更多2024-09-28
SpringCloud第六章(服务保护CircuitBreaker) -2024
CircuitBreaker是断路器的意思，由于原来的SpringCoud的hystrix停更，所以springcloud社区推出了的新断路器，用来进行springcloud的服务降级、限流、熔断由于
阅读更多2024-09-28
ubuntu 开启root
【代码】ubuntu 开启root。
阅读更多2024-09-28
MySQL数据查询（基础）
SELECT语句用于从表中查询数据。可以选择特定的列，也可以选择所有列。：使用表示选择所有列。
阅读更多2024-09-28
区块链可投会议CCF C--FC 2025 截止10.8 附录用率
CCF C：2025：2023年 39 full and 2 short papers selected from 182 submissions.
阅读更多2024-09-28
第1章 C语言概述
4.打开项目后，右击"源文件"并选择"添加"的"新建项"6.在"hello_word"文件下编写代码并点击运行。1.打开
阅读更多2024-09-28
Git 与 GUI 工具
当我们对 Git 的提交、分支已经非常熟悉，可以熟练使用命令操作 Git 后，再使用 GUI 工具，就可以更高效。
阅读更多2024-09-28