【C++】哈希表

目录

一、unordered系列关联式容器

二、哈希

2.1 概念

2.2 哈希冲突

2.3 哈希函数

(1)直接定址法

(2)除留余数法

(3)平方取中法

(4)折叠法

(5)随机数法

(6)数学分析法

三、哈希冲突解决方案

3.1 闭散列

3.1.1 线性探测

(1)处理不同类型的key

(2)插入元素

(3)删除元素

(4)扩容

(5)总结

3.1.2 线性探测模拟实现闭散列

3.1.3 二次探测

3.2 开散列

3.2.1 概念 

3.2.2 模拟实现开散列

四、模拟实现哈希表和Unordered系列关联式容器

4.1 HashTable.h

4.2 Unordered_Set.h

4.3 Unordered_Map.h


一、unordered系列关联式容器

在C++的STL库中,除了底层为红黑树结构的map和set,还有底层为哈希表的unordered_map和unordered_set

由于红黑树的性质,我们遍历map和set会得到一个有序的序列

而顾名思义,我们遍历unordered_map和unordered_set得到的是一个无序的序列。这两个容器的使用方式与map和set类似,只是底层结构不同,这里就不对二者的使用方式做详细介绍了


二、哈希

2.1 概念

在顺序结构以及平衡树中,元素的key和其存储的位置之间没有关联,因此在查找某个元素时需要经过多次对key的比较。所以搜索的效率取决于搜索过程中的比较次数。在依靠比较的排序算法中,其排序效率也取决于排序过程中元素的比较次数。

是否有一种方法能够不经过任何比较,就能直接知道要查找的元素位置,从而在O(1)的时间复杂度内得到要查找的元素呢?

我们可以构造一种存储结构,通过某种函数能够使元素的存储位置和它的key之间建立一个映射关系,那么在查找该元素时就能直接通过key得到它的存储位置。

这种方法就是哈希(Hash),又称为散列。哈希是一个广义的算法,也可以认为是一种思想

哈希算法中使用的将元素的存储位置和key建立映射的函数称为哈希函数或散列函数,构造出的结构称为哈希表(Hash Table)或散列表

以26个英文字母为例,我们可以用一个大小为26的数组来存储它们,将每一个下标都与一个字母建立映射关系,例如0为a,1为b。这种线性的映射关系适用于key的范围小且连续的情况,称为直接定址法,在后面会介绍。

又例如计数排序,就是对哈希直接定址法的变形应用。将每个元素与其存储的位置建立映射关系,然后统计这个元素出现的次数。

2.2 哈希冲突

有时,key的范围较大且过于分散,如果此时还使用直接定址法,就会导致空间的浪费。

例如:

此时我们可以使用除留余数法,将key除以一个不大于散列表长度的数,将所得的余数作为映射的哈希地址

将key除以散列表的长度,就使一个范围大且分散的集合存储到一个较小的散列表中了

但是此时出现了一个问题:有不同的值映射到相同的位置上了

这就是哈希冲突(哈希碰撞),即不同的key通过哈希函数计算出了相同的哈希地址,我们把key不同但哈希地址相同的元素称为同义词

2.3 哈希函数

哈希函数是一种建立映射关系的方法,我们使用某种特定的方法处理key得到相对应的哈希地址

常见的哈希函数有:

(1)直接定址法

key和哈希地址之间是线性的映射关系,适用于key的范围较小且连续的情况。key和哈希地址是一对一的关系,不存在哈希冲突

(2)除留余数法

设散列表的大小为m,取一个不大于m(接近m或等于m)的质数p作为除数,将key除以p后得到的余数作为哈希地址。key和哈希地址是多对一的关系,存在哈希冲突

(3)平方取中法

对key取平方,取其平方后的中间几位作为哈希地址

适合不知道key的分布且key的位数不大的情况

(4)折叠法

将key从左到右分割成位数相等的几部分,然后将这几部分叠加求和,并按散列表长度取后几位作为哈希地址

(5)随机数法

选择一个随机函数,取key的随机函数值作为它的哈希地址

(6)数学分析法

找出key中数字的规律,选择数字差别较大的几位作为哈希地址

例如不同电话号的前几位容易重复,但后四位不容易重复,所以我们可以取后四位作为哈希地址


三、哈希冲突解决方案

解决哈希冲突的两种常见方法:闭散列开散列

3.1 闭散列

闭散列又称开放定址法。当发送哈希冲突时,如果散列表未满,那么就把出现冲突的key存放到冲突位置的下一个空位置

如何寻找下一个空位置呢?

3.1.1 线性探测

线性探测就是从发生冲突的位置开始依次向后探测直到寻找到下一个空位置

(1)处理不同类型的key

在使用map、set或者unordered_map、unordered_set时,我们可以将字符串或者浮点数作为key

也就是说,我们的key不一定是整数。此时就需要在建立映射前对key进行处理。

针对浮点数等非字符串类型的key,我们可以直接强转为size_t类型

针对字符串类型的key,我们可以使用字符串哈希,也就是把一个字符串映射成一个数

此处我们使用BKDR字符串哈希:

size_t operator()(const string& key)
{// BKDR字符串哈希size_t ret = 0;for (auto i : key){ret *= 31;ret += i;}return ret;
}

各种字符串Hash函数比较 (byvoid.com)icon-default.png?t=N7T8https://byvoid.com/zhs/blog/string-hash-compare/

(2)插入元素

先通过哈希函数获取待插入元素在哈希表中的位置,如果该位置为空则直接插入,如果有元素则使用线性探测找到下一个空位置再插入

举一个除留余数法的例子:

4444通过哈希函数计算哈希地址,应该插入下标为4的位置,但该位置已经有元素了,此时发生哈希冲突。

使用线性探测从下标为4的位置向后寻找空位置,找到第一个空位即下标为6的位置,将4444插入

我们如何保证哈希表中一定有空位置呢?这里引入一个概念,即负载因子

负载因子:哈希表存储元素的个数 / 哈希表大小

如果负载因子太大(相同大小的哈希表中存储更多的key),可以提高空间利用率,但是冲突的概率大大增加,降低效率

如果负载因子太小(相同大小的哈希表中存储更少的key),可以降低冲突的概率,但是空间利用率也会降低

我们只要保证哈希表存储元素的个数除以哈希表的大小不超过负载因子,一旦超过负载因子则扩容,就能够确保哈希表中一定有空位置,并且冲突的概率保持在一个合理的范围

(3)删除元素

采用闭散列处理哈希冲突时,我们要如何删除哈希表中已有的元素呢?

如果采用置零或者置为-1的方式是行不通的,因为你无法通过该位置的key判断是否是删除后的值还是原本存储的值

我们可以为哈希表的每个位置设置一个标记空为EMPTY有元素的话标记为EXIST

这样就行了吗?如果我们把删除后的位置从EXIST重新标记为EMPTY,那么在搜索元素时可能会出现错误判断的情况。我们以上面的情况为例:

删除34后,下标为4的位置被置为EMPTY。当我们搜索4444时,因为下标为4的位置标记为EMPTY,所以判断哈希表中没有4444

实际上4444因为哈希冲突被我们使用线性探测放到了后面

所以只有EMPTY和EXIST两种标记是不够的,我们需要采用伪删除法来删除元素,即多增加一个DELETE标记表示该位置曾经有元素但已被删除,当搜索的位置标记为DELETE时需要继续向后搜索。

(4)扩容

当哈希表存储元素的个数除以哈希表的大小超过了负载因子,就需要进行扩容

但是如果我们用除留余数法,将哈希表长度作为除数时,就不能直接在原地进行resize扩容。因为扩容后长度发送变化,映射关系也会改变

所以在扩容时我们需要先开一块新空间,重新建立映射关系,再释放旧空间

(5)总结

线性探测的优点很明显:实现简单

缺点也很明显:容易发生一连串的哈希冲突,与其逐个向后寻找下一个空位置的方式有关

3.1.2 线性探测模拟实现闭散列

namespace open_address // 开放定址法
{enum Status{EMPTY, // 空EXIST, // 已有值DELETE // 曾经存过值但已被删除};template<class K, class V>struct HashData{pair<K, V> _kv;Status _s; // 目标位置的状态};template<class K>struct HashMapping{size_t operator()(const K& key){return (size_t)key; // 把其他类型的key都强转成无符号整形}};template<>struct HashMapping<string> // 如果key是string类型的就无法用上面的仿函数来转换了,所以写一个特化版本的{size_t operator()(const string& key){// BKDR字符串哈希size_t ret = 0;for (auto i : key){ret *= 31;ret += i;}return ret;}};template<class K, class V, class Hash = HashMapping<K>> // key不一定是整型,需要一个仿函数转换key的类型便于建立映射class HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;if (_n * 10 / _tables.size() == 7) // 负载因子到达0.7,扩容{// 不能直接在原基础上扩容,否则映射关系改变后无法找到原值size_t newsize = _tables.size() * 2;HashTable<K, V, Hash> newTable;newTable._tables.resize(newsize);// 遍历旧表,将元素插入新表,重新建立映射for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newTable.Insert(_tables[i]._kv); // 复用原函数}}_tables.swap(newTable._tables); // 新旧表交换}Hash hf;// 线性探测size_t hashI = hf(kv.first) % _tables.size(); // 用无符号可以映射负数while (_tables[hashI]._s == EXIST){hashI++;hashI %= _tables.size();}_tables[hashI]._kv = kv;_tables[hashI]._s = EXIST;_n++;return true;}bool Erase(const K& key){HashData<K, V>* ret = Find(key); // 检测目标是否存在if (ret){ret->_s = DELETE; // 伪修改:直接修改状态--_n;return true;}else return false;}HashData<K, V>* Find(const K& key){Hash hf;size_t hashI = hf(key) % _tables.size();while (_tables[hashI]._s != EMPTY) // 如果遍历到空位置还没找到则说明目标值不存在{if (_tables[hashI]._s == EXIST && _tables[hashI]._kv.first == key) // 找到目标{return &_tables[hashI];}hashI++;hashI %= _tables.size();}return nullptr;}void Print(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST)cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;else if(_tables[i]._s == EMPTY)printf("[%d]->\n", i);elseprintf("[%d]->D\n", i);}}private:vector<HashData<K, V>> _tables;size_t _n; // 存储关键字个数};
}

3.1.3 二次探测

线性探测在插入元素时逐个向后查找空位置,步长不变

二次探测相对线性探测的区别在于,在查找空位置时跳跃式的前后交替查找,每次的步长都是前一次的二次方

3.2 开散列

3.2.1 概念 

开散列法又叫链地址法,用开散列法实现的哈希表又叫哈希桶

在哈希桶中,其每一个位置都是一个链表,原本会产生哈希冲突的、具有相同哈希地址的元素归并成一个集合,用链表链接起来,称为一个桶,并将各个链表的头节点存储在哈希表中

例如:

可以看到,原本在除留余数法下会发生哈希冲突的元素,此时都被放进了同一个桶中。所以哈希桶能够完美解决哈希冲突的问题

所以用开散列法插入元素和删除元素,按照链表的方式进行操作即可。需要注意的是,因为我们采用的是单链表,不好找尾,所以插入元素时应该头插

不断向哈希桶插入元素,虽然不会发生哈希冲突,但是可能会导致某个桶过长从而影响性能,所以哈希桶在一定条件下也需要进行扩容。

哈希桶的负载因子可以开到1,也就是平均每个位置都有一个元素。当达到条件时,首先创建一个新表,重新将每个节点映射到新表中,然后销毁旧表。

3.2.2 模拟实现开散列

namespace hash_bucket // 哈希桶:数组加单链表
{template<class K, class V>struct HashNode{HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}pair<K, V> _kv;HashNode* _next;};template<class K>struct HashMapping{size_t operator()(const K& key){return (size_t)key;}};template<>struct HashMapping<string>{size_t operator()(const string& key){// BKDR字符串哈希size_t ret = 0;for (auto i : key){ret *= 31;ret += i;}return ret;}};template<class K, class V, class Hash = HashMapping<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_tables.resize(10);}~HashTable() // vector可以自己析构,但哈希桶需要我们手动析构{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool Insert(const pair<K, V> kv){if (Find(kv.first)) return false;Hash hf;if (_n == _tables.size()) // 负载因子为1时扩容{// 为了避免析构和重新创建节点的消耗,直接把旧表中的节点重新映射至新表vector<Node*> new_tables;new_tables.resize(_tables.size() * 2);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next; // 头插会改变节点的指向,所以需要保存next// 计算新的映射位置size_t new_hashi = hf(cur->_kv.first) % new_tables.size();cur->_next = new_tables[new_hashi];new_tables[new_hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(new_tables);}size_t hashi = hf(kv.first) % _tables.size();Node* newnode = new Node(kv);// 哈希桶头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}bool Erase(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();Node* prev = nullptr; // 单链表无法找头,需要提前保存Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr) // 待删除节点在头部_tables[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;return true;}prev = cur;cur = cur->_next;}return false;}Node* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr; }void Print(){for (int i = 0; i < _tables.size(); i++){cout << i << " : ";Node* cur = _tables[i];while (cur){cout << "[" << cur->_kv.first << "," << cur->_kv.second << "]" << "->";cur = cur->_next;}cout << endl;}cout << endl;}size_t size(){return _n;}private:vector<Node*> _tables;size_t _n = 0;};
}


四、模拟实现哈希表和Unordered系列关联式容器

4.1 HashTable.h

#pragma oncenamespace hash_bucket // 哈希桶:数组加单链表
{template<class T>struct HashNode{HashNode(const T& data):_data(data), _next(nullptr){}T _data;HashNode<T>* _next;};template<class K>struct HashMapping{size_t operator()(const K& key){return (size_t)key;}};template<>struct HashMapping<string>{size_t operator()(const string& key){// BKDR字符串哈希size_t ret = 0;for (auto i : key){ret *= 31;ret += i;}return ret;}};// 迭代器和HashTable相互依赖:前置声明template<class K, class T, class KeyOfT, class Hash> //声明时不需要带缺省参数class HashTable;template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;//如果pht不定义为const变量,const版本的end和begin就无法使用构造函数(const this),否则会发生权限放大__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi):_node(node), _pht(pht), _hashi(hashi){}Self& operator++(){if (_node->_next)_node = _node->_next;else //当前的桶已走到底部{++_hashi; while (_hashi < _pht->_tables.size()) //找下一个非空的桶{if (_pht->_tables[_hashi]){_node = _pht->_tables[_hashi];break;}++_hashi;}} if (_hashi == _pht->_tables.size()) //走到结束还没找到非空的桶_node = nullptr;return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}bool operator!=(const Self& s){return _node != s._node;}Node* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;size_t _hashi;};template<class K, class T, class KeyOfT, class Hash> //KeyOfT传入仿函数用于取出key,Hash用于将key转化为合适的值class HashTable{template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct __HTIterator; //迭代器需要访问私有成员_tables,需要成为HashTable的友元typedef HashNode<T> Node;public:typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++) //找到第一个不为空的桶{if (_tables[i])return iterator(_tables[i], this, i);}return end(); //如果表为空则返回end()}iterator end(){return iterator(nullptr, this, -1);}const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){if (_tables[i])return const_iterator(_tables[i], this, i);}return end();}const_iterator end() const{return const_iterator(nullptr, this, -1);}HashTable(){_tables.resize(10);}~HashTable() // vector可以自己析构,但哈希桶需要我们手动析构{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}pair<iterator, bool> Insert(const T& data){KeyOfT kot;Hash hf;iterator it = Find(kot(data));if (it != end()) return make_pair(it, false); //如果data已存在则返回对应位置的迭代器和falseif (_n == _tables.size()) // 负载因子为1时扩容{// 为了避免析构和重新创建节点的消耗,直接把旧表中的节点重新映射至新表vector<Node*> new_tables;new_tables.resize(_tables.size() * 2);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next; // 头插会改变节点的指向,所以需要保存next// 计算新的映射位置size_t new_hashi = hf(kot(cur->_data)) % new_tables.size();cur->_next = new_tables[new_hashi];new_tables[new_hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(new_tables);}size_t hashi = hf(kot(data)) % _tables.size();Node* newnode = new Node(data);// 哈希桶头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return make_pair(iterator(newnode, this, hashi), true); //返回data插入位置的迭代器和true}bool Erase(const K& key){KeyOfT kot;Hash hf;size_t hashi = hf(key) % _tables.size();Node* prev = nullptr; // 单链表无法找头,需要提前保存Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr) // 待删除节点在头部_tables[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;return true;}prev = cur;cur = cur->_next;}return false;}iterator Find(const K& key){KeyOfT kot;Hash hf;size_t hashi = hf(key) % _tables.size(); //建立映射Node* cur = _tables[hashi];while (cur) //在对应的桶中查找{if (kot(cur->_data) == key)return iterator(cur, this, hashi);cur = cur->_next;}return end();}size_t size(){return _n;}private:vector<Node*> _tables;size_t _n = 0;};
}

4.2 Unordered_Set.h

#pragma once
#include "HashTable.h"namespace Eristic
{template<class K, class Hash = hash_bucket::HashMapping<K>>class unordered_set{struct Unordered_Set_KeyOfT{const K& operator()(const K& key){return key;}};public://用typename说明此处是对类型重命名typedef typename hash_bucket::HashTable<K, K, Unordered_Set_KeyOfT, Hash>::const_iterator iterator; //set禁止修改,所以只有const迭代器typedef typename hash_bucket::HashTable<K, K, Unordered_Set_KeyOfT, Hash>::const_iterator const_iterator;const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator, bool> insert(const K& key){auto ret = _ht.Insert(key);//HashTable中的Insert返回的是普通迭代器,而set中只有const迭代器,需要进行类型转换return pair<iterator, bool>(iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, K, Unordered_Set_KeyOfT, Hash> _ht;};
}

4.3 Unordered_Map.h

#pragma once
#include "HashTable.h"namespace Eristic
{template<class K, class V, class Hash = hash_bucket::HashMapping<K>>class unordered_map{struct Unordered_Map_KeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, Unordered_Map_KeyOfT, Hash>::iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, Unordered_Map_KeyOfT, Hash>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}private:hash_bucket::HashTable<K, pair<const K, V>, Unordered_Map_KeyOfT, Hash> _ht;};
}

完.

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

springboot注解@ComponentScan注解作用

一 ComponentScan作用 1.1 注解作用 项目会默认扫描SpringBootApplication注解所在路径的同级和下级的所有子包&#xff0c;使用ComponentScan后他会取代掉默认扫描。 ComponentScan 是Spring框架的注解&#xff0c;它的作用是扫描指定的包路径下的标有 Component、Service、…

已备案网站变更并且不影响现有业务的方案

已备案网站变更并且不影响现有业务的方案 近日有个工作上的需求&#xff0c;已备案网站变更并且不影响现有业务&#xff0c;记录一下。 需求 域名&#xff1a;XXXXXX.com备案变更前主体&#xff1a; 海南XXXXXX科技有限公司 备案变更后主体&#xff1a; 深圳XXXXXX科技有限…

梦想CAD二次开发

1.mxdraw简介 mxdraw是一个HTML5 Canvas JavaScript框架&#xff0c;它在THREE.js的基础上扩展开发&#xff0c;为用户提供了一套在前端绘图更为方便&#xff0c;快捷&#xff0c;高效率的解决方案&#xff0c;mxdraw的实质为一个前端二维绘图平台。你可以使用mxdraw在画布上绘…

50-2 内网信息收集 - 内网工作环境(域相关知识)

一、工作组 工作组(Work Group)是局域网中最基本的资源管理模式,适用于小规模网络环境。 工作组的定义: 工作组是将不同功能或部门的计算机分组管理的方式。它提供了层次化的网络资源管理,使得组织内的计算机可以按照功能或部门分类。每个工作组有一个自定义的主机名称,…

Java访问修饰符的区别

public&#xff1a;公开的&#xff0c;任何地方都可以访问。 protected&#xff1a;受保护的&#xff0c;同一个包中的类和所有子类(可跨包)可以访问。 private&#xff1a;私有的&#xff0c;只有在同一个类中可以访问。 默认&#xff08;无修饰符&#xff09;&#xff1a;包级…

零基础STM32单片机编程入门(四)ADC详解及实战含源码视频

文章目录 一.概要二.STM32F103C8T6单片机ADC外设特点三.STM32单片机ADC内部结构图1.ADC相关引脚说明2.ADC通道分类3.触发源4.转换周期5.电压转换计算6.更精确电压转换计算 四.规则通道ADC采集信号流向1.单次转换模式2.连续转换模式 五.CubeMX配置一个ADC采集例程六.CubeMX工程源…

AI基础:从线性回归到梯度下降

一个简单的问题&#xff1a; 如果此时你正站在迷路缭绕的山坡上&#xff0c;能见度不高&#xff0c;但是你又想去往最低的山谷的位置&#xff0c;怎么走&#xff1f; 很简单&#xff0c;哪里陡那就往那里走呗——而这就是梯度下降算法的思想。 古话说&#xff1a;“先发制于人…

mindspore打卡第9天 transformer的encoder和decoder部分

mindspore打卡第9天 transformer的encoder和decoder部分 import mindspore from mindspore import nn from mindspore import ops from mindspore import Tensor from mindspore import dtype as mstypeclass ScaledDotProductAttention(nn.Cell):def __init__(self, dropout_…

计算机毕业设计hadoop+spark+hive知识图谱酒店推荐系统 酒店数据分析可视化大屏 酒店爬虫 高德地图API 酒店预测系统 大数据毕业设计

酒店推荐系统开题报告 一、研究背景与意义 随着旅游业的蓬勃发展和人们生活水平的提高&#xff0c;酒店行业迎来了前所未有的发展机遇。然而&#xff0c;面对众多的酒店选择&#xff0c;消费者往往难以在短时间内找到最适合自己需求和预算的酒店。因此&#xff0c;开发一款高…

推荐一款免费的GIF编辑器——【ScreenToGif编辑器】

读者大大们好呀&#xff01;&#xff01;!☀️☀️☀️ &#x1f440;期待大大的关注哦❗️❗️❗️ &#x1f680;欢迎收看我的主页文章➡️木道寻的主页 文章目录 &#x1f525;前言&#x1f680;素材准备&#x1f680;逐帧制作&#x1f680;保存图片⭐️⭐️⭐️总结 &#…

LangGPT:高质量提示词框架

题目&#xff1a;LangGPT: Rethinking Structured Reusable Prompt Design Framework for LLMs from the Programming Language作者: Ming Wang; Yuanzhong Liu; Xiaoming Zhang; Songlian Li; Yijie Huang; Chi Zhang; Daling Wang; Shi Feng; Jigang LiDOI: 10.48550/arXiv.2…

【排序算法】—— 希尔排序

目录 一、希尔排序原理 二、希尔排序的思路 三、希尔排序为什么快 四、如何取增量 五、源码 希尔排序是简单插入排序的一种升级版&#xff0c;它也是用了插入的思想&#xff0c;而插入排序相比冒泡排序和选择排序的效率要高的多&#xff0c;再将它优化为希尔排序后效率跟原…

【C++11(二)】lambda表达式和可变参数模板

一、可变参数模板 C11的新特性可变参数模板 能够让您创建可以接受 可变参数的函数模板和类模板 // Args是一个模板参数包&#xff0c;args是一个函数形参参数包 // 声明一个参数包Args...args&#xff0c;这个参数包中可以包含0到任意个模板参数。 template <class ...Arg…

智慧记账,轻松管理,让借还款明细一目了然,一键导出

在繁忙的生活中&#xff0c;财务记账管理往往成为我们的一大难题。尤其是面对频繁的借还款项&#xff0c;如何快速、准确地记录每一笔收支明细&#xff0c;并确保数据的清晰、完整&#xff0c;成为许多人关注的焦点。现在&#xff0c;我们为您带来一款全新的记账管理工具——晨…

【第三方JSON库】org.json.simple用法初探—Java编程【Eclipse平台】【不使用项目管理工具】【不添加依赖解析】

本文将重点介绍&#xff0c;在不使用项目管理工具&#xff0c;不添加依赖解析情况下&#xff0c;【第三方库】JSON.simple库在Java编程的应用。 JSON.simple是一种由纯java开发的开源JSON库&#xff0c;包含在JSON.simple.jar中。它提供了一种简单的方式来处理JSON数据和以JSO…

有趣的仿神经猫html5圈小猫游戏源码

有趣的仿神经猫html5圈小猫游戏源码,点击小圆点&#xff0c;围住小猫游戏。猫已经跑到地图边缘&#xff0c;你输了。内含json数据&#xff0c;部署到服务器方可运行 微信扫码免费获取源码

Kafka 位移

Consumer位移管理机制 将Consumer的位移数据作为一条条普通的Kafka消息&#xff0c;提交到__consumer_offsets中。可以这么说&#xff0c;__consumer_offsets的主要作用是保存Kafka消费者的位移信息。使用Kafka主题来保存位移。 消息格式 位移主题就是普通的Kafka主题。也是…

Type-C接口OTG转接器的应用与发展

随着科技的飞速发展&#xff0c;智能移动设备已成为我们生活中不可或缺的一部分。而在这些设备的连接与数据传输中&#xff0c;Type-C接口以其高效、便捷的特性逐渐占据了主导地位。OTG&#xff08;On-The-Go&#xff09;技术则进一步扩展了Type-C接口的功能&#xff0c;使得设…

JavaSE主要内容(全套超完整)

一、为什么选择Java&#xff08;Java的优势&#xff09; 1、应用面广&#xff1a; 相较于其他语言&#xff0c;Java的应用面可谓是非常广&#xff0c;这得益于他的跨平台性和其性能的稳定性。他在服务器后端&#xff0c;Android应用开发&#xff0c;大数据开发&#xf…

鼠尾草(洋苏草)

鼠尾草&#xff08;Salvia japonica Thunb.&#xff09;&#xff0c;又名洋苏草、普通鼠尾草、庭院鼠尾草&#xff0c;属于唇形科鼠尾草属多年生草本植物。鼠尾草以其独特的蓝紫色花序和长而细密的叶片为特点&#xff0c;常用于花坛、庭院和药用植物栽培。 鼠尾草的名字源自于…