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

C++实现unordered_map和unordered_set

article 2024/11/13 12:20:28

1. 结构示意

2. 模版参数控制

我们知道，unordered_set和unordered_map与set和map是一样的，前者不是真正的键值对，它的value值和key值相同；后者是真正的键值对。STL非常注重代码的复用，它们在底层使用了同一棵红黑树模板实现，这也是此文要用同一个哈希表实现unordered_set和unordered_map的原因。

如果各自拥有一个哈希表，set和unordered_set只要一个key值即可。

2.1 容器模版参数 

 unordered_set

template<class K>
class unordered_set
{
public:
    // ..
private:
    HashTable<K, K> _ht;
};

unordered_map

template<class K, class V>
class unordered_map
{
public:
    //...
private:
    HashTable<K, pair<K, V>> _ht;
};

2.2 结点类定义

我们将设计一个底层哈希表类，通过模板参数 T 来区分 unordered_set 和 unordered_map。

由于原先实现哈希表时默认是以<key,value>作为键值对的，而哈希表在底层是不知道上层是unordered_set还是unordered_map，所以为了区分两者键值对的第二个模板参数，将哈希表中的第二个模板参数从V改成T：

  • 当上层是unordered_set时，T和K相同；
  • 当上层是unordered_map时，T就是value。

同时，原先的键值对也要改成模板参数T，由于这个T可能是key，也有可能是<key,value>键值对，所以将原来结点类中的_kv（键值对）改成_data，以保存数据。

template<class T>
struct HashNode
{
    T _data;                    // 保存数据
    HashNode<T>* _next;         // 后继指针
    HashNode(const T& data)     // 结点构造函数
        :_data(data)
        , _next(nullptr)
    {}
};

2.3 仿函数获取键值

上面的操作将unordered_set和unordered_map的键值对是用一个T类型的_data保存的，由于哈希函数要根据键值key计算，所以要取出_data中的key值。在这里可以使用一个仿函数获取，仿函数其实就是一个结构体中重载的operator()。

unordered_set 

template<class K>
class unordered_set
{
    struct SetKeyOfT
    {
        const K& operator()(const K& key)
        {
            return key;
        }
    };
public:
    // ...
private:
    HashTable<K, K, SetKeyOfT> _ht;
};

 unordered_map

template<class K, class V>
class unordered_map
{
    struct MapKeyOfT
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };
public:
    // ...
private:
    HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

因此，在哈希表中的参数列表要新增一个仿函数：

template<class K, class T, class KeyOfT>
class HashTable
{
    // ... 
};

3. 哈希函数

在使用map和set时，大多数情况key值都是字符串类型，unordered_set和unordered_map也是一样的，但是string虽然是常用的类型，但是它无法直接取模，这也是哈希常见的问题。

提出的BKDRHash 算法，是一个高效且实用的哈希函数，之前的文章中提到过，实现起来是：

数字类型 

// 哈希函数
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return static_cast<size_t>(key);
    }
};

字符串类型 （BKDRHash算法）

// 模板的特化
template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t value = 0;
        for (auto ch : s)
        {
            value = value * 131 + ch;
        }
        return value;
    }
};

 所以哈希表的模板参数还要增加一个：                                         

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
    // ...
};

4. 哈希表默认成员

4.1 默认构造函数

这里的 _table 是一个 std::vector，在构造函数中使用 resize(size, nullptr) 来初始化，确保 _table 的大小为 size，并且每个桶初始化为 nullptr。

// 构造函数，初始化桶大小为 size
HashTable(size_t size = 10) {
    _table.resize(size, nullptr);
}

4.2 拷贝构造函数

深拷贝实现拷贝构造函数，新哈希表和旧哈希表中的结点的地址都是相同的。

步骤：

  1. 将新哈希表的大小risize到旧哈希表大小；
  2. 将旧哈希表的每个桶的结点全部拷贝到新的哈希表中；
  3. 更新新哈希表的_size。
//拷贝构造函数
HashTable(const HashTable& ht)
{
    _table.resize(ht._table.size());
    for (size_t i = 0; i < ht._table.size(); i++)
    {
        if (ht._table[i])
        {
            Node* cur = ht._table[i];
            while (cur)
            {
                Node* copy = new Node(cur->_data);
                copy->_next = _table[i];
                _table[i] = copy;
                cur = cur->_next;
            }
        }
    }
    _size = ht._n;
}

4.3 赋值运算符重载

赋值运算符重载函数的本质就是拷贝构造函数：

在参数部分构造一个哈希表，然后将新旧哈希表的地址和有效数据_size交换，为了=能连续赋值，最后返回当前对象的this指针。这里巧妙使用了参数部分构造新对象和函数结束时调用对应的析构函数。

//赋值运算符重载函数
HashTable& operator=(HashTable ht)  // 这里调用了构造函数
{
    _table.swap(ht._table);
    swap(_size, ht._size); 	// 交换数据
    return *this;
} // 调用析构函数，将ht析构

4.4 析构函数

由于每个哈希桶中的结点都是new出来的，所以要遍历哈希表，将每个哈希桶中的所有结点delete。

// 析构函数
~HashTable()
{
    for (size_t i = 0; i < _table.size(); i++)
    {
        Node* cur = _table[i];
        while (cur)
        {
            Node* next = cur->_next;
            free(cur);
            cur = next;
        }
        _table[i] = nullptr;
    }
}

接下来是对数据的插入，查找，删除的操作，显然直接对 Node* 的++或--操作不能正常遍历到数据，所以就需要对结点指针的迭代器封装。

5. 正向迭代器

STL中实现了双向迭代器，但这里只实现了正向迭代器。

在哈希表的情况下，实际上不支持有效的双向迭代器操作，因为哈希表的设计通常不支持向前遍历。

5.1 定义迭代器结构体

由于不同的运算符重载函数的返回值可能不同，类型有引用、指针和迭代器本身，所以在迭代器内部typedef一下。

// 前置声明
template<class K, class T, class KeyOfT, class Hash>  // __HTIterator类需要知道HashTable类的存在，以便使用它作为成员类型HT
class HashTable;
// 正向迭代器
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __HTIterator
{
    typedef HashNode<T> Node;                         // 哈希结点类型
    typedef HashTable<K, T, KeyOfT, Hash> HT;         // 哈希表类型
    typedef __HTIterator<K, T, KeyOfT, Hash> Self;    // 正向迭代器类型

    Node* _node;            // 结点指针
    HT* _pht;               // 哈希表的地址

    // 构造函数
    __HTIterator(Node* node, HT* pht)
        : _node(node)
        , _pht(pht)
    {}

    // 解引用运算符重载
    T& operator*()
    {
        return _node->_data;
    }

    // 箭头运算符重载
    T* operator->()
    {
        return &_node->_data;
    }

    // 比较运算符重载
    bool operator!=(const Self& s) const
    {
        return _node != s._node;
    }

    // ==运算符重载
    bool operator==(const Self& s) const
    {
        return _node == s._node;
    }

    // 前置++
    Self& operator++()
    {
        if (_node->_next)                   // 当前结点不是哈希桶的最后一个结点
        {
            _node = _node->_next;           // 迭代
        }
        else                                // 当前结点是哈希桶的最后一个结点
        {
            KeyOfT kot;
            Hash hash;
            size_t index = hash(kot(_node->_data)) % _pht->_table.size(); // 得到当前哈希桶的下标
            index++;                                                      // 下标+1
            while (index < _pht->_table.size())                           // 遍历哈希表中所有哈希桶
            {
                if (_pht->_table[index])                                  // 当前哈希桶不为空
                {
                    _node = _pht->_table[index];
                    return *this;                                         // 更新结点指针并返回
                }
                index++;                                                  // 当前哈希表为空，往后找
            }
            _node = nullptr;                                              // 上一个是空桶
        }
        return *this;
    }
};

6. 操作函数

6.1 插入

如果元素已存在，返回迭代器指向该元素和 false。否则，插入新元素并返回指向该元素的迭代器和 true。

pair<typename HashTable::iterator, bool> Insert(const T& data)
{
    KeyOfT kot;
    Hash hash;
    size_t index = hash(kot(data)) % _table.size(); // 计算哈希值并获取桶索引

    Node* current = _table[index];
    while (current)
    {
        if (kot(current->_data) == kot(data)) // 检查元素是否已存在
        {
            return { iterator(current, this), false }; // 元素已存在
        }
        current = current->_next;
    }

    // 元素不存在，插入新元素
    Node* newNode = new Node(data);
    newNode->_next = _table[index];
    _table[index] = newNode;
    ++_size;

    return { iterator(newNode, this), true };
}

6.2 查找

若找到元素，返回指向该元素的迭代器；若未找到元素，返回 end() 迭代器。

typename HashTable::iterator Find(const K& key)
{
    Hash hash;
    KeyOfT kot;
    size_t index = hash(key) % _table.size(); // 计算哈希值并获取桶索引

    Node* current = _table[index];
    while (current)
    {
        if (kot(current->_data) == key) // 找到元素
        {
            return iterator(current, this);
        }
        current = current->_next;
    }

    return end(); // 未找到元素
}

6.3 删除  

若元素存在，则删除该元素；若元素不存在，则不做任何操作。 

void Erase(const K& key)
{
    Hash hash;
    KeyOfT kot;
    size_t index = hash(key) % _table.size(); // 计算哈希值并获取桶索引

    Node* current = _table[index];
    Node* prev = nullptr;
    while (current)
    {
        if (kot(current->_data) == key) // 找到要删除的元素
        {
            if (prev)
            {
                prev->_next = current->_next;
            }
            else
            {
                _table[index] = current->_next;
            }
            delete current;
            --_size;
            return;
        }
        prev = current;
        current = current->_next;
    }
}

6. 实现unordered_set和unordered_map

unordered_set 实现

template<class K, class Hash = HashFunc<K>>
class unordered_set
{
    struct SetKeyOfT
    {
        const K& operator()(const K& key)
        {
            return key;
        }
    };
public:
    typedef typename HashTable<K, K, SetKeyOfT>::iterator iterator; // 定义迭代器    

    iterator begin()
    {
        return _ht.begin();
    }

    iterator end()
    {
        return _ht.end();
    }
    // 插入函数
    pair<iterator, bool> insert(const K& key)
    {
        return _ht.Insert(key);
    }
    // 删除函数
    void erase(const K& key)
    {
        _ht.Erase(key);
    }
    // 查找函数
    iterator find(const K& key)
    {
        return _ht.Find(key);
    }

private:
    HashTable<K, K, SetKeyOfT> _ht;
};

unordered_map 实现

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
    struct MapKeyOfT
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };
public:
    typedef typename HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;

    iterator begin()
    {
        return _ht.begin();
    }

    iterator end()
    {
        return _ht.end();
    }
    // 插入函数 
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
        return _ht.Insert(kv);
    }
    // 删除函数
    void erase(const K& key)
    {
        _ht.Erase(key);
    }
    // 查找函数
    iterator find(const K& key)
    {
        return _ht.Find(key);
    }
    // []运算符重载
    V& operator[](const K& key)
    {
        pair<iterator, bool> ret = insert(make_pair(key, V()));
        iterator it = ret.first;
        return it->second;
    }

private:
    HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

用一个哈希表来实现 unordered_set 和 unordered_map 到此结束🌹


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

相关文章：

  • git之 revert和rebase
  • 【深度学习】LSTM、BiLSTM详解
  • STM32学习笔记------GPIO介绍
  • nvm 安装指定node版本时--list 显示为空
  • 壹连科技IPO闯关成功！连接器行业上市企业+1
  • Ubuntu 的 ROS2 操作系统turtlebot3环境搭建
  • 【Kafka】分区与复制机制：解锁高性能与容错的密钥
  • 交换技术是一种在计算机网络和通信系统中广泛应用的关键技术，它主要通过交换设备（如交换机、路由器等）实现数据的转发和传输
  • VBA V3高级视频行为分析系统（含源码）
  • 数据库系统 第52节 数据库日志和恢复
  • 用Matlab求解绘制2D散点（x y）数据的最小外接圆、沿轴外接矩形
  • 代码随想录算法训练营第48天 | LeetCode739.每日温度、 LeetCode496.下一个更大元素I、 LeetCode503.下一个更大元素II
  • Linux 之 RPM [Red - Hat Package Manager]【包管理】
  • JavaScript 事件处理
  • Gateway Timeout504: 网关超时的完美解决方法
  • 【鸿蒙OH-v5.0源码分析之 Linux Kernel 部分】005 - Kernel 入口 C 函数 start_kernel() 源码分析
  • 【Webpack--007】处理其他资源--视频音频
  • PostgreSQL - tutorial
  • 我的标志：奇特的头像
  • ARM驱动学习之21_字符驱动
  • Gitlab 中几种不同的认证机制（Access Tokens，SSH Keys，Deploy Tokens，Deploy Keys）
  • Linux线程同步：深度解析条件变量接口
  • Deep Learning-Based Object Pose Estimation:A Comprehensive Survey
  • VUE使用echarts编写甘特图（组件）
  • AI写作助力自媒体，传统模式将被颠覆
  • 网络安全学习（二）初识kali