【C++】哈希——unordered系列容器哈希概念哈希冲突

文章目录

  • 1. unordered系列的关联式容器
    • 1.1 引言
    • 1.2 unordered_map的使用说明
    • 1.3 unordered_set的使用说明
    • 1.4 unordered_set和unordered_map的应用
    • 1.5 性能比较
  • 2. 哈希概念
  • 3. 哈希函数
  • 4. 哈希冲突
  • 5. 哈希冲突的解决——开散列和闭散列
    • 5.1 闭散列
    • 5.2 开散列

1. unordered系列的关联式容器

1.1 引言

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log_2 N log2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍， unordered_multimap和unordered_multimap可以去自行查看使用文档cplusplus

注意：实际上，unordered系列容器的使用和map/set基本一致，区别就在于unordered系列只支持单向迭代器，并且由于结构的限制，遍历unordered系列容器的顺序是无序的

1.2 unordered_map的使用说明

使用文档

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lh9sfZMp-1684930297303)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.41.16.png)]

void Test_unordered_map()
{
    unordered_map<string, int> countMap;
    string arr[] = { "苹果", "西瓜", "香蕉","苹果", "西瓜", "西瓜"};
    for(const auto& str : arr)
    {
        //countMap[str]++;
        auto it = countMap.find(str);
        if(it == countMap.end())
        {
            countMap.insert(make_pair(str, 1));
        }
        else
        {
            it->second++;
        }
    }
    for(const auto& kv : countMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zQ3hv30X-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.48.12.png)]

除了map的接口之外，由于unordered_map的底层是哈希桶，所以，有一些只属于哈希桶的接口

函数原型功能介绍
size_t bucket_count() const返回哈希桶中桶的总个数
size_t max_bucket_count() const返回哈希桶中能够容纳的最大的桶个数
size_t bucket_size(size_t n) const返回哈希桶中有效元素个数
**size_t bucket(const K& key) **返回元素key所在的桶号

1.3 unordered_set的使用说明

使用文档

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l4MBpovo-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.33.08.png)]

void Test_unordered_set()
{
    unordered_set<int> us;
    us.insert(10);
    us.insert(2);
    us.insert(4);
    us.insert(5);
    us.insert(3);
    us.insert(1);
    us.insert(10);
    unordered_set<int>::iterator it = us.begin();
    while(it != us.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YZHaJAyB-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2014.04.56.png)]

1.4 unordered_set和unordered_map的应用

在长度为2*N的数组中找到重复出现N次的数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xTk0r0sx-1684930297305)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2014.44.00.png)]

1.5 性能比较

void Test_efficient()
{
	const size_t N = 1000000;//测试的数据个数
    //构造两个数组，一个有序一个无序，用于测试
	vector<int> SortV;
    vector<int> UnsortV;
	SortV.reserve(N);
	UnsortV.reserve(N);
	srand(time(0));
	for (int i = 0; i < N; ++i)
	{
		UnsortV.push_back(rand());
        SortV.push_back(i);
	}
    //开始测试
    unordered_set<int> SortUs;
    unordered_set<int> UnsortUs;
	set<int> SortS;
	set<int> UnsortS;
    cout << "有序插入效率对比" << endl;
	size_t begin1 = clock();
	for (auto e : SortV)
	{
		SortS.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert sorted:" << end1 - begin1 << endl;
	size_t begin2 = clock();
	for (auto e : SortV)
	{
		SortUs.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert sorted:" << end2 - begin2 << endl;
    cout << "无序插入效率对比" << endl;
	size_t begin3 = clock();
	for (auto e : UnsortV)
	{
		UnsortS.insert(e);
	}
	size_t end3 = clock();
	cout << "set insert unsort:" << end3 - begin3 << endl;
	size_t begin4 = clock();
	for (auto e : UnsortV)
	{
		UnsortUs.insert(e);
	}
	size_t end4 = clock();
	cout << "unordered_set insert unsort:" << end4 - begin4 << endl;
	
    cout << "有序查找效率对比" << endl;
    size_t begin5 = clock();
	for (auto e : SortV)
	{
		SortS.find(e);
	}
	size_t end5 = clock();
	cout << "set find sorted:" << end5 - begin5 << endl;
	size_t begin6 = clock();
	for (auto e : SortV)
	{
		SortUs.find(e);
	}
	size_t end6 = clock();
	cout << "unordered_set find sorted:" << end6 - begin6 << endl;
    cout << "无序查找效率对比" << endl;
    size_t begin7 = clock();
	for (auto e : UnsortV)
	{
		UnsortS.find(e);
	}
	size_t end7 = clock();
	cout << "set find unsorted:" << end7 - begin7 << endl;
	size_t begin8 = clock();
	for (auto e : UnsortV)
	{
		UnsortUs.find(e);
	}
	size_t end8 = clock();
	cout << "unordered_set find unsorted:" << end8 - begin8 << endl;
    cout << "有序删除效率对比" << endl;
	size_t begin9 = clock();
	for (auto e : SortV)
	{
		SortS.erase(e);
	}
	size_t end9 = clock();
	cout << "set erase sorted:" << end9 - begin9 << endl;
	size_t begin10 = clock();
	for (auto e : SortV)
	{
		SortUs.erase(e);
	}
	size_t end10 = clock();
	cout << "unordered_set erase:" << end10 - begin10 << endl;
    cout << "无序删除效率对比" << endl;
    size_t begin11 = clock();
	for (auto e : UnsortV)
	{
		UnsortS.erase(e);
	}
	size_t end11 = clock();
	cout << "set erase sorted:" << end11 - begin11 << endl;
	size_t begin12 = clock();
	for (auto e : UnsortV)
	{
		UnsortUs.erase(e);
	}
	size_t end12 = clock();
	cout << "unordered_set erase:" << end12 - begin12 << endl;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wXEUyCsZ-1684930297305)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2015.07.18.png)]

可以看到随机数下unordered系列效率更高，但是有序数的情况下就不太行。

2. 哈希概念

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构，那么什么是哈希？

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

理想的搜索方法:可以不经过任何比较，一次直接从表中得到要搜索的元素。类似通过下标访问数组中任意位置的元素。 如果构造一种存储结构，通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放；搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功.

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

接下来我们看下面这个例子：

假设有数据集{1, 7, 6, 4, 5, 9};

哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小

按照这种存放方式，如果需要查找4，就直接通过4 % 10 = 4找到hash(key) = 4的位置，直接取出来即可，省略了多次key的比较，节约了时间。

请添加图片描述

3. 哈希函数

哈希结构最关键的点就是哈希函数的设置

哈希函数的设置原则

  • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

常见的哈希函数设置方法

  1. 直接定址法常用

    直接定址法是最常用的哈希函数，就是根据key直接取到存储位置，这里的位置可能是绝对位置也可能是相对位置。

    哈希函数：Hash(Key)= A*Key + B

    例如对于统计字符串中某种字符出现的次数，key的范围比较小，所以这里可以直接映射

    Hash(key) = 1 * ‘a’ - ‘a’,这里就把a映射给0，所以显而易见z映射给了26。

    但是如果数据比较分散的话，就不适合使用直接定址法了，比如对于集合{1, 2, 3, 4,99, 999},就会造成很大的空间浪费

  2. 除留余数法常用

    为了应对直接定址法中的数据较为分散造成空间浪费的情况，有人设计出了除留余数法，用于集中数据。设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的素数p作为除数，按照哈希函数，将关键码转换成哈希地址。

    **哈希函数：**Hash(key) = key % p (p<=m)

  3. 平方取中法了解

    假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址; 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址

    适合:不知道关键字的分布，而位数又不是很大的情况

  4. 折叠法了解

    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

    适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

  5. 随机数法了解

    选择一个随机函数，取关键字的随机函数值为它的哈希地址，

    **哈希函数：**Hash(key) = random(key),其中 random为随机数函数。

    通常应用于关键字长度不等时采用此法

  6. 数学分析法了解

    设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散 列地址。

    例如:假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同 的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还 可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

    适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

4. 哈希冲突

上面那个例子，使用哈希的方式解决，看起来这样的算法非常棒，但是，如果数据集中还有一个44需要被插入，怎么办呢？44对应的hashkey也是4，和4产生了冲突。这就是哈希冲突，也叫哈希碰撞。

对于两个数据元素的关键字 k i k_i ki​和 k j k_j kj​(i != j)，有 k i k_i ki​ != k j k_j kj​，但有:Hash( k i k_i ki​) == Hash( k j k_j kj​)，即:不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突/哈希碰撞，把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

哈希函数的设置决定了哈希冲突的产生可能性，哈希函数设置的越巧妙，越能够减小哈希冲突，但是哈希冲突是不可能被完全避免的

5. 哈希冲突的解决——开散列和闭散列

由于哈希冲突是不可避免的，所以当然要总结哈希冲突的解决方案，一般来说，解决方案分为两种——闭散列和开散列。

5.1 闭散列

闭散列也叫开放定址法：当发生哈希冲突的时候，如果哈希表还没有被装满，那么就有空余的位置存放，那么就可以把key存放到冲突位置的“下一个空位置”中。

那么，怎么寻找下一个空位置呢？

这里同样有很多种方式，最经典的就是线性探测

同样的，针对上述的哈希冲突的例子，现在需要插入元素44，通过哈希函数计算出哈希地址为4，因此44理论上插入的位置是4，但是由于该位置已经存放了值为4的元素，出现哈希冲突，所以依次向后探测，直到寻找到下一个空位置为止。

所以，针对线性探测的插入和删除算法如下：

  1. 插入

    • 通过哈希函数获取到待插入元素在哈希表中的为止

    • 如果该位置没有元素就直接插入新元素，如果该位置有元素就继续找下一个空位置，插入新元素

      image-20230523221935153

  2. 删除

    采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

    所谓伪删除法就是用一个状态标志来代表此位置的状态

    enum State {EMPTY, EXIST, DELETE};
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除

闭散列线性探测的哈希表代码实现插入删除查找

首先对于闭散列的哈希表，有以下的结构设计

  1. 由于伪删除法的存在，所以需要让表里面存放的数据中增加一个状态变量，这里使用一个枚举来给出状态情况

    enum State { EMPTY, EXIST, DELETE };

  2. 表中的元素类型是一个KV结构的pair和一个状态变量state，所以哈希数据结构体设计如下

    //HashData数据结构体
template<class K, class V>
struct HashData
{
    std::pair<K, V> _kv;
    State _state = EMPTY;
}

  3. 由于KV结构中的key是一个泛型，当我们在进行哈希映射的时候，需要先让其映射成为整型，然后才能够映射到哈希地址，所以这里提供一个仿函数，用于将key映射到整型家族

    //仿函数，映射到整型
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

由于string类型在哈希映射中使用的频率非常高，所以有人对string的哈希算法做了一些研究与总结，这里附上链接，有兴趣的小伙伴可以去看一看 [字符串哈希算法](各种字符串Hash函数 - clq - 博客园 (cnblogs.com)),下面是hash映射的string类型的特化

//模版特化，针对string类型
template<>
struct HashFunc<std::string>
{
    size_t operator()(const std::string& key)
    {
        //采用了特殊方法把各元素的值放在一起
        size_t hash = 0;
        for (auto ch : key)
        {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

  1. 闭散列哈希表的结构

    • 由于哈希表是KV模型，所以模板参数中肯定要有KV，除此之外，由于哈希映射的key要求是整型，所以一定需要提供一个仿函数来把key映射给整型

    • 哈希表本身使用一个vector来管理，再加上一个整型的n用来存放哈希表中的有效数据个数

    所以哈希表的结构就显而易见了

    template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
    HashTable()//由于哈希表需要根据容量来判断哈希地址，所以_tables必须要先初始化，所以这里显示写构造函数
        :_n(0)
	{
		_tables.resize(10);
	}
private:
    std::vector<Data> _tables;//表里面存储的是HashData，HashData内部是一个KV结构和一个状态
    size_t _n = 0;//存储表中的有效数据个数
};

  2. 插入

    //插入
bool Insert(const std::pair<K,V>& kv)
{
    if(Find(kv.first))//如果已经存在，插入失败返回false
        return false;
    //扩容:判断是否扩容的方式是判断负载因子大小 负载因子 = 存放有效个数/哈希表容量（一般对于线性探测来说都是小于1的）
    if(_n * 10 / _tables.size() >= 7)//负载因子大于0.7时扩容
    {
        //这里采用二倍的方式扩容，实际上不是这样扩容的，在上文中说明按照
        HashTable<K, V, Hash> newTable;
        newTable._tables.resize(2 * _tables.size());//重新创建一个哈希表，大小是原表的二倍
        for(auto& e : _tables)//遍历原表，如果有数据的话就在新表中插入
        {
            if(e._state == EXIST)
            {
                newTable.Insert(e._kv);
            }
        }
        _tables.swap(newTable._tables);//交换二者的表（vector对象），这里调用的是vecotr库里的swap
    }

    //插入数据
    size_t hashi = Hash()(kv.first) % _tables.size();//通过Hash的匿名对象映射出一个整形，通过这个整型除留余数从而定址
    while(_tables[hashi]._state == EXIST)//映射的位置已经有值，出现哈希冲突，进行线性探测
    {
        ++hashi;
        hashi %= _tables.size();//++之后可能大于size，所以需要 模等一下
    }

    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
    return true;
}

  3. 删除

    //删除
bool Erase(const K& key)
{
    //由于直接删除该位置的值会引发后面的值的映射错误（会导致在找的时候提前找到空，所以不能直接删除，要使用伪删除法删除，即给一个DELETE状态）
    Data* ret = Find(key);
    if(ret)//找到值
    {
        //将该位置的值状态置为DELETE，然后n--
        ret->_state = DELETE;
        --_n;
        return true;//返回true表示删除成功
    }
    else//哈希表中没有该值，返回false
    {
        return false;
    }
}

  4. 查找

    //查找
Data* Find(const K& key)
{
    //按照哈希函数的方式计算，得到哈希地址
    size_t hashi = Hash()(key) % _tables.size();
    //从该地址向后寻找，由于线性探测的问题，所以该地址不一定是实际存放要找的位置的值，所以需要继续向后找，直到遇到EMPTY为止
    while(_tables[hashi]._state != EMPTY)
    {
        if(_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
            return &_tables[hashi];//找到了返回地址
        else//否则++hashi继续寻找
        {
            ++hashi;
            hashi %= _tables.size();
        }
    }
    return nullptr;//最终遇到EMPTY都没找到，返回空指针
}

闭散列二次探测的哈希表代码实现插入删除查找

实际上，线性探测也是具有一定的缺陷的，线性探测的缺陷就是会将产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： H i H_i Hi​ = ( H 0 H_0 H0​ + i 2 i^2 i2 )% m, 或者： H i H_i Hi​ = ( H 0 H_0 H0​ - i 2 i^2 i2 )% m。其中：i =1,2,3…， H 0 H_0 H0​是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
那么，对于2.1中如果要插入44，产生冲突，使用解决后的情况为

image-20230524183116900

由于闭散列不管使用什么探测方式，都是治标不治本，所以这里就不再继续代码实现二次探测了，下面我们看一看开散列的实现方式

5.2 开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

image-20230524192605818

image-20230524192618547

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列哈希表代码实现插入删除查找

  1. 首先由于结构的原因，要把数据链接起来需要一个节点类：

    template<class K, class V>
struct HashNode
{
    std::pair<K, V> _kv;
    HashNode* _next;
    HashNode(const std::pair<K, V>& kv)
        :_kv(kv)
            ,_next(nullptr)
        {}
};

  2. 同样的，由于KV结构中的key是一个泛型，当我们在进行哈希映射的时候，需要先让其映射成为整型，然后才能够映射到哈希地址，所以这里提供一个仿函数，用于将key映射到整型家族

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

    1. 开散列的哈希表结构

      template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
    typedef HashNode<K, V> Node;
public:
    HashTable()
        :_n(0)
        {
            _tables.resize(10);
        }
private:
    std::vector<Node*> _tables;//本质上是一个指针数组，存放节点指针。
    size_t _n = 0;
};

    2. 插入

      bool Insert(const std::pair<K,V>& kv)
{
    if(Find(kv.first))
        return false;
    //扩容
    //负载因子为1的时候就扩容
    if(_n == _tables.size())
    {
        //扩容方式有两种，一种是遍历，然后创建新节点挂在新表上
        //由于方案一造成的消耗较大，所以这里就不实现了
        //                HashTable<K, V, Hash> newTable;
        //                newTable._tables.resize(2 * _tables.size());
        //另一种是直接更改节点的指向
        std::vector<Node*> newTables;
        newTables.resize(2* _tables.size(), nullptr);//这里暂时使用2倍的方式扩容
        for(size_t i = 0; i < _tables.size(); ++i)//遍历旧表，依次拿到每个桶的头节点
        {
            Node* cur = _tables[i];
            while(cur)
            {
                Node* next = cur->_next;//先使用一个指针保存next，以免更改cur指向之后找不到其他节点
                size_t hashi = Hash()(cur->_kv.first) % newTables.size();//计算哈希位置
                //头插到新表中
                cur->_next = newTables[hashi];
                newTables[hashi] = cur;

                cur = next;//迭代到next
            }
            _tables[i] = nullptr;//将旧表的内容置空，以免出现自动析构旧表的时候释放节点
        }
        _tables.swap(newTables);//交换旧表和新表
    }
    //插入
    size_t hashi = Hash()(kv.first) % _tables.size();//定址
    //头插
    Node* newnode = new Node(kv);
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    ++_n;

    return true;
}

    3. 删除

      bool Erase(const K& key)
{
    size_t hashi = Hash()(key) % _tables.size();
    Node* prev = nullptr;//用prev存放当前节点的上一个节点，从而链接cur的前后节点
    Node* cur = _tables[hashi];
    while(cur)
    {
        if(cur->_kv.first == key)//找到了,准备删除
        {
            if(_tables[hashi] == cur)//删除桶的头节点
            {
                _tables[hashi] = cur->_next;
            }
            else//删除非头节点
            {
                prev->_next = cur->_next;
            }

            delete cur;
            --_n;
            return true;
        }
        else//没找到
        {
            prev = cur;
            cur = cur->_next;
        }
    }

    return false;
}

    4. 查找

      Node* Find(const K& key)
{
    size_t hashi = Hash()(key) % _tables.size();//找到key对应的哈希地址
    Node* cur = _tables[hashi];//遍历该地址对应的哈希桶
    while(cur)
    {
        if(cur->_kv.first == key)//找到了
        {
            return cur;
        }
        else//没找到
        {
            cur = cur->_next;
        }
    }
    return nullptr;
}

    本节完……

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/22570.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Elasticsearch：Explicit mapping - 显式映射

Elasticsearch：Explicit mapping - 显式映射

显式映射相比较动态映射&#xff08;Dynamic mapping&#xff09;是需要我们在索引创建时就定义字段及其类型。这个和我们传统的 RDMS 数据库一样&#xff0c;在我们写入数据到数据库之前&#xff0c;我们需要工整地定义好每个字段及其类型和长度。Elasticsearch 既可以使用显式…
阅读更多...
使用柔性数组重写MyString

使用柔性数组重写MyString

hello&#xff0c;各位宝子&#xff0c;今天阿崽将使用c和柔性数组的方式重新去写String类 在开始本次知识前&#xff0c;首先给大家介绍下柔性数组这个buff特点&#xff1a; 结构中的柔性数组成员前面至少要包含一个其他成员 sizeof返回的这种结构大小不包括柔性数组的内存 …
阅读更多...
数据结构课程设计——哈夫曼编/译码器

数据结构课程设计——哈夫曼编/译码器

数据结构课程设计任务书 学生姓名&#xff1a; 专业班级&#xff1a;软件工程 指导教师&#xff1a; 工作单位&#xff1a; 题 目: 哈夫曼编/译码器 基础要求&#xff1a; &#xff08;1&#xff09;熟悉各种…
阅读更多...
数字信号处理基础(二):FFT和IFFT的使用以及详细分析代码书写思路

数字信号处理基础(二):FFT和IFFT的使用以及详细分析代码书写思路

目录 1. fft和ifft的原理1.1 fft1.2 ifft 2. 书写代码思路3. 完整代码4. 结果图 1. fft和ifft的原理 1.1 fft fft是快速傅里叶变换&#xff0c;是MATLAB中计算信号频谱的函数&#xff0c;使用方法是fft(x)&#xff0c;直接对信号x进行fft计算。 由于fft函数计算信号的频谱是0…
阅读更多...
vue3与vue2共存环境搭建

vue3与vue2共存环境搭建

1、全局安装vue2 npm install vue-cli -g2、自行在任意位置创建一个文件夹&#xff0c;局部安装vue3 npm初始化 npm initnpm初始化 提示&#xff1a; 初始化后 出现文件package.json 如果没有初始化 会报错&#xff0c;且文件夹中不会新增内容 3、局部安装vue3 npm install …
阅读更多...
宏工科技“全面”发力CIBF，助推电池智造“高效提质”

宏工科技“全面”发力CIBF，助推电池智造“高效提质”

5月16-18日&#xff0c;第十五届中国国际电池技术展览会&#xff08;CIBF2023&#xff09;在深圳盛大举行。宏工科技携电池材料与电池匀浆领域的创新产品和系统解决方案精彩亮相。 据了解&#xff0c;宏工科技在新能源行业的业务涉及电池材料整线产线、电池匀浆、电池回收三个…
阅读更多...
R语言实践——rWCVP入门

R语言实践——rWCVP入门

rWCVP入门 介绍1. 访问到WCVP1.1 方法一1.2 方法二&#xff08;谨慎&#xff09; 2. WCVP数据筛选2.1 关于按分类单元筛选的说明2.2 关于按分布区域筛选的说明 笔者实践 介绍 世界维管植物名录&#xff08;WCVP&#xff09;是维管植物物种的全球共识。它提供了科学已知的> …
阅读更多...
【C语言】结构体指针

【C语言】结构体指针

结构体指针 结构体基础知识注意对于成员的赋值 结构体指针指向结构体变量的指针结构体指针与结构体成员指针用结构体指针引用结构体成员 结构体 基础知识 初识结构体&#xff0c;可以先看这篇浅显易懂的文章结构体–基础篇 所谓结构体&#xff0c;是一组类型可以不同的相关变…
阅读更多...
怎么把录音转文字？推荐你这三款工具

怎么把录音转文字？推荐你这三款工具

随着科技不断发展&#xff0c;录音转文字的技术也逐渐被广泛应用于各种场景中。其中最常见的一种就是会议记录。在日常工作中&#xff0c;会议是企业和组织中必不可少的一个环节&#xff0c;但在会议过程中的录音和记录往往需要花费大量的时间和精力。这个时候&#xff0c;我们…
阅读更多...
基于MAC地址的ACL配置

基于MAC地址的ACL配置

基于MAC地址的ACL配置 【实验目的】 掌握基于MAC地址的标准ACL的配置。验证配置。 【实验拓扑】 实验拓扑如图1所示。 图1 实验拓扑 设备参数如表所示。 表1 设备参数表 设备 接口 IP地址 子网掩码 默认网关 S1 e0/0 N/A N/A N/A e0/1 N/A N/A N/A PC1 N/…
阅读更多...
架构-软件工程模块-2

架构-软件工程模块-2

系统分析 数据流图可能出案例题&#xff0c;状态转换图了解作用即可 用例图、类图选择题多&#xff0c;暴徒了解即可 #mermaid-svg-lGozbtkYJPEQF1eo {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-lGozbtkYJPEQF1e…
阅读更多...
c++学习——c与c++const修饰的变量的区别

c++学习——c与c++const修饰的变量的区别

c语言下const修饰的变量 1、c语言下const修饰的变量都有空间 2. c语言的const修饰的全局变量具有外部链接属性 07 const修饰的变量.c #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #include <stdlib.h>const int a 10;//常…
阅读更多...
解析使用FPGA逻辑实现FIR滤波器的几种架构

解析使用FPGA逻辑实现FIR滤波器的几种架构

有限脉冲响应(finite impulse response&#xff0c;FIR)数字滤波器 一、FIR数字滤波器理论介绍 FIR滤波器的实质就是输入序列与系统脉冲响应的卷积&#xff0c;即&#xff1a; 其中&#xff0c;N为滤波器的阶数&#xff0c;也即抽头数&#xff1b;x(n)为第n个输入序列&#xff…
阅读更多...
AI人工智能标记数据的技术：类型、方法、质量控制、应用

AI人工智能标记数据的技术：类型、方法、质量控制、应用

AI人工智能 标记数据 在人工智能&#xff08;Artificial Intelligence&#xff0c;简称AI&#xff09;领域中&#xff0c;标记数据是非常重要的一环。它是指对原始数据进行标记和注释&#xff0c;以便机器学习算法可以理解和利用这些数据。标记数据可以提高机器学习模型的准确…
阅读更多...
研发项目工时统计工具哪个好？9大工时管理系统盘点

研发项目工时统计工具哪个好？9大工时管理系统盘点

工时管理是项目型企业的重要需求&#xff0c;特别是在人力成本占比较高的行业&#xff0c;如软件开发、设计咨询、会计律师等。工时管理可以帮助企业核算项目人工成本&#xff0c;控制成本投入&#xff0c;提高项目利润&#xff0c;客观考核员工绩效&#xff0c;优化资源分配等…
阅读更多...
HackTheBox-关卡Fawn

HackTheBox-关卡Fawn

1. 连接靶场&#xff0c;打开FAWN实例场景&#xff0c;检查是否互通 TASK1 3 个字母的首字母缩写词 FTP 代表什么&#xff1f; 答案是&#xff1a;File Transfer Protocol TASK2 问题是&#xff1a;FTP服务通常监听哪个端口&#xff1f; FTP监听的TCP端口号为21,监听的数据端…
阅读更多...
计算机操作系统（慕课版）第二章课后题答案

计算机操作系统（慕课版）第二章课后题答案

一、简答题 (1)什么是前趋图&#xff1f;试画出下面四条语句的前趋图. S1&#xff1a;axy&#xff1b; S2&#xff1a;bz1&#xff1b; S3&#xff1a;ca-b&#xff1b; S4&#xff1a;wc1&#xff1b; 答&#xff1a;前趋图(Precedence Graph)是一个有向无循环图&#xff0c;…
阅读更多...
进程控制--进程的等待

进程控制--进程的等待

回顾 之前我们已经学习了进程的状态和进程的退出如果你没有这些基础知识&#xff0c;应先去了解进程的相关基础知识。 这次我们主要来学习如何让进程等待子进程的退出。 为什么要等待子进程&#xff1f; 之前我们在学习进程的状态的时候&#xff0c;我们知道了进程有一种状态…
阅读更多...
spring boot +Sa-Token优雅的实现项目鉴权！

spring boot +Sa-Token优雅的实现项目鉴权！

1. 技术选型 最近在做登录、授权的功能&#xff0c;一开始考虑到的是spring boot spring security&#xff0c;但spring security太重&#xff0c;而我们是轻量级的项目&#xff0c;所以&#xff0c;spring security不适合我们。 而后考虑spring boot shiro&#xff0c;但s…
阅读更多...
ChatGPT ✖️ 前端 = 有点er意思

ChatGPT ✖️ 前端 = 有点er意思

HOT! HOT! HOT! &#x1f525; &#x1f525; &#x1f525; ChatGPT登上了国内各大平台的热搜榜&#xff0c;应该在去年11月末的时候就有不少同学了解并使用过&#xff0c;那个时候它刚刚问世&#xff0c;在互联网圈子里有了很大的热度&#xff0c;但是对于大众来说&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023