c++实现HashMap

本文涉及的产品
函数计算FC,每月15万CU 3个月
简介: 这篇文章提供了一个用C++实现的简单HashMap类的示例代码,包括构造函数、put、get、remove和size方法,以及私有的hash函数,用于计算键的哈希值。该HashMap使用链地址法解决哈希冲突,适用于学习和理解哈希表的基本概念。

概述: 无聊的时候学一下。

完整代码:

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

template<typename K, typename V>
class HashMap {
public:
    HashMap(size_t capacity = 10) : capacity_(capacity), size_(0) {
        table_.resize(capacity_);
    }

    void put(const K& key, const V& value) {
        size_t index = hash(key) % capacity_;
        for (auto& pair : table_[index]) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        table_[index].emplace_back(key, value);
        ++size_;
    }

    V get(const K& key) {
        size_t index = hash(key) % capacity_;
        for (auto& pair : table_[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        throw std::runtime_error("Key not found");
    }

    bool remove(const K& key) {
        size_t index = hash(key) % capacity_;
        for (auto it = table_[index].begin(); it != table_[index].end(); ++it) {
            if (it->first == key) {
                table_[index].erase(it);
                --size_;
                return true;
            }
        }
        return false;
    }

    size_t size() const {
        return size_;
    }

private:
    size_t hash(const K& key) const {
        return std::hash<K>{}(key);
    }

    size_t capacity_;
    size_t size_;
    std::vector<std::list<std::pair<K, V>>> table_;
};

int main() {
    HashMap<std::string, int> map;
    map.put("one", 1);
    map.put("two", 2);
    map.put("three", 3);

    std::cout << "Size: " << map.size() << std::endl;
    std::cout << "Value of 'one': " << map.get("one") << std::endl;
    std::cout << "Value of 'two': " << map.get("two") << std::endl;
    std::cout << "Value of 'three': " << map.get("three") << std::endl;

    map.remove("two");
    std::cout << "Size after removing 'two': " << map.size() << std::endl;

    return 0;
}

这段代码使用单独的链实现了一个简单的哈希映射来解决冲突。让我们来分析一下主要组成部分:

template<typename K, typename V>是C++中模板的声明方式,表示这是一个模板函数或模板类。其中,KV是类型参数,可以在实例化模板时替换为具体的类型。

HashMap map; 就是将k化成string,V化成int类型

HashMap类:这是一个表示散列映射的模板化类。它有put(key, value)方法来添加键值对,get(key)方法来检索与键相关的值,remove(key)方法来删除键值对,size()方法来获取哈希映射的当前大小。

HashMap(size_t capacity = 10) : capacity_(capacity), size_(0) { table_.resize(capacity_); }

这是C++中HashMap类的构造函数。它接受一个名为capacity的参数,默认值为10。在构造函数内部,它将成员变量capacity_设置为传入的capacity值,将size_设置为0,并调用table_.resize(capacity_)来调整哈希表的大小。这个构造函数的作用是初始化一个具有指定容量的空HashMap对象。

私有成员:
capacity_:哈希表的初始容量。
size_:表示当前存储在哈希映射中的元素数量。
表_:表示哈希表本身,实现为链表的向量。vector的每个元素都是键值对的链表(std::list)。

公共方法:

put(const K& key, const V& value):在哈希映射中插入一个键值对。它使用散列函数计算索引,然后遍历该索引处的链表,如果键已经存在,则更新该值,或者添加新的键值对。

get(const K& key):检索与给定键相关联的值。它使用散列函数计算索引,并在该索引处的链表中搜索键。如果找到,它返回相应的值;否则,它将抛出运行时错误。

remove(const K& key):删除与给定键相关联的键值对。它使用散列函数计算索引,并在该索引处的链表中搜索键。如果找到,则删除键值对并减小大小;否则,返回false。

size():返回当前哈希映射的大小。

Private Method:

hash(const K& key):该方法使用std::hash函数计算给定键的哈希值。

相关实践学习
【文生图】一键部署Stable Diffusion基于函数计算
本实验教你如何在函数计算FC上从零开始部署Stable Diffusion来进行AI绘画创作,开启AIGC盲盒。函数计算提供一定的免费额度供用户使用。本实验答疑钉钉群:29290019867
建立 Serverless 思维
本课程包括: Serverless 应用引擎的概念, 为开发者带来的实际价值, 以及让您了解常见的 Serverless 架构模式
目录
相关文章
|
23天前
|
存储 编译器 对象存储
【C++打怪之路Lv5】-- 类和对象(下)
【C++打怪之路Lv5】-- 类和对象(下)
21 4
|
23天前
|
编译器 C语言 C++
【C++打怪之路Lv4】-- 类和对象(中)
【C++打怪之路Lv4】-- 类和对象(中)
20 4
|
23天前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
17 1
|
1月前
|
存储 编译器 C++
【C++类和对象(下)】——我与C++的不解之缘(五)
【C++类和对象(下)】——我与C++的不解之缘(五)
|
1月前
|
编译器 C++
【C++类和对象(中)】—— 我与C++的不解之缘(四)
【C++类和对象(中)】—— 我与C++的不解之缘(四)
|
1月前
|
编译器 C语言 C++
C++入门3——类与对象2-2(类的6个默认成员函数)
C++入门3——类与对象2-2(类的6个默认成员函数)
23 3
|
1月前
|
存储 编译器 C语言
C++入门2——类与对象1(类的定义和this指针)
C++入门2——类与对象1(类的定义和this指针)
24 2
|
1月前
|
C++
C++番外篇——对于继承中子类与父类对象同时定义其析构顺序的探究
C++番外篇——对于继承中子类与父类对象同时定义其析构顺序的探究
51 1
|
1月前
|
编译器 C语言 C++
C++入门4——类与对象3-1(构造函数的类型转换和友元详解)
C++入门4——类与对象3-1(构造函数的类型转换和友元详解)
18 1
|
1月前
|
C++
C++番外篇——日期类的实现
C++番外篇——日期类的实现
79 1