哈希表实现

哈希概念

哈希(hash)又称散列,是一种组织数据的方式。从译名来看,有散乱排列的意思。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系,查找时通过这个哈希函数计算出 Key 存储的位置,进行快速查找。

直接定址法

当关键字的范围比较集中时,直接定址法就是非常简单高效的方 法,比如一组关键字都在 [0,99] 之间,那么我们开一个 100 个数的数组,每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a,z] 的小写字母,那么我们开一个 26 个数的数组,每个关键字 ASCII 码 - 'a' ASCII 码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们在计数排序部分已经用过了

直接定址法的缺点也非常明显

当关键字的范围比较分散时,就很浪费内存甚至内存不够用。假设我们只有数据范围是 [0, 9999] 的 N 个值,我们要映射到一个 M 个空间的数组中(一般情况下 M >= N),那么就要借助哈希函数 (hash function) hf,关键字 key 被放到数组的 h(key) 位置,这里要注意的是 h(key) 计算出的值必须在 [0, M) 之间。

这里存在一个问题就是,两个不同的 key 可能会映射到同一个位置去,这种问题我们叫做哈希冲突,或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突,但是实际场景中,冲突是不可避免的,所以我们尽可能设计出优秀的哈希函数,减少冲突的次数,同时也要去设计出解决冲突的方案。

负载因子

假设哈希表中已经映射存储了 N 个值,哈希表的大小为 M,那么负载因子 α=N/M,负载因子有些地方也翻译为载荷因子/装载因子等,它的英文为 load factor。负载因子越大,哈希冲突的概率越高,空间利用率越高;负载因子越小,哈希冲突的概率越低,空间利用率越低。

将关键字转为整数

我们将关键字映射到数组中位置,一般是整数好做映射计算,如果不是整数,我们要想办法转换成整数,这个细节我们在后面代码实现中再进行细节展示。

哈希函数

一个好的哈希函数应该让 N 个关键字被等概率地均匀地散列分布到哈希表的 M 个空间中,但是在实际中却很难做到,但是我们要尽量往这个方向去考量设计。

除法散列法/除留余数法

• 除法散列法也叫做除留余数法,顾名思义,假设哈希表的大小为 M,那么通过 key 除以 M 的余数作为映射位置的下标,也就是哈希函数为:h(key) = key % M。

• 当使用除法散列法时,要尽量避免 M 为某些值,如 2 的幂,10 的幂等。如果是 2^x ,那么 key % 2^x 本质相当于保留 key 的后 X 位,那么后 X 位相同的值,计算出的哈希值都是一样的,就冲突了。例如:

  • {63, 31} 看起来没有关联的值,如果 M 是 16 (2424),那么计算出的哈希值都是 15,因为 63 的二进制后 8 位是 00111111,31 的二进制后 8 位是 00011111

 乘法散列法

• 乘法散列法对哈希表大小 M 没有要求,它的大思路第一步:用关键字 K 乘上常数 A (0 < A < 1),并提取出 k*A 的小数部分。第二步:后再用 M 乘以 kA 的小数部分,再向下取整。

h(key)=floor(M×((A×key)%1.0))h(key)=floor(M×((A×key)%1.0)),其中 floor 表示对表达式进行下取整,A∈(0,1)A∈(0,1),这里最重要的是 A 的值应该如何设定,Knuth 认为 A=5−12=0.6180339887...A=25​−1​=0.6180339887... (黄金分割点)比较好

• 例如,假设 M 为 1024,key 为 1234,A=0.6180339887A=0.6180339887,A×key=762.6539420558A×key=762.6539420558,取小数部分为 0.6539420558,M×((A×key)%1.0)=0.6539420558×1024=669.6366651392M×((A×key)%1.0)=0.6539420558×1024=669.6366651392,那么 h(1234)=669h(1234)=669。

全域散列法

• 如果存在一个恶意的对手,他针对我们提供的散列函数,特意构造出一个发生严重冲突的数据集,比如,让所有关键字全部落入同一个位置中。这种情况是可以存在的,只要散列函数是公开且确定的,就可以实现此攻击。解决方法自然是见招拆招,给散列函数增加随机性,攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。

• h(key)=((a×key+b)%P)%M,P 需要选一个足够大的质数,a 可以随机选 [1, P-1] 之间的任意整数,b 可以随机选 [0, P-1] 之间的任意整数,这些函数构成了一个 P*(P-1) 组全域散列函数组。 假设 P=17,M=6,a=3,b=4,则 h34(8)=((3×8+4)%17)%6=5h34​(8)=((3×8+4)%17)%6=5。

需要注意的是每次初始化哈希表时,随机选取全域散列函数组中的一个散列函数使用,后续增删查改都固定使用这个散列函数,否则每次哈希都是随机选一个散列函数,那么插入是一个散列函数,查找又是另一个散列函数,就会导致找不到插入的 key 了。

其他方法

• 上面的几种方法是《算法导论》书籍中讲解的方法。

• 《殷人昆 数据结构:用面向对象方法与 C++ 语⾔描述(第二版)》和《[数据结构(C 语言版)]. 严蔚敏_吴伟民》等教材型书籍上面还给出了平方取中法、折叠法、随机数法、数学分析法等,这些方法相对更适用于一些局限的特定场景,有兴趣可以去看看这些书籍。

处理哈希冲突

实践中哈希表一般还是选择除法散列法作为哈希函数,当然哈希表无论选择什么哈希函数也避免不了冲突,那么插入数据时,如何解决冲突呢?主要有两种方法,开放定址法和链地址法。

开放定址法

在开放定址法中所有的元素都放到哈希表里,当一个关键字 key 用哈希函数计算出的位置冲突了,则按照某种规则找到一个没有存储数据的位置进行存储,开放定址法中负载因子一定是小于 1 的。这里的规则有三种:线性探测、二次探测、双重探测。

线性探测

从发生冲突的位置开始,依次线性向后探测,直到寻找到下一个没有存储数据的位置为止,如果走到哈希表尾,则回绕到哈希表头的位置。

• h(key)=hash0=key%M,如果 hash0位置冲突了,则线性探测公式为: hc(key,i)=hashi=(hash0+i)%M,i=1,2,3,...,M−1i=1,2,3,...,M−1 • 因为负载因子小于 1,则最多探测 M-1 次,一定能找到一个存储 key 的位置。

• 线性探测比较简单且容易实现,线性探测的问题是,假设 hash0hash0 位置连续冲突,hash0,hash1,hash2 位置已经存储数据了,后续映射到 hash0,hash1,hash2,hash3 的值都会争夺 hash3hash3 位置,这种现象叫做群集/堆积下面的二次探测可以在一定程度上改善这个问题

示例演示

考虑一组值 {19, 30, 5, 36, 13, 20, 21, 12} 映射到 M=11 的表中。

 二次探测

从发生冲突的位置开始,依次左右按二次方跳跃式探测,直到寻找到下一个没有存储数据的位置为止,如果往右走到哈希表尾,则回绕到哈希表头的位置;如果往左走到哈希表头,则回绕到哈希表尾的位置;

h(key) = hash0 = key % M, hash0位置冲突了,则二次探测公式为:
hc(key, i) = hashi = (hash0 ± i^2) % M,  i = {1, 2, 3, ..., M/2}

二次探测当 hashi = (hash0 - i^2) % M 时,当hashi<0时,需要hashi += M

下面演示 {19,30,52,63,11,22} 等这⼀组值映射到M=11的表中。

双重散列

第一个哈希函数计算出的值发生冲突,使用第二个哈希函数计算出一个跟key相关的偏移量值,不断往后探测,直到寻找到下一个没有存储数据的位置为止。

• h₁(key) = hash0 = key % M,hash0位置冲突了,则双重探测公式为:
  hc(key, i) = hashi = (hash0 + i * h₂(key)) % M,i = {1, 2, 3, ..., M}

• 要求 h₂(key) < M 且 h₂(key) 和 M 互为质数,有两种简单的取值方法:
  1. 当 M 为 2 的整数幂时,h₂(key) 从 [0, M-1] 任选一个奇数;
  2. 当 M 为质数时,h₂(key) = key % (M - 1) + 1

• 保证 h₂(key) 与 M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群,若最大公约数 p = gcd(M, h₁(key)) > 1,那么所能寻址的位置的个数为 M/P < M,使得对于一个关键字来说无法充分利用整个散列表。举例来说,若初始探查位置为 1,偏移量为 3,整个散列表大小为 12,那么所能寻址的位置为 {1, 4, 7, 10},寻址个数为 12/gcd(12, 3) = 4

下面演示 {19,30,52} 等这⼀组值映射到M=11的表中,设h2 (key)  =  key%10 + 1 

开放定址法代码实现

哈希结构

enum State
{EXIST,EMPTY,DELETE
};template<class K,class V>
struct hashdate
{pair<K, V> _kv;State sta = EMPTY;
};

要注意的是这里需要给每个存储值的位置加⼀个状态标识,否则删除⼀些值以后,会影响后面冲突的值的查找。如下图,我们删除30,会导致查找20失败,当我们给每个位置加⼀个状态标识 {EXIST,EMPTY,DELETE} ,删除30就可以不用删除值,而是把状态改为 DELETE ,那么查找20 时是遇到 EMPTY 才能,就可以找到20。

key不能取模的问题 

template<class K>
struct hashfunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct hashfunc<string>
{size_t operator()(const string& s){size_t hash0 = 0;for(auto e : s){hash0 += e;hash0 *= 131;}return hash0;}
};

当 key 是 string/Date 等类型时,key 不能取模,那么我们需要给 HashTable 增加一个仿函数,这个仿函数支持把 key 转换成为一个可以取模的整形,如果 key 可以转换为整形并且不容易冲突,那么这个仿函数就用默认参数即可,如果这个 Key 不能转换为整形,我们就需要自己实现一个仿函数传给这个参数,实现这个仿函数的要求就是尽量 key 的每值都参与到计算中,让不同的 key 转换成的整形值不同。string 做哈希表的 key 非常常见,所以我们可以考虑把 string 特化一下。 

整体结构

enum State
{EXIST,EMPTY,DELETE
};template<class K,class V>
struct hashdate
{pair<K, V> _kv;State sta = EMPTY;
};template<class K>
struct hashfunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct hashfunc<string>
{size_t operator()(const string& s){size_t hash0 = 0;for(auto e : s){hash0 += e;hash0 *= 131;}return hash0;}
};namespace hyx
{template<class K, class V, class hashf = hashfunc<K>>class hash{public:hash():_data(__stl_next_prime(0))//数组初始化的时候会根据传的值来初始化容量的大小, _n(0)//数据个数{}typedef hashdate<K, V> node;inline unsigned long __stl_next_prime(unsigned long n)//用来更新数组容量的大小{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}bool insert(const pair<K, V>& data)//插入{if (find(data.first)){return false;}if (_n * 10 / _data.size() >= 7)//负载因子>0.7需要扩容{hash<K, V,hashf> newhash;newhash._data.resize(__stl_next_prime(_data.size() + 1));//找到比原来数组更大的素数容量for (auto& da : _data)//将旧数组的数据存入新数组{if (da.sta == EXIST)//重新插入,如果倒入的数据的状态为插入的话就要在新数组中插入{newhash.insert(da._kv);}}_data.swap(newhash._data);//插入完毕后交换数组即可}//线性探测插入hashf func;int hash0 = func(data.first) % _data.size();int i = 1;while (_data[hash0].sta == EXIST){hash0 = (hash0 + i) % _data.size();i++;}_data[hash0]._kv = data;_data[hash0].sta = EXIST;_n++;return true;}hashdate<K, V>* find(const K& key){hashf func;int hash0 = func(key) % _data.size();int i = 1;while (_data[hash0].sta != EMPTY){if (_data[hash0]._kv.first == key&& _data[hash0].sta == EXIST) return &_data[hash0];hash0 = (hash0 + i) % _data.size();i++;}return nullptr;}bool erase(const K& key){node* data = find(key);if (data){data->sta = DELETE;_n--;return true;}else{return false;}}private:vector<hashdate<K, V>> _data;size_t _n;};
}

链地址法

解决冲突的思路
开放定址法中所有的元素都放到哈希表里,链地址法中所有的数据不再直接存储在哈希表中,哈希表中存储⼀个指针,没有数据映射这个位置时,这个指针为空,有多个数据映射到这个位置时,我们把这些冲突的数据链接成⼀个链表,挂在哈希表这个位置下面,链地址法也叫做拉链法或者哈希桶。

下面演示 {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M=11的表中。

扩容 


开放定址法负载因子必须小于1,链地址法的负载因子就没有限制了,可以大于1。负载因子越大,哈希冲突的概率越高,空间利用率越高;负载因子越小,哈希冲突的概率越低,空间利用率越低;STL中unordered_xxx的最大负载因子基本控制在1,大于1就扩容,我们下面实现也使用这种方式。 

namespace hyx
{template<class K, class V>struct hashnode{pair<K, V> _kv;hashnode* next;hashnode(const pair<K, V> kv):_kv(kv), next(nullptr){}};inline unsigned long __stl_next_prime(unsigned long n)//用来更新数组容量的大小{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}template<class K,class V>class hash{public:typedef hashnode<K, V> node;hash():_root(__stl_next_prime(0)),_n(0){}bool insert(const pair<K, V> kv){if (_n == _root.size())//负载因子=1需要扩容{vector<node*> newhash(__stl_next_prime(_root.size() + 1));for (size_t i = 0; i < _root.size(); i++){node* cur = _root[i];while (cur)//扩容的时候不创建新节点,而是将旧结点的指针移走,提高了效率{int hash0 = cur->_kv.first % newhash.size();cur->next = newhash[hash0];newhash[hash0] = cur;cur = cur->next;}_root[i] = nullptr;//移除完毕之后将旧表的结点设成空}_root.swap(newhash);}int hash0 = kv.first % _root.size();node* cur = new node(kv);cur->next = _root[hash0];_root[hash0] = cur;_n++;return true;}node* find(const pair<K, V> kv){int hash0 = kv.first % _root.size();node* cur = _root[hash0];while (cur){if (cur->_kv == kv) return cur;cur = cur->next;}return nullptr;}bool earse(const pair<K, V> kv){int hash0 = kv.first % _root.size();node* prev = nullptr;node* cur = _root[hash0];while (cur){if (cur->_kv == kv){if (prev == nullptr)//删除的是头结点{_root[hash0] = nullptr;}else//非头节点{prev->next = cur->next;}delete cur;_n--;return true;}else//还未找到{prev = cur;cur = cur->next;}}return false;}private:                                              vector<node*> _root;size_t _n;};
}

 

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

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

相关文章

CSS学习记录08

CSS文本颜色 文本颜色 color属性用于设置文本的颜色&#xff0c;颜色由以下值指定&#xff1a; 颜色名-比如“red"十六进制值-比如”#ff0000"RGB值-比如&#xff1a;“rgb&#xff08;255,0,0)”等。 页面的默认文本颜色在body选择器中定义的。 body {color: bl…

电子商务人工智能指南 6/6 - 人工智能生成的产品图像

介绍 81% 的零售业高管表示&#xff0c; AI 至少在其组织中发挥了中等至完全的作用。然而&#xff0c;78% 的受访零售业高管表示&#xff0c;很难跟上不断发展的 AI 格局。 近年来&#xff0c;电子商务团队加快了适应新客户偏好和创造卓越数字购物体验的需求。采用 AI 不再是一…

R155 VTA 认证对汽车入侵检测系统(IDS)合规要求

续接上集“浅谈汽车网络安全车辆型式认证&#xff08;VTA&#xff09;的现状和未来发展”&#xff0c;有许多读者小伙伴有联系笔者来确认相关的R155 VTA网络安全审核要求&#xff0c;基于此&#xff0c;笔者将针对 R155 VTA 每一条网络安全审核细则来具体展开。 今天就先从汽车…

利用Java爬虫按关键字搜索淘宝商品

在当今数字化时代&#xff0c;获取和分析电子商务平台上的商品数据对于市场研究者、数据分析师或个人买家而言是一项非常有用的能力。本文将详细介绍如何利用Java爬虫技术按关键字搜索淘宝商品&#xff0c;并提供相应的代码示例。 1. 爬虫技术简介 爬虫&#xff08;Web Crawle…

数据结构——B-树

目录 一.常见的搜索结构 二.B-树概念 三.B-树的插入分析及实现 1.插入分析 2.插入实现 1. B-树的节点设计 2.插入key的过程 3.B-树的插入实现 4.B-树的验证 5.B-树的性能分析 四.B树和B*树 1.B树 2.B*树 3.总结 五.B-树的应用 1.索引 2.MySQL索引简介 1.MyIS…

【vue2】封装自定义的日历组件(二)之基础添加返回到今天的功能

在上次封装的日历组件的基础上&#xff0c;我们完善下&#xff0c;在月份变化后&#xff0c;返回到当前月份的的当天日期的显示。 效果展示 代码逻辑 高亮的UI样式美化 .calendar-day {color: #d7d7d7;width: 100px;line-height: 80px;text-align: center;box-sizing: borde…

连续大涨,汉王科技跑步进入AI应用舒适区

OpenAI正在进行的“12天12场直播”让行业再次沸腾&#xff0c;二级市场也在寻找AI应用的机会。这刺激了12月首周同花顺sora概念涨超11&#xff05;&#xff0c;远超同期大盘指数涨幅。 截至目前&#xff0c;“满血版”推理模型o1和月收费高达200美元的ChatGPT Pro订阅服务&…

沃丰科技智能客服在跨境电商独立站中的核心角色

随着全球化进程的加速和互联网技术的不断发展&#xff0c;跨境电商行业蓬勃兴起&#xff0c;为消费者提供了更广阔、更便捷的购物选择。在这样一个竞争激烈的市场环境中&#xff0c;优质的客户服务成为了企业脱颖而出的关键。沃丰科技智能客服凭借其先进的技术和人性化的设计理…

智创 AI 新视界 -- AIGC 重塑广告行业的创新力量(16 - 7)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

入门级捡垃圾工作站记录

入门级捡垃圾工作站记录 想法 一直想着拥有有一台自己的多功能机子&#xff0c;一个笔记本很难事事包办&#xff0c;本来打算配一个台式机&#xff0c;后来研究了一下&#xff0c;索性捡垃圾拼装的工作站&#xff0c;性价比更高&#xff0c;稳定性也更强&#xff0c;而且还可…

SpringBoot【三】多环境切换,实例演示

一、前言 实际的项目开发中&#xff0c;一个项目通常会存在多个环境&#xff0c;例如&#xff0c;开发环境、测试环境和生产环境等。不同环境的配置也不尽相同&#xff0c;例如开发环境使用的是开发数据库&#xff0c;测试环境使用的是测试数据库&#xff0c;而生产环境使用的是…

Node.js创建Express项目安装express-generator报错

一、在我进行Node.js项目开发时&#xff0c;使用Express框架构建一个Express项目&#xff0c;时报错&#xff1a; npm warn deprecated mkdirp0.5.1: Legacy versions of mkdirp are no longer supported. Please update to mkdirp 1.x. (Note that the API surface has change…

在 .NET 9 中让您的 OpenAPI(Swagger)文档 UI 变得出色

从 .NET 9 开始&#xff0c;默认模板中不再包含 Swagger UI webapi。虽然文档仍然包含在内&#xff0c;但现在通过调用MapOpenApi&#xff0c;UI 不再存在。很高兴&#xff0c;重新获得文档 UI 相对容易。但 UI 本来就很无聊&#xff0c;所以让我们来点更花哨的东西吧&#xff…

使用Kimi开发自己的问答应用

概述 Kimi是大家常用的一个人工智能助手&#xff0c;本文使用Kimi开发文档&#xff0c;以node作为后端&#xff0c;开发与一个问答系统 实现效果 Kimi简介 Kimi是由Moonshot AI开发的人工智能助手&#xff0c;擅长中文和英文对话。目标是帮助用户解决问题、提供信息和执行任…

2024.12.09标准IO(作业)

1、使用这fscanf和fprintf两个函数实现文件的拷贝。 #include <myhead.h>int main(int argc, const char *argv[]) {//使用这fscanf和fprintf两个函数实现文件的拷贝FILE *fp1 fopen("./1.txt","r"); //打开被拷贝的文件1.txtif(NULL fp1){perror…

JK软考小程序上线啦

经过一段时间的题库整理和录入&#xff0c;JK软考小程序终于和大家见面了&#xff01; 扫描识别赶紧体验吧&#xff1a; JK软考是一款专门为准备软考的考生设计的移动学习工具。JK软考集成了丰富的软考题目资源&#xff0c;通过便捷的操作界面和多样化的功能&#xff0c;帮助考…

40分钟学 Go 语言高并发:负载均衡与服务治理

负载均衡与服务治理 一、知识要点总览 模块核心内容技术实现难度负载策略轮询、权重、最小连接数自定义负载均衡器中服务降级服务降级、熔断降级、限流降级Hystrix模式高熔断机制熔断器状态机、失败计数、自动恢复Circuit Breaker高限流设计令牌桶、滑动窗口、计数器Rate Lim…

LLMs之Agent之Lares:Lares的简介、安装和使用方法、案例应用之详细攻略

LLMs之Agent之Lares&#xff1a;Lares的简介、安装和使用方法、案例应用之详细攻略 导读&#xff1a;这篇博文介绍了 Lares&#xff0c;一个由简单的 AI 代理驱动的智能家居助手模拟器&#xff0c;它展现出令人惊讶的解决问题能力。 >> 背景痛点&#xff1a;每天都有新的…

Halcon 轮廓检测常用算子、原理及应用场景

一、引言 在机器视觉领域&#xff0c;轮廓检测是一项关键技术&#xff0c;它能够提取物体的边缘信息&#xff0c;从而实现物体的定位、识别、测量等多种功能。Halcon 作为一款强大的机器视觉软件库&#xff0c;提供了丰富的轮廓检测算子。本文将详细介绍 Halcon 中轮廓检测的常…

11.23[大数据]

PRO1:LSTM模型预测输出都是同一个值&#xff1f; 画出来的图像就是一条横线 这个搜了搜&#xff0c;原因可能有很多&#xff0c;但感觉最主要的原因极可能是激活函数选择不当&#xff0c;以及层的搭建不合适 原模型是 REF https://zhuanlan.zhihu.com/p/654325094 https:/…