【C++】哈希(模拟实现unordered系列容器)

这篇具有很好参考价值的文章主要介绍了【C++】哈希(模拟实现unordered系列容器)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、哈希表的改造

【C++】哈希(模拟实现unordered系列容器),C++,哈希算法,c++,哈希表,unordered,模拟实现,容器

1、模板参数列表的改造

  • K:关键码类型
  • V:不同容器V的类型不同。如果是 unordered_map,V 代表一个键值对;如果是 unordered_set,V 为 K。
  • KeyOfValue:因为 V 的类型不同,通过 value 取 key 的方式就不同,通过T的类型来获取 key 值。
  • HF:哈希函数仿函数对象类型,哈希函数使用除留余数法,需要将不能取模的类型 Key 转换为可以取模的 size_t (整形数字)。
template<class K, class V, class KeyOfValue, class HF = DefHashF<T>>
class HashBucket;

2、增加迭代器操作

// 为了实现简单,在哈希桶的迭代器类中需要用到hashBucket本身,
template<class K, class V, class KeyOfValue, class HF>
class HashBucket;

// 注意:因为哈希桶在底层是单链表结构,所以哈希桶的迭代器不需要--操作
template <class K, class V, class KeyOfValue, class HF>
struct HBIterator
{
    // 类型重命名
    typedef HashBucket<K, V, KeyOfValue, HF> HashBucket; // 哈希表
    typedef HashBucketNode<V> Node;                      // 哈希表节点
    typedef HBIterator<K, V, KeyOfValue, HF> Self;       // 迭代器

    // 构造函数(迭代器由节点指针和哈希表指针来构造)
    HBIterator(Node* node = nullptr, HashBucket* pHt = nullptr);

    // 相关运算符重载
    // 1、让迭代器可以移动,前置++运算符的重载(单向迭代器,不支持--操作)
    Self& operator++() // 前置++,返回指向下一个节点的迭代器的引用
    {
        // 遍历当前桶的节点
        // 1.当前节点的下一个节点不为空
        if (_node->_next)
        {
            _node = _node->_next; // _node指向下一个节点
        }
        // 2.当前节点的下一个节点为空,说明走到当前哈希桶的桶底了
        else
        {
            // 先通过哈希函数计算出当前桶的位置(先取出key再进行取模)
            size_t index = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();

            // 从下一个位置开始,遍历哈希表,找到下一个不为空的哈希桶
            index++;
            while (index < _ht->_tables.size())
            {
                if (_ht->_tables[index]) // 找到下一个不为空的桶了
                {
                    _node = _ht->_tables[index]; // _node指向该桶的第一个节点
                    return *this;
                }
                index++;
            }
            // 后面没有不为空的桶了
            _node = nullptr; // _node指向空
        }
        return *this; // 返回下一个节点的迭代器的引用
    }

    Self operator++(int);

    // 2、让迭代器具有类似指针的行为
    V& operator*() // *解引用操作符
    {
        return _node->_data; // 返回迭代器指向节点中数据的引用
    }

    V* operator->() // ->成员访问(指针)操作符
    {
        return &_node->_data; // 返回迭代器指向节点中数据的地址
    }

    // 让迭代器可以比较
    bool operator==(const Iter& it) const
    {
        return _node == it._node; // 比较两个迭代器中的节点指针,看是否指向同一节点
    }

    bool operator!=(const Iter& it) const
    {
        return _node != it._node; // 比较两个迭代器中的节点指针,看是否指向同一节点
    }

    Node _node;     // 当前迭代器关联的节点
    HashBucket* _pHt; // 哈希桶--主要是为了找下一个空桶时候方便
};

注意:哈希表迭代器封装的是节点指针哈希表指针,因为要在哈希表中找下一个桶,所以要用到哈希表指针。 

 【思路】前置++运算符的重载(单向迭代器,不支持 -- 操作)

  • 如果当前桶的节点没有遍历完,则让节点指针 _node 指向下一个节点。
  • 如果当前桶的节点遍历完了,则让节点指针 _node 指向下一个不为空的桶的第一个节点。

【C++】哈希(模拟实现unordered系列容器),C++,哈希算法,c++,哈希表,unordered,模拟实现,容器


3、定义哈希表的结构

一个数组,数组中存储着各个链表头结点的地址。

注意这里有一个私有成员访问的问题,我们在哈希表迭代器中封装了一个哈希表指针,当一个桶遍历完成时,用来在哈希表中找下一个桶,但哈希表 _tables 是私有成员,无法访问,所以需要将迭代器类模板声明为友元。

K:键值 key 的类型。
T:数据的类型,如果是 unordered_set,则为 key,如果是 unordered_map,则为 pair<const key, V>。
Hash:仿函数类,将不能取模的类型转换成可以取模的 size_t 类型。
KeyOfT:仿函数类,通过 T 的类型来获取 key 值。

// 定义哈希表结构
template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
    typedef HashNode<T> Node; // 哈希表节点

    // 声明迭代器类模板为友元,因为迭代器中的哈希表指针要访问哈希表的私有成员_tables
    // 写法一:
    template<class K, class T, class Hash, class KeyOfT>
    friend struct HTIterator;
    // 写法二:
    friend struct HTIterator<K, T, Hash, KeyOfT>;

public:
    // 迭代器
    typedef HTIterator<K, T, Hash, KeyOfT> iterator; // iterators内嵌类型
    iterator begin(); // 返回指向第一个节点的迭代器
    iterator end();   // 返回指向nullptr的迭代器
    
    // 构造、拷贝构造、赋值重载、析构函数
    HashTable() = default; // 默认生成,因为实现了拷贝构造函数,就不会再生成构造函数了
    HashTable(const HashTable& ht);
    HashTable& operator=(HashTable ht);
    ~HashTable();
    
    Node* Find(const K& key);                   // 查找节点
    pair<iterator, bool> Insert(const T& data); // 插入节点
    bool Erase(const K& key);                   // 删除节点
    
private:
    vector<Node*> _tables;  // 哈希表(存储着各个链表头结点的地址)
    size_t _n = 0;          // 哈希表中有效节点的个数(缺省为0)
};

① begin() 和 end() 的实现
// 返回指向第一个节点的迭代器
iterator begin()
{
    // 遍历哈希表,找到第一个不为空的哈希桶
    for (size_t i = 0; i < _tables.size(); i++)
    {
        if (_tables[i])
        {
            // 注意:迭代器由节点指针和哈希表指针构造,而成员函数的this指针就是指向哈希表的
            return iterator(_tables[i], this); // 返回迭代器
        }
    }
    return end();
}

// 返回指向nullptr的迭代器
iterator end()
{
    // 注意:迭代器由节点指针和哈希表指针构造,而成员函数的this指针就是指向哈希表的
    return iterator(nullptr, this);
}

注意:this 指针指向当前调用 begin() 成员函数的哈希表对象的。


② 默认成员函数的实现
a. 构造函数的实现
HashTable() = default; // 默认生成,因为实现了拷贝构造函数,就不会再生成构造函数了

b. 拷贝构造函数的实现(深拷贝)

必须是深拷贝,浅拷贝出来会导致两个哈希表中存放的是同一批哈希桶的地址

  • 将新哈希表大小调整为 ht._tables.size()
  • 遍历 ht._tables 的所有哈希桶,将桶里的节点 一一 拷贝到新哈希表对应位置上。
  • 更改新哈希表中的有效节点个数为 ht._n
// 拷贝构造
HashTable(const HashTable& ht)
{
    // 深拷贝,用已存在的对象ht去拷贝构造一个新对象
    // 将新哈希表大小调整为ht._tables.size()
    _tables.resize(ht._tables.size());

    // 遍历ht._tables的所有哈希桶,将桶里的节点一一拷贝到新哈希表对应位置上
    for (size_t i = 0; i < ht._tables.size(); i++)
    {
        Node* cur = ht._tables[i]; // 记录当前桶的位置
        while (cur) // 当前桶不为空,开始拷贝桶中的节点
        {
            Node* copy = new Node(cur->_data); // 申请一个新节点

            copy->_next = _tables[i]; // 将新节点插入到新哈希表中
            _tables[i] = copy;

            cur = cur->_next; // 继续遍历下一个节点
        }
    }
    // 更改新哈希表中的有效节点个数
    _n = ht._n;
}

c. 赋值运算符重载函数的实现(现代写法)

通过参数间接调用拷贝构造函数,然后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可,这样当前哈希表就拿到了自己想要的内容,当函数调用结束后,拷贝构造出来的哈希表 ht 出了作用域会被自动析构。

// 赋值运算符重载
HashTable& operator=(HashTable ht)
{
    // 传参时,调用拷贝构造函数,拷贝构造了一个哈希表ht
    // 将拷贝构造出来的哈希表ht和当前哈希表的两个成员变量分别进行交换
    _tables.swap(ht._tables);
    _n = ht._n;

    return *this; // 返回当前哈希表
}

d. 析构函数的实现 
// 析构函数
~HashTable()
{
    // 遍历哈希表,找到不为空的哈希桶
    for (size_t i = 0; i < _tables.size(); i++)
    {
        Node* cur = _tables[i]; // 记录当前桶的位置
        
        while (cur) // 当前桶不为空,开始释放桶中的所有节点
        {
            Node* next = cur->_next; // 记录cur指向节点的下一个节点

            delete cur; // 释放节点

            cur = next; // 继续去释放下一个节点
        }
        
        _tables[i] = nullptr; // 当前桶释放完毕,置空
    }

    _n = 0; // 有效节点个数置0
}

4、实现哈希表的相关接口

① 查找节点

查找节点接口中,需要获取不同类型元素关键码 key,因为元素间的比较是通过 key 值来比较的,以及通过元素关键码 key 取模计算出哈希位置。

所以需要借助两个仿函数类:

  • 仿函数类 KeyOfT,获取不同类型的 data 中的关键码 key 值(如果 data 是 key 就取 key,如果是 pair 就取 first)
  • 仿函数类 Hash,有些元素关键码 key 的类型不能直接取模,需要将其转换成可以取模的 size_t 类型。
Node* Find(const K& key)
{
    // 1、先检查哈希表是否为空
    if (_tables.size() == 0)
    {
        return nullptr;
    }

    // 2、再通过哈希函数计算出该元素映射的哈希桶的位置
    size_t index = Hash()(key) % _tables.size();

    // 3、遍历该哈希桶,查找节点
    Node* cur = _tables[index]; // cur指向该哈希桶
    while (cur)                 // 遍历该哈希桶的所有节点
    {
        if (key == KeyOfT()(cur->_data)) // 取key出来比较
        {
            return cur; // 找到了,返回节点地址
        }

        // 继续往后遍历
        cur = cur->_next;
    }

    // 4、没找到,返回空
    return nullptr;
}

② 插入节点

插入节点接口中,需要获取不同类型元素关键码 key,因为元素间的比较是通过 key 值来比较的,以及通过元素关键码 key 取模计算出哈希位置。

所以需要借助两个仿函数类:

  • 仿函数类 KeyOfT,获取不同类型的 data 中的关键码 key 值(如果 data 是 key 就取 key,如果是 pair 就取 first)
  • 仿函数类 Hash,有些元素关键码 key 的类型不能直接取模,需要将其转换成可以取模的 size_t 类型。

函数的返回值为 pair<iterator, bool> 类型对象:

  • 目的是为了在 unordered_set 和 unordered_map 中模拟实现 operator[] 运算符重载函数。

插入元素接口功能:插入元素前,会通过该元素的关键码 key 检查该元素是否已在哈希表中(不允许冗余):

  • 如果在,返回:pair<指向该元素的迭代器, false>。
  • 如果不在,先插入节点,再返回:pair<指向该元素的迭代器, true>。

T:数据的类型,如果是 unordered_set,则为 key,如果是 unordered_map,则为 pair<const key, V> 。

// 插入节点
pair<iterator, bool> Insert(const T& data)
{
    // 1、先检查哈希表是否需要扩容:表为空或者负载因子超过1
    if (_n == _tables.size())
    {
        // 计算新容量(按2倍扩)
        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]; // cur当前指向的哈希桶

            // 哈希桶不为空,开始转移哈希桶中的节点
            while (cur != nullptr)
            {
                // 保存cur指向节点的下一个节点
                Node* next = cur->_next;

                // 重新计算cur指向的旧表节点,映射到新表中的位置
                size_t index = Hash()(KeyOfT()(cur->_data)) % newSize; // 取key出来取模

                // 把cur指向的旧表节点,转移到新表中
                cur->_next = newTables[index];
                newTables[index] = cur;

                // 继续转移下一个旧表节点
                cur = next;
            }
            // 节点转移完毕,把当前哈希桶置空
            _tables[i] = nullptr;
        }
        // 旧表所有节点全部转移到新表中了,交换新表与旧表
        _tables.swap(newTables);
    }

    // 2、再通过哈希函数计算出待插入元素映射的哈希桶的位置
    size_t index = Hash()(KeyOfT()(data)) % _tables.size(); // 取key出来取模

    // 3、插入节点到该位置的哈希桶中
    // 先检查哈希桶中是否存在重复节点(因为不允许数据冗余)
    Node* cur = _tables[index]; // cur指向哈希桶的第一个节点
    while (cur)                 
    {
        // 存在重复节点,插入失败
        if (KeyOfT()(data) == KeyOfT()(cur->_data)) // 取key出来比较
        {
            // 构造pair<cur指向节点的迭代器, false>,进行返回
            return make_pair(iterator(cur, this), false);
        }
        cur = cur->_next;
    }

    // 开始头插
    Node* newNode = new Node(data);  // 申请新节点
    newNode->_next = _tables[index]; // 头插
    _tables[index] = newNode;
    _n++;                            // 有效节点个数+1

    // 插入成功
    // 构造pair<cur指向节点的迭代器, false>,进行返回
    return make_pair(iterator(newNode, this), true);
}

③ 删除节点

删除节点接口中,需要获取不同类型元素关键码 key,因为元素间的比较是通过 key 值来比较的,以及通过元素关键码 key 取模计算出哈希位置。

所以需要借助两个仿函数类:

  • 仿函数类 KeyOfT,获取不同类型的 data 中的关键码 key 值(如果 data 是 key 就取 key,如果是 pair 就取 first)。
  • 仿函数类 Hash,有些元素关键码 key 的类型不能直接取模,需要将其转换成可以取模的 size_t 类型。
bool Erase(const K& key)
{
    // 1、先判断哈希表是否为空
    if (_tables.size() == 0)
    {
        return false; // 表为空,删除失败
    }

    // 2、通过哈希函数计算出待删除节点所映射哈希桶的位置
    size_t index = Hash()(key) % _tables.size();

    // 3、遍历该哈希桶,查找待删除节点,以及它的前驱节点
    Node* cur = _tables[index];
    Node* prev = nullptr;
    while (cur)
    {
        // 找到该节点了
        if (key == KeyOfT()(cur->_data)) // 取key出来比较
        {
            if (cur == _tables[index]) // cur是头节点,进行头删
            {
                _tables[index] = cur->_next;
            }
            else // cur不是头节点
            {
                prev->_next = cur->_next;
            }

            delete cur;    // 删除节点
            cur = nullptr;
            _n--;          // 有效节点个数-1

            return true;   // 删除成功,返回true
        }
        // 继续往后遍历
        prev = cur;
        cur = cur->_next;
    }

    // 没有找到该节点,返回false
    return false;
}

5、针对除留余数法的取模问题

实现哈希表,计算元素关键码对应哈希位置的哈希函数采用的是除留余数法,需要传仿函数将不能取模的类型转换成可以取模的 size_t 类型。

这里给出针对普通类型取模和 string 类型取模的仿函数,放到全局域中,方便模拟实现 unordered_set 和 unordered_map 时使用。

// 仿函数(解决哈希函数采用除留余数法时,将不能取模的类型转换成可以取模的size_t类型)
// 默认仿函数类
template<class K>
struct HashFunc
{
    // 针对size_t类型和能够隐式类型转换成size_t的类型
    size_t operator()(const K& key)
    {
        return key;
    }
};

// 特化
template<>
struct HashFunc<string>
{
    // 把string类型转换成可以取模的size_t类型
    size_t operator()(const string& key)
    {
        size_t hash_key = 0;
        for (size_t i = 0; i < key.size(); i++)
        {
            hash_key *= 131;
            hash_key += key[i];
        }
        return hash_key;
    }
};

二、unordered_set 的模拟实现

unordered_set 在实现时,只需将 hashbucket 中的接口重新封装即可。

定义 unordered_set 的结构:

  • K:键值 key 的类型。
  • Hash:仿函数类,将不能取模的类型转换成可以取模的 size_t 类型。
namespace winter
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		// 仿函数类,获取key对象中的key
		struct KeyOfSet
		{
			const K& operator()(const K& key) const
			{
				return key;
			}
		};
        
	public:
		// 这里是要取HashTable<...>类模板里面定义的内嵌类型iterator,要注意:
		// 编译到这里的时候,类模板HashTable<K, K, Hash, KeyOfSet>可能还没有实例化成具体的类
		// 那么编译器就不认识这个类模板,更别说去它里面找iterator了
		// 所以要加typename,告诉编译器这是个类型,等它实例化了再去它里面找iterator
		typedef typename hash_bucket::HashTable<K, K, Hash, KeyOfSet>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}

		// 插入元素
		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private:
        // 封装一张哈希表,因为要实现unordered_set,所以要传
        // 键值K、键值K、针对除留余数法取模问题的Hash仿函数,提取Key值的KeyOfSet仿函数
		hash_bucket::HashTable<K, K, Hash, KeyOfSet> _ht;
	};
}

三、unordered_map 的模拟实现

unordered_map 在实现时,只需将 hashbucket 中的接口重新封装即可。

定义 unordered_map 的结构:

  • K:键值 key 的类型。
  • V:unordered_map 存储的数据 d 类型,pair<const key, V>。
  • Hash:仿函数类,将不能取模的类型转换成可以取模的 size_t 类型。

unordered_map 中存储的是 pair<K, V> 的键值对,K 为 key 的类型,V 为 value 的类型,HF 为哈希函数类型。文章来源地址https://www.toymoban.com/news/detail-755377.html

template<class K, class V, class HF = DefHashF<K>>
class unordered_map
{
    typedef pair<K, V> ValueType;
    typedef HashBucket<K, ValueType, KeyOfValue, HF> HT;
    // 通过key获取value的操作
    struct KeyOfValue
    {
        const K& operator()(const ValueType& data)
        {
            return data.first;
        }
    };
public:
    typename typedef HT::Iterator iterator;
public:
    unordered_map(): _ht()
    {}

    iterator begin(){ return _ht.Begin();}
    iterator end(){ return _ht.End();}

    // capacity
    size_t size()const
    {
        return _ht.Size();
    }
    bool empty()const
    {
        return _ht.Empty();
    }

    // Acess
    V& operator[](const K& key)
    {
        return (*(_ht.InsertUnique(ValueType(key, V())).first)).second;
    }
    const V& operator[](const K& key)const;

    // lookup
    iterator find(const K& key)
    {
        return _ht.Find(key);
    }
    size_t count(const K& key)
    {
        return _ht.Count(key);
    }

    // modify
    pair<iterator, bool> insert(const ValueType& valye)
    {
        return _ht.Insert(valye);
    }
    iterator erase(iterator position)
    {
        return _ht.Erase(position);
    }

    // bucket
    size_t bucket_count()
    {
        return _ht.BucketCount();
    }
    size_t bucket_size(const K& key)
    {
        return _ht.BucketSize(key);
    }
private:
    HT _ht;
};

到了这里,关于【C++】哈希(模拟实现unordered系列容器)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 哈希——unordered系列关联式容器

      目录 unordered系列关联式容器 概念 unordered_map 无序+去重 operator[] unordered_set 无序+去重 OJ练习题 重复n次的元素 两个数组的交集  两个数的交集二  底层结构 概念  哈希冲突 闭散列 结点的定义 扩容 字符串取模 插入 查找 删除 闭散列完整代码  开散列 结点定义 释放桶(析构

    2023年04月17日
    浏览(34)
  • 【C++】哈希表封装unordered系列

      文章目录 前言 一、哈希表的封装 总结 在看本篇文章前大家尽量拿出上一篇文章的代码跟着一步步实现,否则很容易引出大量模板错误而无法解决。 一、哈希表的封装 首先我们要解决映射的问题,我们目前的代码只能映射整形,那么如何支撑浮点数等的映射呢?只需要多

    2024年02月07日
    浏览(40)
  • 【C++】哈希和unordered系列封装

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( l o g 2 N log_2 N l o g 2 ​ N ),搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方

    2024年02月02日
    浏览(34)
  • 【C++】unordered系列容器

    unordered容器是C++标准库中提供的一组无序关联式容器,用于存储和管理无序的数据集合。这些容器的特点是快速的查找、插入和删除操作,其内部实现通常基于哈希表(hash table)。 C++标准库提供了四种unordered容器: unordered_set:无序唯一元素集合,存储一组唯一的元素,不允

    2024年02月16日
    浏览(42)
  • 由[哈希/散列]模拟实现[unordered_map/unordered_set] (手撕迭代器)

    以下两篇文章均为笔者的呕心沥血 想要搞懂本篇文章的uu请自行查阅 哈希/散列的细节实现 哈希/散列–哈希表[思想到结构][==修订版==] 手撕迭代器的细节处理 模拟实现map/set[改编红黑树实现map/set容器底层]

    2024年02月07日
    浏览(45)
  • 【C++】unordered 系列关联式容器

    在 C++ 98 中,STL 提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是:进行很少的比较次数就能将元素找到,因此在 C++ 11 中,STL 又

    2024年04月11日
    浏览(34)
  • 【C++】哈希表封装实现 unordered_map 和 unordered_set

    在 C++98 中,STL 提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 O(logN),即最差情况下只需要比较红黑树的高度次;但是当树中的节点非常多时,其查询效率也不够极致。 最好的查询是,不进行比较或只进行常数次比较就能够将元素找到,因此在 C++11 中,

    2023年04月16日
    浏览(49)
  • 【C++】开散列哈希表封装实现unordered_map和unordered_set

    在未达成目的之前,一切具有诱惑力的事物都显得那么不堪一击 1. 在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。 最好的查询是

    2023年04月09日
    浏览(84)
  • [C++]哈希表实现,unordered_map\set封装

    目录 ​​​​​​​ 前言: 1 哈希 1.1 为什么有哈希 1.2 哈希结构 1.3 哈希冲突  2 闭散列 2.1 闭散列结点结构和位置状态表示 2.2 哈希类结构 2.3 插入 2.4 查找 2.5 删除 3 开散列 3.1 哈希表结点结构 3.2 哈希表结构 3.3 插入 3.4 查找、删除 3.5 迭代器实现 4 map和set的封装 4.1 map的封

    2024年02月08日
    浏览(49)
  • C++进阶--使用哈希表实现unordered_map和unordered_set的原理与实例

    本文将介绍如何使用哈希表来实现C++ STL库中的unordered_map和unordered_set容器。我们将会解释哈希表的基本原理,并给出具体的代码示例,帮助读者更好地理解和应用哈希表。 哈希原理讲解–链接入口 set和map的实现的文章,与unordered_map实现类似 unordered_set是一种集合存储的容器

    2024年04月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包