当前位置: 首页 > article >正文

【C++】unordered_map(set)

前言

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

unordered系列的实现(基哈希桶)

哈希表的基本结构

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

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

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

哈希函数

  1. 在函数的内容的不确定的时候进行返回。
  2. 针对string字符串的直接进行特模板化。
  3. 针对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插入操作

  1. 哈希计算
    当你插入一个元素(比如在unordered_map中插入一个键值对),首先会调用哈希函数对键(key)进行哈希计算。这个哈希函数返回一个哈希值(通常是一个无符号整数类型,如std::size_t)。
    这个哈希值会被用来确定元素应该存储在哪个桶(bucket)中。桶的数量通常是哈希表当前容量的一个因子。

  2. 桶的选择
    哈希表根据哈希值和桶的数量来确定目标桶的位置。通常这是通过取模运算来完成的,即 hf(kot(data)) % _table.size()
    在这个位置上,哈希表要检查这个桶是否已经存在元素,如果存在,则进行冲突处理。

  3. 冲突处理
    如果目标桶已经有其他元素(即发生了哈希冲突),unordered_map unordered_set 通过 开链法(chaining) 进行处理。
    开链法意味着每个桶实际上包含一个链表或链表的类似结构。新元素将被添加到这个链表中。

  4. 元素存储
    如果目标桶为空,则直接将新元素存储在该桶中。
    如果目标桶不为空(发生冲突),则将元素追加到该桶的链表中。
    unordered_map 中,如果插入的键已经存在,则插入操作不会改变哈希表,而是更新该键对应的值。

  5. 负载因子与再散列(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删除操作

删除操作的底层流程

  1. 哈希计算
    对于基于键删除的操作(如 erase(const key_type& k)),首先会对给定的键 k 进行哈希计算,计算出哈希值。
    根据哈希值确定该键可能存储在哪个桶中。

  2. 查找元素
    哈希表在确定了桶的位置后,会在对应的桶(链表)中查找目标元素。
    如果找到匹配的元素,哈希表会进行删除操作;如果未找到,erase 返回 0,表示没有元素被删除。

  3. 删除元素
    删除元素时,需要从桶的链表中移除该元素,并处理相应的链表指针调整,以确保链表结构的完整性。
    如果该桶中的链表只有一个元素,删除该元素后,该桶变为空。
    如果链表中有多个元素,删除操作只影响指定元素,并将链表的前后元素连接起来。

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查找操作

  1. 桶的选择
    根据哈希值确定桶的位置(索引),通常通过哈希值对桶的数量取模来实现,即 bucket_index = hash_value % bucket_count。
    定位到桶之后,开始在该桶的链表中查找目标元素。
  2. 遍历桶的链表
    如果目标桶不为空,查找操作会遍历桶中的链表,比较每个元素的键与目标键 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;
}

http://www.kler.cn/a/327003.html

相关文章:

  • Android App 技能在DuerOS的调试方法
  • 新一代跟踪器StrongSORT: Make DeepSORT Great Again论文解析—让 DeepSORT 再次伟大
  • 你适合哪种tiktok广告账户类型?
  • 自研小程序-心情追忆
  • sql server 文件备份恢复
  • Docker使用复习(11.3)
  • 几种常见点云开源库——点云、网格数据结构转换
  • 麒麟桌面系统V10 SP1安装php的达梦数据库扩展
  • latex打出邮箱图标和可点击的orcidID
  • NXP(恩智浦)—MC33PF8200A0ES PMIC芯片详解
  • 【COSMO-SkyMed系列的4颗卫星主要用途】
  • Spring Boot技术:构建高效网上购物平台
  • 高效学习工作SMART原则
  • C++中set集合和Python中set集合的区别
  • 【Golang】关于Go语言数学计算、随机数生成模块--math
  • 微信小程序使用picker,数组怎么设置默认值
  • RabbitMQ MQ的可靠性及消费者的可靠性
  • 【Ubuntu】VMware中虚拟网卡与服务器网卡的绑定
  • XHTML学习
  • MacOS升级Ruby版本详解:步骤、挑战与解决方案
  • 【Linux:线程概念】
  • 【并发】ThreadLocal 为什么会内存泄露
  • golang小项目1-家庭收支记账系统
  • java计算机毕设课设—超级玛丽游戏(附源码、文章、相关截图、部署视频)
  • OJ在线评测系统 后端基础部分开发 完善CRUD相关接口
  • 【ARM 嵌入式 C 入门及渐进26 -- 内敛函数和宏定义的区别】