作为一个做过体育内容平台的创业者，之前踩过的数据服务坑现在想起来还头疼：用户在评论区刷 “你们数据比电视慢半分钟”，写深度分析时缺高阶数据只能自己手动统计，凌晨直播出问题找客服半天没人回。直到试了这家服务商，才明白 “专业” 不是口号 —— 今天结合我的实战经历，聊聊它怎么精准戳中体育行业的核心数据需求。 一、先看核心需求：数据 “全” 且 “快”，才是真刚需做体育产品绕不开两个灵魂拷问：我要的赛事能不能覆盖？数据更新能不能跟上节奏？这家的覆盖范围是真的超出预期 —— 不光足球、篮球这些主流项目配齐，排球、棒球、板球全包含，连羽毛球、乒乓球、斯诺克这种偏门项目，甚至 LOL、DOTA2 等电竞数据都能拿到。 单说足球，50 + 联赛从英超、西甲、欧冠这些顶流，到东南亚联赛、南美解放者杯这种小众赛事都有； 篮球更不用提，NBA、CBA、欧洲篮球联赛的每一项核心数据都没落下。我之前做越南足球联赛的专题内容，找了三家服务商都缺数据，这家直接能拉取实时战报，一下解了燃眉之急。 最惊艳的还是更新速度。我们做实时比分功能时专门测过：足球的进球、红黄牌、换人这些关键事件，延迟居然压在 500ms 以内；篮球的得分、助攻、篮板更夸张，延迟＜300ms—— 相当于裁判哨声刚落，后台数据就同步更新了，彻底摆脱了 “别人都在刷进球，我们 APP 还停留在上一回合” 的尴尬。 二、技术对接：小白能上手，专业党能深挖过去对接过某家数据 API，文档写得像天书，团队技术小哥折腾了半个月才勉强跑通。这家的 “双通道接入” 是真懂开发者的难处：REST API 专用于查赛程、历史数据这类非实时需求，HTTPS 加密防泄露这点很安心。最贴心的是文档 —— 附了 Postman 测试模板，复制粘贴就能跑通示例，我们团队刚毕业的实习生跟着步骤操作，10 分钟就调通了第一个赛程接口，小团队不用再为技术对接烧钱请专家；WebSocket 是实时场景的 “杀手锏”：比分变化、关键球触发时主动推送，不用像以前那样每秒轮询 API。实测下来每月流量直接省了 80%（之前轮询月账单要四千多，现在不到八百），而且自带自动重连机制 —— 上次欧冠决赛直播时服务器断了 3 秒，它自动恢复后没丢任何数据，稳定性比我们之前用的服务商强太多。简单总结：查历史数据用 API，做实时直播用 WebSocket，按需搭配就行，不用委屈自己迁就技术限制。 三、真正的差距：不止给数据，更懂 “用数据”这是它和普通服务商最本质的区别 —— 不是把数据堆给你就完事，而是懂你要怎么用这些数据。比如我们写战术分析文章时，需要球员热图、足球的 PPDA 防守强度、篮球的 PIE 球员影响力这些高阶数据，以前找的服务商要么没有，要么单买一项就要加钱；但这家不仅全包含，还支持 “定制字段”。我们曾想做 “中超球员边路突破成功率” 的专题，提需求后 3 天就做好了适配，文章发出去后阅读量涨了 30%，读者都说 “数据够细，比泛泛而谈的分析有用”。甚至连 “梅西式弧线球” 这种个性化统计，只要说清需求都能做，对内容创新太关键了。另外，可靠性和服务真的没话说：从数据采集、清洗到接口交付全是自主技术栈，不用依赖第三方，7×24 小时有人盯着系统，全年可用性能做到 99.9% 以上；有次凌晨 2 点做英超直播，接口突然报错，联系专属技术顾问后 15 分钟就接通了视频，直接远程协助排查问题，不是甩个文档让我们自己琢磨 —— 对比之前那家 “工作日才回复” 的服务商，这种响应速度在赛事直播这种 “不等人” 的场景里，简直是救命级的。 哪些人真的需要它？ 如果你是这几类从业者，建议重点考察：体育 APP / 网站开发者：实时比分、赛况动画离不开低延迟数据，用户对 “慢半拍” 的容忍度为零；媒体 / 解说团队：做数据可视化、战术板分析时，高阶数据能让内容更有说服力；体育科技公司：训练 AI 模型缺数据源？球员动线、战术分析这些稀缺数据刚好能用上。 最后说句实在话：选体育数据服务别光看 “低价”，要盯着 “能不能解决你的具体痛点”—— 是缺小众赛事数据？还是实时延迟太高？或是服务响应慢？这家在这几点上都踩在了行业需求的点子上，亲测靠谱。如果正在对比服务商，建议先问清三个问题：“我要的小众赛事能不能覆盖？WebSocket 稳定性有没有实测案例？定制需求多久能落地？” 这些比单纯比价重要多了，能帮你少走不少弯路。  欢迎交流！

1.位图给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中? 放在哈希表中去寻找？不，这并不现实，因为哈希表的存储也是需要空间消耗的，况且是 40 亿个数据，如此庞大的数据计算机一般是很难存储 因此就诞生了位图的概念，位图简单来说就是把每个数按照哈希函数的计算，存储到每个比特位上。数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为 1，代表存在，为 0 代表不存在   1.1 位图的结构template<size_t N>class bitset{public:bitset(){_a.resize(N / 32 + 1);}private:vector<int> _a;}; 开辟一个 vector 数组 _a，这里我们以 int 作为位图的基本单位，那么就是把每个数据存储到 int 的比特位上 🔥值得注意的是： resize 的时候无论如何都要加 1，比如 100 个数据，除以 32，等于 3，余 4，那么就需要多一个 int 空间来存储，不能说每次都卡好刚好 32 整除 1.2 位图映射的比特位标记成1// x映射的那个标记成1void set(size_t x){size_t i = x / 32;size_t j = x % 32; _a[i] |= (1 << j);} i 用于确定在第几个 int 里，j 用于确定在第几个 int 的第几位上   二进制位从右到左是最低位到最高位，所以左移即可 1.3 位图映射的比特位标记成0// x映射的那个标记成0void reset(size_t x){size_t i = x / 32;size_t j = x % 32; _a[i] &= (~(1 << j)); 同理，因为按位与是有 0 就是 0，直接计算即可   1.4 位图映射判断为1 or 0bool test(size_t x){size_t i = x / 32;size_t j = x % 32; return _a[i] & (1 << j);} 注意这里是 &，而不是 &=，因为只需要判断，而不是修改 位图通常不支持删除功能，因为没有必要删除 2.布隆过滤器  我们在存储字符串数据时，是通过计算这个字符串的ASC||码值之和，然后通过哈希函数计算存入的，但是这可能会产生哈希冲突，但是数据量太大了，无法通过常规的方法解决 那么最简单的方法就是降低误判率，通过多个不同哈希函数计算，将一个值映射多个位置，这样不至于每次查找都会产生冲突 用哈希表存储用户记录，缺点：浪费空间用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了将哈希与位图结合，即布隆过滤器  再举个现实点的例子，就能理解布隆过滤器存在的必要：   比如我们在注册账号昵称时，会显示是否已经被取过，先在布隆过滤器中进行查找，若不在，那么成功注册；如果在，那么就到数据库中查询，这样能减少数据库查询次数，降低负载压力，提升整体查询效率 2.1 布隆过滤器的结构template<size_t N,    class K = string,    class Hash1 = BKDRHash,    class Hash2 = APHash,    class Hash3 = DJBHash>class BloomFilter{private:    bitset<N> _bs; Hash1、Hash2、Hash3 是用于计算 string 存储的哈希函数，stl 库里是有 bitset 使用的，直接开辟位图空间即可 传送门：字符串Hash函数对比 2.2 布隆过滤器的哈希函数struct BKDRHash{    size_t operator()(const string& str)    {        size_t hash = 0;        for (auto ch : str)        {            hash = hash * 131 + ch;        }         //cout <<"BKDRHash:" << hash << endl;        return hash;    }}; struct APHash{    size_t operator()(const string& str)    {        size_t hash = 0;        for (size_t i = 0; i < str.size(); i++)        {            size_t ch = str[i];            if ((i & 1) == 0)            {                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));            }            else            {                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));            }        }         //cout << "APHash:" << hash << endl;        return hash;    }}; struct DJBHash{    size_t operator()(const string& str)    {        size_t hash = 5381;        for (auto ch : str)        {            hash += (hash << 5) + ch;        }         //cout << "DJBHash:" << hash << endl;        return hash;    }}; 选取了三种计算冲突较小的哈希函数算法进行计算，因为需要多处使用，以仿函数的形式更加方便快捷 2.3 布隆过滤器的插入void Set(const K& key){    size_t hash1 = Hash1()(key) % N;    _bs.set(hash1);     size_t hash2 = Hash2()(key) % N;    _bs.set(hash2);     size_t hash3 = Hash3()(key) % N;    _bs.set(hash3);     /* cout << hash1 << endl;     cout << hash2 << endl;     cout << hash3 << endl << endl;*/} 由于是以仿函数的方式进行，Hash1() 是匿名对象，有了对象才能以函数的形式调用参数 2.4 布隆过滤器映射判断为true or falsebool Test(const K& key){    size_t hash1 = Hash1()(key) % N;    if (_bs.test(hash1) == false)        return false;     size_t hash2 = Hash2()(key) % N;    if (_bs.test(hash2) == false)        return false;     size_t hash3 = Hash3()(key) % N;    if (_bs.test(hash3) == false)        return false;     return true;} 2.5 布隆过滤器的优缺点🚩优点： 增加和查询元素的时间复杂度为: O(K), ( K 为哈希函数的个数，一般比较小)，与数据量大小无关哈希函数相互之间没有关系，方便硬件并行运算布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势数据量很大时，布隆过滤器可以表示全集，其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算🚩缺点： 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除，可能会存在计数回绕问题3.常见面试题3.1 哈希切割3.1.1 问题一给一个超过 100G 大小的 log file，log 中存着 IP 地址, 设计算法找到出现次数最多的 IP 地址？ 🛜解决方法： 对于超过 100G 的日志文件，直接加载到内存是不可行的，既然大的不行，就把文件分割为小文件一个个进行 使用哈希函数计算将 IP 映射到不同的小文件中，确保相同 IP 进入同一个文件，对每个小文件，使用哈希表统计 IP 频率，合并所有小文件的统计结果，就能找出出现次数最多的 IP 3.1.2 问题二与上题条件相同，如何找到 top K 的 IP ？ 🛜解决方法： 既然相同 IP 一定进入同一个小文件，用 map 去统计每个文件中 IP 出现的次数即可 3.2 位图应用3.2.1 问题一给定 100 亿个整数，设计算法找到只出现一次的整数？ 🛜解决方法： 对于 100 亿个整数（约 40GB 数据），直接加载到内存显然不可行。我们可以使用 位图 和 哈希分治 相结合的方法高效解决这个问题——双位图法  使用两个位图，每个整数对应两位： 00：整数未出现01：整数出现 1 次10：整数出现 2 次及以上假设计算出第一个数据映射第一个位置，且第一次出现，则上面的位图第一位设置为 0，下面位图的第一位设置为 1。其他情况依次类推 template<size_t N>class twobitset{public:void set(size_t x){// 00 -> 01if (!_bs1.test(x) && !_bs2.test(x)){_bs2.set(x);} // 01 -> 10else if (!_bs1.test(x) && _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}// 本身10代表出现2次及以上，就不变了} bool is_once(size_t x){return !_bs1.test(x) && _bs2.test(x);}private:bitset<N> _bs1;bitset<N> _bs2;}; 最后遍历位图对每一位进行 is_once 函数的判断，符合一次的存入哈希表即可 3.2.2 问题二给两个文件，分别有 100 亿个整数，我们只有 1G 内存，如何找到两个文件交集？ 🛜解决方法： 还是利用两个位图的方式解决，一个文件映射一个位图，对应的位置 & 按位与一下，两个位置都为 1，则这个位置是交集，注意存储的值应该放在 set 里去重 3.2.3 问题三1 个文件有 100 亿个 int，1G 内存，设计算法找到出现次数不超过 2 次的所有整数 🛜解决方法： 和问题一的方法是一样的，只不过改一下表示方法而已 00：整数未出现01：整数出现 1 次10：整数出现 2 次11：整数出现 3 次及以上3.3 布隆过滤器应用3.3.1 问题一给两个文件，分别有 100亿个 query，我们只有 1G 内存，如何找到两个文件交集？分别给出精确算法和近似算法 🛜解决方法： 近似算法： 用文件 A 的所有 query 构建布隆过滤器，遍历文件 B 的每个 query，判断是否可能在 A 中，对布隆过滤器返回 “可能存在” 的 query，再在文件 A 中精确验证，但是这种方法并不百分百准确，可能存在误判 精确算法：   将 A、B 文件都分割为同样数量的小文件，都上好编号，因为经过相同哈希函数计算，所以 A 和 B 中相同的 query 必定分别进入 Ai 和 Bi 文件中，因此 A0 和 B0 比较，A1 和 B1 进行比较，以此类推即可   3.3.2 问题二如何扩展 BloomFilter 使得它支持删除元素的操作? 🛜解决方法： 将标准布隆过滤器的每个二进制位扩展为一个小计数器（通常 4-8 位），当插入元素时增加计数器，删除时减少计数器。只有当计数器为 0 时，才表示该位置未被占用————————————————                             版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                        原文链接：https://blog.csdn.net/Zero_VPN/article/details/148150897

双向链表链表分类 8种 (带头/不带头 单向/双向 循环/循环)最常用两种 单链表(不带头单向不循环链表) 双向链表（带头双向循环链表） 双链表有 头节点（哨兵位） 后继指针(next) 前驱指针(prev) 双向链表为空时，为一个哨兵位 同样采用多文件操作   1.申请节点//申请节点LTNode* LTBuyNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL)//申请不成功{perror("malloc fail");exit(1);//给非0值}node->data = x;node->next = node->prev = node; return node;} 2.链表初始化void LTInit(LTNode** pphead){//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);//随便赋一个值}  3.尾插  以上图为例 尾插时 head->prev指向的就是d3 void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;//也就是newnode->prev指向d3newnode->next = phead; phead->prev->next = newnode;//d3的next指针指向新节点phead->prev = newnode;} 4.打印链表  让pcur指向phead的next指针，然后遍历链表，直到pcur=phead void LTPrint(LTNode* phead){LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");} 5.头插头插是插到头结点与d1之间，插在头结点前边跟尾插一样(因为链表是双向循环的)   void LTPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;  phead->next->prev = newnode;//先改影响小的phead->next = newnode; } 6.尾删  void LTPopBack(LTNode* phead){//链表必须有效且链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->prev;    del->prev->next = phead;phead->prev = del->prev; //删除del节点free(del);del = NULL; } 7.头删  void LTPopFront(LTNode* phead){assert(phead && phead->next != phead);LTNode* del = phead->next; phead->next = del->next;del->next->prev = phead; //删除del节点free(del);del = NULL;} 8.查找LTNode* LTFind(LTNode* phead, LTDataType x){LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;} 9.指定位置插入  10.删除pos节点  void LTErase(LTNode* pos)//这里传一级指针是为了保持接口的一致性 其他函数传的都是一级指针{//pos理论上来说不能为phead,但是参数没有phead，所以无法增加校验pos->next->prev = pos->prev;pos->prev->next = pos->next; free(pos);pos = NULL;} 11.链表的销毁  void LTDesTroy(LTNode* phead){assert(phead); LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;//如果不置为空 plist(保存的地址空间被释放掉了) 若后续不再使用plist则没问题(野指针) } 12.程序源码List.h #pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h> typedef int LTDataType;//定义双向链表节点的结构typedef struct ListNode{LTDataType data;struct ListNode* next;struct ListNode* prev; }LTNode; //声明双向链表种提供的方法 //初始化void LTInit(LTNode** pphead);void LTPrint(LTNode* phead);//插入数据之前，链表必须初始化到只有一个头结点的情况// 不改变哨兵位的地址，所以传一级指针即可//尾插void LTPushBack(LTNode* phead,LTDataType x);//头插void LTPushFront(LTNode* phead, LTDataType x); void LTPopBack(LTNode* phead);void LTPopFront(LTNode* phead);//在pos位置之后插入数据void LTInsert(LTNode* pos, LTDataType x);void LTErase(LTNode* pos);//查找LTNode* LTFind(LTNode* phead, LTDataType x); void LTDesTroy(LTNode* phead); #include"List.h"; void LTPrint(LTNode* phead){LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");} //申请节点LTNode* LTBuyNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(1);//给非0值}node->data = x;node->next = node->prev = node; return node;}void LTInit(LTNode** pphead){//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);}//尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead; phead->prev->next = newnode;//不能交换位置phead->prev = newnode;}//头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;  phead->next->prev = newnode;//先改影响小的phead->next = newnode; }//尾删void LTPopBack(LTNode* phead){//链表必须有效且链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev; //删除del节点free(del);del = NULL; }//头删void LTPopFront(LTNode* phead){assert(phead && phead->next != phead);LTNode* del = phead->next; phead->next = del->next;del->next->prev = phead; //删除del节点free(del);del = NULL;}//查找LTNode* LTFind(LTNode* phead, LTDataType x){LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;}//指定位置插入数据void LTInsert(LTNode* pos, LTDataType x){assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next;newnode->prev = pos; pos->next->prev = newnode;pos->next = newnode; }//删除pos节点void LTErase(LTNode* pos)//这里传一级指针是为了保持接口的一致性 其他函数传的都是一级指针{//pos理论上来说不能为phead,但是参数没有phead，所以无法增加校验pos->next->prev = pos->prev;pos->prev->next = pos->next; free(pos);pos = NULL;}//链表销毁void LTDesTroy(LTNode* phead){assert(phead); LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;//如果不置为空 plist(保存的地址空间被释放掉了) 若后续不再使用plist则没问题(野指针) }//LTErase和LTDestroy参数理论上要传二级，因为我们需要让形参的改变影响到实参，但是为了接口的一致性才穿的一级//传一级存在的问题是，当形参phead置为NULL后，实参plist不会被修改为NULL,因此解决方法是 调用完方法后手动将实参置为NULL  #define _CRT_SECURE_NO_WARNINGS#include"List.h"; void ListTest01(){LTNode* plist = NULL;LTInit(&plist); LTPushBack(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPushFront(plist, 3); LTPrint(plist);LTNode* find = LTFind(plist, 3);{if (find == NULL){printf("找不到\n");}else{printf("找到了\n");}}LTInsert(find, 66);LTPrint(plist);LTErase(find);LTPrint(plist); }int main(){ListTest01();return 0;}AI写代码c运行 ————————————————                             版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                        原文链接：https://blog.csdn.net/czx_163/article/details/149162828

一、什么是哈希表？什么是哈希表？ 哈希表，顾名思义，就是一个表。 可是为什么叫哈希表？ 因为这是从老美那里音译过来的 叫做->Hash Table 翻译过来就是->哈希表 既然是表，那么 第一，哈希表长什么样子？ 第二，为什么会有哈希表？ 第三，哈希表用来做什么？ 第三，哈希表的特点是什么？ 第四，什么是取余法？ 第五，什么是映射？ 第六，什么是线性探测？ 第七，什么是哈希桶？ 以上相关常见的概念，要怎么理解？是什么？为什么？怎么办？ 下面我来一一解析。 1.1哈希表长什么样？一般哈希表有两种形式（先别问为什么，先看，后面解释）     1.2为什么会有哈希表？假设你有一个数组或者链表， 传统的数组访问某一个数据，或者链表访问某一个数据，必须遍历，也只有遍历。 假如你的数组长度为100万，你现在要取某个值，而你已经知道这个值在就在数组的中间。 怎么办？ 此时，无论从前往后，还是从后往前遍历，都绕不过50万个值。 蛋不蛋疼？蛋疼。 难受不难受？难受。 如果数据规模更大，例如100亿，那更难受。 所以，有困难，有麻烦，就会引发思考：我能不能不用遍历，咔的一下，马上就找到这个值？ 显然传统的数据结构无法突破这个难题。 既然旧的不行，干脆，那就搞一个新的。 于是，天空一声巨响，哈希表闪亮登场！ 所以，哈希表就是为了解决查找必须遍历的问题而生。 1.3哈希表的特点如何做到不遍历直接访问到数据？ 很简单，非常简单，简单到不能再简单。 举个例子，你有5个值：1， 2， 3， 4 ，10001 我在创建数组的时候，我直接申请10001个空间！ 然后所有的数据直接存储在对应的下标位置。 (啊？？？) 现在你给我一个值，例如说10001。 要我去表里找，此时我不去遍历。 我直接就到数组下标为10001的位置取数据。 因为数组是支持随机访问的。 什么叫做数组随机访问？-CSDN博客（找了半天，关于数组随机访问的博客没有一个满意的，所以我自己写了一个。仅供参考。） 我直接初始位置+10001，直接就拿到数据了。 有毛病没有？没有。 有问题没有？没有。 你会说，是不是太浪费空间了？ 是的，非常浪费。 但是，你就说我遍历了没有？没有。 你就说找到了没有？找到了。 你就说快不快吧？快，非常快，O(1)的速度。 所以，解决我们原来要遍历的困扰没有？解决了。 但是，你会发现不对劲，空间太浪费了啊。 假设我有只有2个数据，一个是1，另一个是1000000000000000。 (嗯......?!) 难道我要建立那么大的空间，就为了存这俩货？ 不行，很cuo，非常cuo，cuo的一批。 那么，怎么办？ 于是，取余法就来了。 1.3.1 取余法、线性探测现在，我们回到文章开始的地方，哈希表的模样，其中一种是这样的：   为什么是这样的？ 下面我们来解释： 假如，我们有以下数据：2，18，22，89，1000000000001 按照原来的办法，我们需要开辟10000000000001个空间，才能构成哈希表 即数据存储在对应位置 但是，这种方式不行，太浪费空间。 怎么办？取余法。 什么是取余法？ 很简单，就是取余数。 例如，我们现在有5个数据，那么我们就开10个空间 然后，让这每一个数据%10，得到结果 再将这个结果放到对应的位置。 什么意思？ 很简单，现在有6个数据：2，18，22，23，89，1000000000001 2%10 = 2，所以2存放在下标为2的位置   18%10 = 8，所以18存放在下标为8的位置   22%10 = 2，所以22存放在下标为2的位置 但是，现在下标为2的位置已经有了一个值 这个情况，就是所谓的哈希冲突！非常简单，非常好理解对不对？ 是的，就是这么简单。不要被一些看似很牛b的概念给困住了。 所有的概念都只不过是为了更好的概括和综合某个现象，方便于你理解，仅此而已。 学习新事物，也是如此。 好的，那么，这个位置冲突了，怎么办？ 那就放到后面没有冲突的位置。 下标为3的位置没有冲突，所以，放到3   23%10 = 3，所以23存放在下标为3的位置 但是，同样的，下标为3的位置已经有数据了。 即所谓哈希冲突了。 怎么办？ 很简单，同样的道理，往后挪 挪到没有冲突的位置。 所以，往后下标4的位置没有数据，所以23存在下标为4的位置   89%10 = 9，所以89存放在下标为9的位置   1000000000001%10 = 1，所以1000000000001存放在下标为1的位置   于是，这6个数据，即使有数据为1000000000001那么大的值， 我们也仅仅用了10个空间就存储下来了。 那么，如何取出数据呢？ 同样的，很简单，例如取18，将18%10=8，然后到下标为8的位置取即可。 但是，22呢？22%10=2，但是22却不在下标为2的位置。 怎么办？ 往后找。 23呢？也不在下标为3的位置。 怎么办？ 还是往后找。 如果当前位置找不到值，就往后挨个查找，直到找到。 往后找，就像是探测，而且是一个一个探测，是线性的查找。 这就是所谓线性探测！ 所以，我们把这个表，就叫做线性探测表 非常简单！有手就行。 1.3.2 映射同时，你会发现： 22并不是存在下标为22的位置，而是存在下标为2的位置 1000000001也不是存在下标为1000000001的位置，而是存在下标为1的位置 这就是所谓映射！ 即，值与值之间的关联，一种关系。 22和下标为2的位置的映射关系。 1000000001和下标为1的位置的映射关系。 还可以这么理解： 你名字叫做张三，你的女朋友叫做李四。 别人叫张三，叫的是你，而不是你女朋友。 这就是映射，张三映射你，李四映射你女朋友。 这就是一对一映射。 同时，还会有这一种情况： 你遇到了一个人，她名字也叫做张三！ 现在，有人叫张三的名字，但是张三有两个人。 所以，张三映射对应两个人。 甚至，同一个名字的人会有很多很多，例如说张伟这个名字，直接顶一个县城。   这，就是一对多的映射。 1.3.3负载因子取余法，解决数据存放空间太大的问题 好了，现在我们已经解决了空间太大的问题。 但是，问题又来了。 什么问题？ 例如，假设我们的数据老是冲突，怎么办？ 这个时候的访问，就会偏离我们初始的目的，即不遍历 因为访问一个数据，老是要往后遍历，很麻烦 随着数据的增多，冲突的概率增加，查找的成本越来越高。 也就是说，问题源于数据太多，而空间不够 怎么办？ 很简单，扩容。 那么，我们应该什么时候扩容呢？ 很简单，用负载因子判断。 好，什么是负载因子？ 负载因子就是数据个数所占整个空间的比率。 例如 10个空间，有2个数据 负载因子就是0.2 10个空间，有7个数据 负载因子就是0.7 所以，每插入一个位置，我们就让负载因子+1 而一般来说，负载因子达到0.7就要进行扩容。 1.4哈希桶回到文章开始，我们说哈希表一般有两种形式， 一个叫做线性探测表，前面已经解释清楚。 另一个，叫做哈希桶。 长这个样子：   我们已经知道哈希桶长什么样子，下面我们来解释： 为什么要有哈希桶？ 假如我有一组数据。 这一组数据是：2，22，222，2222，22222，222222，2222222，22222222........ 好的，数据我给你了。 你存吧。 你想要怎么存？ 如果按照线性探测表的方式进行存储： 好家伙，你一看数据，你发现 取余数，结果全是2 存一个冲突一个 存两个冲突两个 存三个冲突三个 ..... 从头冲突到尾，没完没了。 怎么办？ 很明显，线性探测形式的哈希表有着致命的弱点 即无法对余数相同的数据进行处理 冲突了，只有往后放 我的位置冲突了，我就去放别人的位置，让别人冲突 （没错，就是这么强大，你打我啊） 如此一来，当数据越来越多时，哈希冲突的概率将会越来越大 哈希冲突多了，就会导致查找的成本越来越高 哈希表的优势也会越来越微弱 怎么办？ 于是，哈希桶来了。 我这么存：   我现在无论是存12，22，32，42，52还是222222222222 还会和其他位置冲突吗？ 不会。 哈希桶将冲突的值，放到同一个位置下，用单链表管理起来 哈希桶的结构，极大的优化了线性探测表无法处理哈希冲突的缺点 同时，单链表的访问，其时间复杂度也控制在O(n)的量级。 非常棒。 哈希桶也存在负载因子的问题， 和线性探测负载因子是一样的逻辑 同样，也是大于0.7就进行扩容 扩容是对数组的扩容 而扩容之后，单链表的长度也会变短 为什么？ 例如空间从10变为100 原来2，12，22，32，42，52，62，72，82，92等值都只能挂在下标2的位置 但是当空间变为100 瞬间，所有的值都有了自己对应的下标位置 原本长度为10的哈希桶，直接变为1   优化效果相当棒 这，就是哈希桶 同学，都看到这了，顺手给咱点个赞吧~    1.5闲散列与开散列1、闲散列：开放定址法（线性探测/二次探测） 二次检测：当数据比较集中的时候，查找会比较慢， 为了更快的查找，下一个位置查找偏移量不为1，可以为2次方 思路：我的位置被别人占了，我就去占别人得位置 冲突越多，效率越低 因此，有人提出了开散列 2、开散列：哈希桶/拉链法 1.6总结综上，我们来总结一下： 1、值很分散，因此哈希表也叫做散列表 2、有些值不好映射，比如string，结构体等 3、开空间问题，即哈希冲突 4、哈希表是用哈希思想实现的一种数据结构 hash更多的来说，是一种思想 例如编码表也是一种哈希编码的运用 例如经典的ASCII码表 同时，有时候你会发现你打开某些文件，会出现乱码 为什么？ 因为码表对错了，原本这个文件要拿表A来映射 结果拿成表B来映射了 所以结果就是乱码 乱码的本质是编码表对乱了 以上就是关于哈希表的基础概念和知识。 下面博主要带大家设计出一个简易版哈希表 即unordered_set和unordered_map 使用c++实现，总体还是比较难的 涉及模板、多层嵌套封装、泛型编程、内外部类、友元等 需要有一定的c++基础。 其实简单理解就够了，不必跟着我写出一个。 二、设计hash表1、哈希表的设计  1）插入如果位置不被占，插入；如果位置被占，遇到空才插入       插入逻辑： 先是数据%size，为什么是size而不是capacity呢？ 因为capacity后面的的值是没法访问的，end位置是size前一个位置 然后找到空/被删除的位置，插入，n++ n是记录哈希表个数的值，为什么不用size呢？ 因为hash表是离散的表 如果hash表数值很多，就有很大的概论发生冲突 怎么办？ 设置一个负载因子，用来记录hash表内的数据个数的占比 一般是0.7~0.8 如果hash表满了呢？在找空/被删除位置时，就会出现死循环的问题 满了就扩容 扩容之后，原有的值不能拷贝，需要重新映射，新的hash表的size是原有空间的2倍 处理数据冗余：插入前利用find   2）查找遇到空才停止，但是如果中间位置有空位置，就查不到后面的位置，如何解决？ 设置一个位置状态：EMPTY、DELETE，EXIST  3）删除删除的值不必抹除，而是将状态设置为DELETE。 如果抹除，设置为什么值都不合适 因此，删除是一个伪删除，查找值时依旧能找到 在Find函数需要特殊判断，即存在才查找 如果数据不能取%怎么办？ 例如string数据类型 用仿函数进行解决 对于整型、浮点型、指针都进行size_t强转为整型，就可以取% 但是string不可以转化为整型 怎么办？ 单独写一个为string转换的仿函数 这个仿函数返回string【0】 4）字符串哈希算法把字符串转型为整型 将每一个字符的ASCII值*某个数值，累计加 最后每一个字符串的结果一般都不会重复，但是依旧会重复 string很常见，那可以对仿函数使用特化 什么是特化？就是对某些类进行特殊化处理 就是不适用模板推广，而是直接使用 2、封装map和set1、完成对hash表的基础功能一个哈希表要有的功能： 插入、删除、遍历（迭代器） 2、完成封装插入、删除、查找的接口封装 3、对应的迭代器        1）首先是一个迭代器对象，完成对象的简单框架         哈希表的迭代器，需要哈希表本身，以及哈希表对应位置的节点         其内部的哈希表，需要外部调用对象哈希表来初始化         2）++重载                 1、先算出当前所在位置                 2、当前位置的下一个位置不为空，那就是有直接返回                 3、当前位置为空，要继续找后面的位置 4、【】方括号重载返回值是一个pair，第一个参数是迭代器，第二个参数是bool，判断是否添加成功 如果已经存在，返回已存在节点的迭代器，以及false 如果节点不存在，返回新插入节点的迭代器，以及true 需要修改insert的返回值 以及find的返回值 这样就可以直接对find和insert进行复用 方括号重载返回值为value 三、设计原码1、HashTable#pragma once#include<iostream>#include<vector>using namespace std; //设计一个hash表//哈希表是一个vector数组//节点存储的是一个pair节点//使用模板编程 //如果插入的是string,就不能取%//怎么办？字符串哈希算法//使用仿函数 enum State{EXIST,DELETE,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& key){size_t ret = 0;for (auto ch : key){ret *= 131;ret += ch;}return ret;}};  namespace hash{//哈希表节点template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;}; //定义哈希表template<class K, class V, class  Hash = hashFunc<K>>class HashTable{public:typedef HashData<K, V> Node;HashTable(){_tables.resize(10);} //插入bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;} //检查扩容if (_n / _tables.size() >= 0.7){size_t newSize = _tables.size() * 2;  HashTable<K,V,Hash> newHashTable;  newHashTable._tables.resize(newSize); //重新插入新空间for (size_t i = 0; i < _tables.size(); ++i){newHashTable.Insert(_tables[i]._kv);}} //1、找到插入的位置，取%Hash hs; size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state != EMPTY){++hashi;} //3、插入,更新负载因子_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++; return true;} //查找Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST  &&_tables[hashi]._kv.first ==  key)  {return &_tables[hashi];} ++hashi;hashi %= _tables.size();} return nullptr;} size_t size(){return _n;} //删除bool Erase(const K& key){Node* cur = Find(key);if (cur){cur->_state = DELETE;--_n;return true;} return false;} private:vector<HashData<K, V>> _tables;size_t _n = 0; }; void HashTest(){HashTable<int, int> ht;ht.Insert({ 1,1 });ht.Insert({ 2,2 });ht.Insert({ 3,3 });ht.Insert({ 4,4 });ht.Insert({ 3,3 });ht.Insert({ 3,3 });cout << ht.Find(1) << endl;cout << ht.Find(2) << endl;cout << ht.Find(3) << endl;cout << ht.Find(4) << endl;cout << ht.size() << endl; ht.Erase(1);ht.Erase(2);cout << ht.size() << endl; } void HashTest1(){HashTable<string, int> ht;ht.Insert({ "abcd",1});ht.Insert({ "edasdfas",2});ht.Insert({ "kahkahdk",3});ht.Insert({ "ohjahsflhasf",4}); cout << ht.size() << endl;size_t ret = hashFunc<string>()("dasldfhalf");size_t ret1 = hashFunc<string>()("sad");cout << ret << endl;cout << ret1 << endl; }}  ////////////////////////////////////////////////////////    //哈希桶实现namespace hash_bucket{ //哈希节点，是一个链表template<class T>struct HashNode{T _data;HashNode* _next; HashNode(const T& data):_data(data), _next(nullptr){} }; ////前置声明//template<class K, class T, class Hash, class KeyOfT>//class HashTable; ////实现迭代器//template<class K, class T, class Hash, class KeyOfT>//struct __HSIterator//这个是给hash表底层使用的迭代器对象//{// typedef HashNode<T> Node;// typedef  HashTable<K, T, Hash, KeyOfT> Self; // HashTable<K, T, Hash, KeyOfT>* _pht;// Node* _node; // __HSIterator(const Node* node, const HashTable<K, T, Hash, KeyOfT>* pht)// :_pht(pht)// ,_node(node)// {// } // //++// Self& operator++()//返回结构体对象// {// KeyOfT kot;// Hash hs;// size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();// Node* cur = _pht->_tables[hashi];//// if (_node->_next)// {// _node = _node->_next;// }// else//该节点为空// {// while (hashi < _pht->_tables.size())// {// if (cur == nullptr)// {// ++hashi;// }// else// {// break;// }// } // if (hashi == _pht->_tables.size())// {// _node = nullptr;// }// else// {// _node = _pht->_tables[hashi];// }// }//// return *this; // } // //解引用*// T& operator*()// {// return _node->_data;// } // T* operator->()// {// return &_node->_data;// } // bool operator!=(const Self& s)// {// return _node != s._node;// } //}; //哈希表template<class K, class T, class Hash , class KeyOfT>class HashTable{public:////友元声明(但是这种方式的代码过于冗余)//template<class K, class T, class Hash, class KeyOfT>//friend struct __HSIterator;  //内部类template<class Ref, class Ptr>struct __HSIterator//这个是给hash表底层使用的迭代器对象{typedef HashNode<T> Node;typedef  __HSIterator Self; const HashTable* _pht;Node* _node; __HSIterator( Node* node, const HashTable* pht):_pht(pht), _node(node){} //++Self& operator++()//返回结构体对象{  if (_node->_next){_node = _node->_next;}else//该节点为空{KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size(); ++hashi;while (hashi < _pht->_tables.size()){if (_pht->_tables[hashi])break;++hashi; } if (hashi == _pht->_tables.size()){_node = nullptr;}else{_node = _pht->_tables[hashi];} } return *this; } //解引用*Ref operator*(){return _node->_data;} Ptr operator->(){return &_node->_data;} bool operator!=(const Self& s){return _node != s._node;} }; typedef __HSIterator<T&, T*> iterator; iterator begin(){//找到第一个非空节点for (int i = 1;i< _tables.size(); ++i){if (_tables[i]){return  iterator(_tables[i], this);} }return end();} iterator end(){//直接是空return  iterator(nullptr, this);}  typedef HashNode<T> Node;public: HashTable(){_tables.resize(10,nullptr);} //插入pair<iterator, bool> Insert(const T& data){Hash hs;//取模仿函数KeyOfT kot;//取key仿函数iterator it = Find(kot(data)); if (it._node != nullptr)//存在节点{return make_pair(it, false);} //扩容if (_n == _tables.size()){ vector<Node*> newTable(_tables.size() *2,nullptr); for (size_t i = 0; i<_tables.size(); ++i){//首先，插入头节点Node* cur = _tables[i];//再处理后面的串while (cur){Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newTable.size();//头插cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}  }_tables.swap(newTable); } size_t hashi = hs(kot(data)) % _tables.size();Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;++_n; return make_pair(iterator(newNode, this), true);} //查找iterator Find(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);} cur = cur->_next;}return  iterator(nullptr, this);} size_t size() {return _n;} //删除bool Erase(const K& key){KeyOfT kot;KeyOfT hs;Node* prev = nullptr;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi]; while (cur){if (kot(cur->_data) == key){//如果是第一个节点if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur; return true;}else{prev = cur;cur = cur->_next;}}return false;} private: vector<Node*> _tables;size_t _n = 0;}; //void test_hash_bucket1()//{// HashTable<string, int> hb;// hb.Insert({"asada",1});// hb.Insert({"DASDAS",1});// hb.Insert({"DASDAS",1});// hb.Insert({"DASDAS",1});// hb.Insert({"DASDAS",1});// hb.Insert({"DASDAS",1});// hb.Insert({"DASbAS",1});// hb.Insert({"HHDH",1});// //cout << hb.Erase("") << endl;// cout << hb.size() << endl;// cout << hb.Find("asada") << endl;// cout << hb.Find("DASDAS") << endl;// cout << hb.Find("HHDH") << endl;////} //void test_hash_bucket2()//{// vector<int> v = {1,2,3,4,5,65,6,7,8,9,90,0,2,3,23,45,232};// HashTable<int, int> hb;// for (size_t i = 0; i<v.size(); ++i)// {// if (i  == 9)// {// int j = 0;// }// hb.Insert(make_pair(v[i],v[i]));// }// cout << hb.size() << endl;//}  }AI写代码cpp运行 2、unordered_map#pragma once#pragma once#include"HashTable.h" namespace my_unordered_map {  template<class K, class V, class Hash = hashFunc<K> >class unordered_map{public://仿函数dstruct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};  typedef typename hash_bucket::HashTable<K, pair<const K, V>, Hash, 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);} 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()));//V()为匿名对象return ret.first->second;} private:hash_bucket::HashTable<K,  pair<const K, V>, Hash, MapKeyOfT> _ht;}; void test_unordered_map(){unordered_map<int,int> um;um.insert({1,1});um.insert({2,1});um.insert({3,1});um.insert({4,1});um.insert({5,1});um.insert({6,1});um.find(1);//cout << um.find(2) << endl;//cout << um.find(200) << endl; } void test_unordered_map1(){unordered_map<int, int> um;um.insert({ 1,1 });um.insert({ 2,1 });um.insert({ 3,1 });um.insert({ 4,1 });um.insert({ 5,1 });um.insert({ 6,1 });um[7];um[8];um[9];um[10];um[11]++;unordered_map<int, int>::iterator it = um.begin();while (it != um.end()){cout << it->first << " ";++it;}cout << endl;} void test_unordered_map2(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;} for (auto e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;}  };AI写代码cpp运行 3、unordered_set#pragma once#include"HashTable.h" namespace my_unorded_set { template<class K, class Hash = hashFunc<K> >class unorded_set {public: struct SetKeyOfT{const K& operator()(const K& key){return key;}};    typedef typename hash_bucket::HashTable< K,const K, Hash, SetKeyOfT>::iterator iterator;iterator beigin(){return _ht.begin();} iterator end(){return _ht.end();} pair<iterator, bool> insert(const K& key){return _ht.Insert(key);} iterator find(const K& key){return _ht.Find(key);} bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, Hash, SetKeyOfT> _ht;}; void test_unordered_set(){unorded_set<int> us;us.insert(1);us.insert(2);us.insert(3);us.insert(4);us.insert(6);us.insert(7);//cout << us.find(1) << endl;//cout << us.find(100) << endl;cout << "//////////////////////////////" << endl;cout << us.erase(100) << endl;cout << us.erase(1) << endl; } void test_unordered_set1(){unorded_set<int> us;us.insert(99);us.insert(4);us.insert(6);us.insert(7);us.insert(9);us.insert(2);us.insert(3);us.insert(11);us.insert(1);us.insert(96);us.insert(16);us.insert(56);us.insert(50);us.insert(57);us.insert(58);us.erase(11); unorded_set<int>::iterator it = us.beigin();while (it != us.end()){cout << *it << " ";++it;}cout << endl; }   };   ————————————————                             版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                        原文链接：https://blog.csdn.net/qq_51216031/article/details/139199982

一、数组去重的基本概念        数组去重是指从一个数组中移除重复的元素，保留唯一值的过程。例如，给定数组 [1, 2, 2, 3, 4, 4]，去重后的结果为 [1, 2, 3, 4]。        在日常开发中，数组去重是一个常见的需求。无论是处理用户输入、分析数据集，还是实现某些特定算法，数组去重都能显著提升代码的效率和可读性。然而，随着数据规模的增长，不同的去重方法在性能上的差异也会愈发明显。本文将深入探讨数组去重的各种方法及其性能表现，并重点分析如何利用 Set 和哈希表实现高效的去重操作。二、常见的数组去重方法        这篇博客主要讨论数组去重的性能，数组去重方法不细谈，有需求您可以移步到我写的数组去重方法合集，其中讨论了：数值类去重、引用类去重：去除完全重复的对象元素、引用类去重：去除部分重复的对象元素、特殊情况：对象的键值对顺序不同但其内容相同、混合数组去重五大类数组去重情景的各种去重方法，适用于任何场景：全网最全情景，深入浅出解析JavaScript数组去重：数值与引用类型的全面攻略-CSDN博客文章浏览阅读3.3k次，点赞171次，收藏97次。在日常开发中，数组去重是一个不可避免的话题。不管是简单的数值数组去重，还是复杂的引用类型数组去重，掌握多种方法可以帮助开发者高效、优雅地解决实际问题。在这篇博客中，我们将从基础到进阶，结合大量代码案例，系统介绍数组去重的各种技巧。_f (!txt.includes(num)) { txt.push(num) 什么意思https://opengms-watermelo.blog.csdn.net/article/details/143950308        常见数组去重方法有：方法    适用场景    优点    缺点Set    基础类型数组去重    简洁高效    无法处理引用类型遍历 + includes    基础类型数组去重    易理解    性能较低filter() + indexOf()    基础类型数组去重    通用    性能较低reduce()    复杂逻辑处理或混合类型数组去重    灵活，可扩展逻辑    写法稍复杂JSON.stringify+set    引用类型数组去重    简洁    无法处理嵌套或无序字段的对象Map    引用类型数组去重    性能较优，适合复杂数据结构    写法稍繁琐       有人做过一个测试：在处理一百万个数字的数组（有30%元素重复），使用常规方法去重，执行时间均超过30s，但是使用Set和Object哈希表用时在100ms左右。存在巨大的性能差距。        这里分享一下生成大量元素数组且重复元素比例可控的方法，这是我在别的资料里面找到的，感觉很有意思。function generateTestArray(size) {  const array = []; // 初始化一个空数组   for (let i = 0; i < size; i++) {    // 每次循环决定是否生成重复元素    if (Math.random() > 0.7) {      // 生成重复元素（30% 概率）      array.push(array[Math.floor(Math.random() * array.length)] || 0);    } else {      // 生成新的随机数（70% 概率）      array.push(Math.floor(Math.random() * size * 10));    }  }   return array;}AI写代码javascript运行拓展：该方法的系统误差        生成数的范围是0-10size。比如传入5，那就生成0-50之间的整数，传入1000，就生成0-10000之间的整数，其中有300个是确定重复的。 可是在0-10000之间的剩下的700个整数也有可能重复，重复的期望是多少呢？        首先，700个整数相对于10000来说很小，所以有3个整数相同的概率极低，故忽略，那么第i个生成的整数已经存在的概率为：         m为总范围，即10000，然后线性期望相加得到重复的数字数量为：         n是生成的数字总数，计算结果约为24.465个，即随机生成的重复率为：24.465/700，约为3.5%，即该方法生成数字的实际重复率约为：33.5%。        当然，其实真正的存在概率是：         综合期望是：         但是结果和近似估算几乎没差距，就不展开了。如果想降低这个系统误差，直接扩大size后面的乘数即可。拓展：排序后去重        这种去重方法的时间复杂度为O(nlogn)，额外开销主要由排序操作决定。但是这种方法只能用来进行基础数据类型的去重。同时会改变原始数组的顺序，在部分场景的使用受限。        为什么呢？        首先我们知道，遍历 + includes、filter() + indexOf()、reduce()只有写法上存在优雅与否，但是本质都是双循环，均为O(n²)复杂度，关键就在于Set和Object哈希表去重特别高效，接下来我们来探究一下Set和Object哈希表去重高效的原因。三、Set和Object哈希表综合复杂度为O(n)的秘密1、数据结构区别        Set 是 ES6 引入的一种集合数据结构，专门用于存储唯一值。它的底层实现基于哈希表，因此插入和查找的时间复杂度接近 O(1)。        Object哈希表就不用说了，本质就是利用Object键的映射创建了一个哈希表，只是没有哈希函数，且无法兼容引用类型（可以通过JSON.stringify()处理后兼容）。V8引擎中，Set使用哈希表和红黑树的组合实现，据测试Set的效率要略优于Object哈希表。2、Set去重的底层原理        Set 的高效性源于其底层的哈希表实现。以下是关键步骤：计算哈希值 ：通过哈希函数将每个值映射到一个整数索引。定位存储位置 ：根据哈希值找到对应的存储位置。检查冲突 ：如果发生哈希冲突，则采用链地址法或开放地址法解决。插入或跳过 ：如果该位置已有相同值，则跳过；否则插入。        这种机制使得 Set 能够快速判断某个值是否已经存在，从而实现高效的去重。3、Set去重的鲁棒性        我们来看一个特殊的例子：function deduplicateWeirdValues(array) {  return [...new Set(array)];} const weirdArray = [0, -0, NaN, NaN, undefined, null, false, 0, "0"];console.log(deduplicateWeirdValues(weirdArray));// 输出: [0, NaN, undefined, null, false, "0"]AI写代码javascript运行        在这样一个去重案例中，NaN !== NaN， 同时 0 == "0"，但是Set只保留了一个NaN，同时又区分开了 0 与 "0"  ，这是常规方法所做不到的：要么会保留所有的NaN，要么无法区分 0 和 "0"。4、Set去重的局限性        仅限于基础数据类型的数组去重，如果涉及到引用类型的数组去重，一般需要结合JSON.stringify（）函数（有局限性）或者设计对比函数来实现。详情可以参考这篇文章：全网最全情景，深入浅出解析JavaScript数组去重：数值与引用类型的全面攻略四、总结        数组去重过程中，本质可以简化为遍历原数组，然后通过去重算法判断是否重复，重复就去除，不重复就添加，所以综合复杂度一定是O(n)*x，x是去重算法的时间复杂度。Set和Object哈希表去重的时间复杂度正好是O(1)，如果还要进一步优化，就需要再在去重算法上下功夫了。        只有锻炼思维才能可持续地解决问题，只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助，麻烦您点个赞支持一下，还可以收藏起来以备不时之需，有疑问和错误欢迎在评论区指出~        其他热门文章，请关注：        极致的灵活度满足工程美学：用Vue Flow绘制一个完美流程图        你真的会使用Vue3的onMounted钩子函数吗？Vue3中onMounted的用法详解        DeepSeek：全栈开发者视角下的AI革命者        通过array.filter()实现数组的数据筛选、数据清洗和链式调用        通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能        TreeSize：免费的磁盘清理与管理神器，解决C盘爆满的燃眉之急        通过MongoDB Atlas 实现语义搜索与 RAG——迈向AI的搜索机制        深入理解 JavaScript 中的 Array.find() 方法：原理、性能优势与实用案例详解        el-table实现动态数据的实时排序，一篇文章讲清楚elementui的表格排序功能        MutationObserver详解+案例——深入理解 JavaScript 中的 MutationObserver        JavaScript中通过array.map(）实现数据转换、创建派生数组、异步数据流处理、DOM操作等        前端实战：基于Vue3与免费满血版DeepSeek实现无限滚动+懒加载+瀑布流模块及优化策略        高效工作流：用Mermaid绘制你的专属流程图；如何在Vue3中导入mermaid绘制流程图        干货含源码！如何用Java后端操作Docker（命令行篇）        在线编程实现！如何在Java后端通过DockerClient操作Docker生成python环境        Dockerfile全面指南：从基础到进阶，掌握容器化构建的核心工具————————————————                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                        原文链接：https://blog.csdn.net/RenGJ010617/article/details/147259594

数据结构前言1.什么是数据结构？数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的 数据元素的集合。 2.什么是算法？算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为 输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。 3.数据结构和算法的重要性现在公司对学生代码能力的要求是越来越高了，大厂笔试中几乎全是算法题而且难度 大，中小长的笔试中才会有算法题。算法不仅笔试中考察，面试中面试官基本都会让现场写代 码。而算法能力短期内无法快速提高了，至少需要持续半年以上算法训练积累，否则真正校招时 笔试会很艰难，因此算法要早早准备。 算法的时间复杂度和空间复杂度1.算法效率1.1 如何衡量一个算法的好坏如何衡量一个算法的好坏呢？比如对于以下斐波那契数列： long long Fib(int N){ if(N < 3) return 1;  return Fib(N-1) + Fib(N-2);} 斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？ 1.2 算法的复杂度算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。**时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。**在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 1.3 复杂度在校招中的考察  2.时间复杂度2.1 时间复杂度的概念时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。 // 请计算一下Func1中++count语句总共执行了多少次？void Func1(int N){    int count = 0;    for (int i = 0; i < N ; ++ i)   {         for (int j = 0; j < N ; ++ j)         {              ++count;         }    }     for (int k = 0; k < 2 * N ; ++ k)    {        ++count;    }     int M = 10;    while (M--)    {         ++count;    }        printf("%d\n", count);} 2.2 大O的渐进表示法大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。推导大O阶方法： 1、用常数1取代运行时间中的所有加法常数。2、在修改后的运行次数函数中，只保留最高阶项。3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。使用大O的渐进表示法以后，Func1的时间复杂度为：   通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况：最坏情况：任意输入规模的最大运行次数(上界)平均情况：任意输入规模的期望运行次数最好情况：任意输入规模的最小运行次数(下界)例如：在一个长度为N数组中搜索一个数据x最好情况：1次找到最坏情况：N次找到平均情况：N/2次找到 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N) 2.3常见时间复杂度计算举例实例1：// 计算Func2的时间复杂度？void Func2(int N){     int count = 0;     for (int k = 0; k < 2 * N ; ++ k)    {            ++count;    }      int M = 10;     while (M--)     {        ++count;     }      printf("%d\n", count);} F(N) = 2*N+10->O(N) 实例2:// 计算Func3的时间复杂度？void Func3(int N, int M){ int count = 0; for (int k = 0; k < M; ++ k) {++count; }  for (int k = 0; k < N ; ++ k) {  ++count; }  printf("%d\n", count);} 时间复杂度 O(M+N) O(max{M,N}) 如果M远大于N->O(M) 如果N远大于M->O(N) 实例3:// 计算Func4的时间复杂度？void Func4(int N){   int count = 0;   for (int k = 0; k < 100; ++ k) {   ++count; }   p(rintf("%d\n", count);}//O(1) 代表常数次 O(1) 不是代表一次 代表常数次 实例4:// 计算strchr的时间复杂度？const char * strchr ( const char * str, int character );AI写代码c运行12while(*str){if(*str==character)        return str;    else        ++str;} 最好O(1) 最坏O(N) 实例5:冒泡排序/ 计算BubbleSort的时间复杂度？void BubbleSort(int* a, int n){ assert(a); for (size_t end = n; end > 0; --end) {     int exchange = 0;     for (size_t i = 1; i < end; ++i) {if (a[i-1] > a[i]){  Swap(&a[i-1], &a[i]);  exchange = 1;  } }  if (exchange == 0) break; }}N-1+N-2+……+2+1 = N(N-1)/2–>O(N^2)* 实例6:二分查找// 计算BinarySearch的时间复杂度？int BinarySearch(int* a, int n, int x){ assert(a);  int begin = 0; int end = n-1; // [begin, end]：begin和end是左闭右闭区间，因此有=号 while (begin <= end) {     int mid = begin + ((end-begin)>>1);     if (a[mid] < x)     begin = mid+1;     else if (a[mid] > x)     end = mid-1;     else     return mid; } return -1;  二分查找 O(logN) 默认以2为底 实例7:// 计算阶乘递归Fac的时间复杂度？long long Fac(size_t N){ if(0 == N) return 1;  return Fac(N-1)*N;} Fac(N)—>N次 Fac(N-1)–>N-1次 Fac(N-2)–>N-次 …… Fac(1)–>1次 递归时间复杂度:所有递归调用次数累加 等差数列求和 时间复杂度为O(N^2) 实例8:// 计算斐波那契递归Fib的时间复杂度？long long Fib(size_t N){ if(N < 3) return 1;  return Fib(N-1) + Fib(N-2);}  等比数列求和 2^(N-1)-1 时间复杂度为O(2^n) 面试题1：消失的数字消失的数字  思路一先排序，再依次查找，如果下一个值不等于前一个+1，下一个值就是消失的数字 冒泡排序 O(N^2) qsort O(N*logN) 思路二先求0到N,再依次减去数组中值，剩下的那个值就是消失的数字 int missinNumber(int* nums,int numsSize){    int N=numsSize;    int ret-=N(N+1)/2;    for(int i=0;i<numsSize;++i)    {        ret-=sums[i];}} N太大会存在溢出风险 思路三异或(相同的值==0) int missinNumber(int* nums,int numsSize){    int N=numsSize;    int x=0;    for(int i=0;i<numsSize;++i)    {        x^=nums[i];    }    for(int j=0;j<=N;++j)    {        x^=j;    } 面试题2：轮转数组轮转数组  思路一先看旋转一次 int tmp=nums[numsSize-1];for(int i =numsSize-2;i>=0;i--){    nums[i+1]=nums[i];}nums[0]=tmp; 真实的旋转次数 K%=N 时间复杂度:O(K*N) 最好的情况:k%N=0 最坏的情况:K%N=N-1–>O(N^2) void rotate(int* nums,int numsSize,int k){    k%=numsSize;    while(k--)    {           //旋转一次        int tmp=nums[numsSize-1];        for(int i =numsSize-2;i>=0;i--)        {            nums[i+1]=nums[i];        }        nums[0]=tmp;    }}   void reverse(int*a,int left,int right){    while(left<right)    {        int tmp=a[left];        a[left]=a[right];        a[right]=tmp;        ++left;        --right;    }}void rotate(int* nums;int sumsSize;intk){    k%=sumsSize;   reverse(nums,0,numsSize-k-1);   reverse(nums,numsSize-k,numsSize-1);   reverse(nums,0,numsSize-1);    } 3.空间复杂度空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度。它通常用大O表示法来表示，记作S(n)=O(f(n)) ，其中 n是问题的规模， f(n) 是算法所占存储空间的函数。空间复杂度的分析有助于了解算法在执行时所需的内存资源，从而评估算法的效率和可行性。 常见的空间复杂度：O(N^2) O(N) O(1) 实例//计算阶乘递归Fac的空间复杂度long long Fac(size_t N){    if(N==0)        return 1;    return Fac(N-1)*N;} 因为每次调用都占用一个空间 所以空间复杂度为O(N)————————————————                             版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                        原文链接：https://blog.csdn.net/czx_163/article/details/149250386

正文快速排序是一种非常高效的排序算法，其基本思想是通过一个划分操作将待排序的数组分为两个子数组，左边子数组的元素都比右边子数组的元素小，然后递归地对这两个子数组进行排序。下面是快速排序的多种版本及其实现原理和优化方法的详细介绍。 1. 基本快速排序原理 选择基准：从数组中选择一个元素作为基准（pivot）。分区操作：将数组分为两部分，左边部分的所有元素都小于基准，右边部分的所有元素都大于基准。递归排序：对左右两个子数组递归地进行快速排序。三种版本： 霍尔法（Hoare法）霍尔法是以快速排序的创始人霍尔命名的，也是快速排序最初的实现版本。其基本思想是用两个指针分别指向待排序数组的开头和结尾，然后让这两个指针相向而行，根据与key值的大小关系进行移动和交换，直到两者相遇。具体步骤如下： 任取一个待排序数组中的数作为key值（可以取头值、尾值或中间值等）。 如果取头值作为key值，则让右指针先移动；如果取尾值作为key值，则让左指针先移动。“移动”的过程是： right指针直到找到小于key的值才停下来，left指针直到找到大于key的值才停下来。 将left和right所对应的值进行交换。 重复上述过程，直到left和right相遇。此时，将key值和right所指向的值进行交换，right最后指向的位置就是key值应该所在的位置。 以right为界，将数组一分为二，递归地对左右两部分进行排序。 代码实现： //快速排序-----霍尔void QuickSort1(int* a, int left, int right) {if (left >= right) return;int end = right, begin = left, keyi = left;while (left < right) {//右指针找小while (left < right && a[right] >= a[keyi]) {--right;} //左指针找大while (left < right && a[left] <= a[keyi]) {++left;} Swap(&a[right], &a[left]);}//最后对调将目标值放到合适的位置Swap(&a[keyi], &a[left]);keyi = left; QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);} 霍尔法的优势在于其高效性，但理解起来可能相对复杂一些。 挖坑法挖坑法是快速排序的一种实现方式，其思路与霍尔法类似，但更容易理解。具体步骤如下： 选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。定义left和right两个指针，分别从数组的左右两端开始相向而行。right指针向左移动，直到找到比key小的数；然后将该数填入坑中，并将hole更新为当前right的位置。left指针向右移动，直到找到比key大的数；然后将该数填入当前的hole中，并再次更新hole为当前left的位置。重复上述步骤，直到left和right相遇。此时，将key值填入最后的hole中。以hole为界，将数组一分为二，递归地对左右两部分进行排序。 代码实现： //快速排序-----挖坑void QuickSort2(int* a, int left, int right) {if (left >= right) return;int end = right, begin = left;int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left], hole = left;while (left < right) {//右指针找小while (left < right && a[right] >= key) {--right;}a[hole] = a[right];hole = right; //左指针找大while (left < right && a[left] <= key) {++left;}a[hole] = a[left];hole = left; }a[hole] = key; QuickSort2(a, begin, hole - 1);QuickSort2(a, hole + 1, end);} 挖坑法的优势在于其直观易懂，便于理解和实现。 快慢指针法这种方法使用两个指针从数组的两端向中间移动，直到它们相遇或交错。 代码实现： //快速排序-----快慢指针void QuickSort3(int* a, int left, int right) {if (left >= right) return;int keyi = left;int prev = left, cur = left + 1;int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);while (cur <= right){if (a[cur] < a[keyi]) {Swap(&a[cur], &a[++prev]);}cur++;}Swap(&a[keyi], &a[prev]);keyi = prev;QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);}  2. 随机化快速排序原理 随机选择基准：在每次划分之前，随机选择一个元素作为基准，以减少最坏情况的发生概率。分区操作：与基本快速排序相同。递归排序：对左右两个子数组递归地进行快速排序。代码示例 #include <stdlib.h> int randomPartition(int arr[], int low, int high) {    int random = low + rand() % (high - low + 1);    swap(&arr[random], &arr[high]);    return partition(arr, low, high);} void randomizedQuickSort(int arr[], int low, int high) {    if (low < high) {        int pi = randomPartition(arr, low, high);         randomizedQuickSort(arr, low, pi - 1);        randomizedQuickSort(arr, pi + 1, high);    }}  3. 三向切分快速排序原理 选择基准：选择一个元素作为基准。三向分区：将数组分为三部分：左边部分的所有元素都小于基准。中间部分的所有元素都等于基准。右边部分的所有元素都大于基准。递归排序：只对左右两个子数组递归地进行快速排序，中间部分已经有序。代码示例 void threeWayQuickSort(int arr[], int low, int high) {    if (high <= low) return;     int lt = low, gt = high;    int pivot = arr[low];    int i = low + 1;     while (i <= gt) {        if (arr[i] < pivot) {            swap(&arr[lt++], &arr[i++]);        } else if (arr[i] > pivot) {            swap(&arr[i], &arr[gt--]);        } else {            i++;        }    }     threeWayQuickSort(arr, low, lt - 1);    threeWayQuickSort(arr, gt + 1, high);} 4. 插入排序优化原理 选择基准：选择一个元素作为基准。分区操作：将数组分为两部分。递归排序：当子数组的大小小于某个阈值时，使用插入排序而不是快速排序，以减少递归调用的开销。代码示例 void hybridQuickSort(int arr[], int low, int high, int threshold) {    while (low < high) {        if (high - low < threshold) {            insertionSort(arr, low, high);            break;        } else {            int pi = partition(arr, low, high);             hybridQuickSort(arr, low, pi - 1, threshold);            low = pi + 1;        }    }} void insertionSort(int arr[], int low, int high) {    for (int i = low + 1; i <= high; i++) {        int key = arr[i];        int j = i - 1;         while (j >= low && arr[j] > key) {            arr[j + 1] = arr[j];            j--;        }        arr[j + 1] = key;    }}  6.非递归优化因为递归算法都存在一个无法避免的问题——递归深度太大会导致栈溢出的问题，所以我们应该掌握非递归实现各种递归算法的技能。 递归算法改非递归一般有两种思路：（1）直接改循环；（2）借用数据结构其中栈是最为常用的。对于快速排序，使用栈是最好模拟的方式。代码实现： （1）ST.h #include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h> #define MAXCAPACITY 4 typedef int Datastyle; typedef struct stack {Datastyle* a;               //指向有效数据的指针 int top;//给top初始化一般要么给-1，要么给0，如果给1及以上就会造成空间的浪费，给-2及以下也会造成空间的浪费（除非进行特殊的处理，分情况给top加值）//如果top初始化给的是-1，则top代表的是栈顶元素所在位置的下标；如果top初始化给的是0，则top代表的是栈顶元素所在位置的下一个位置的下标//这是因为（以插入为例）每一次入栈后，top必定加1-----而top初始化给-1元素入栈就是top先++再赋值；而top初始化给0元素入栈就是top先赋值再++//但无论哪种入栈方式，最终的结果都是top++。至于为什么两种不同的给top赋初值对应不同的入栈方式也是取决于数组的下标从0开始的特点//本次我们就展示top初始化为0的栈的写法int capacity;}ST; //初始化栈void STInit(ST* ps); //销毁栈void  STDestory(ST* ps); //插入数据（从栈顶）----（入栈，压栈）void STPush(ST* ps, Datastyle x); //删除数据（从栈顶）----（出栈）void STPop(ST* ps); //访问栈顶元素Datastyle STTop(ST* ps); //得出栈的元素个数int STSize(ST* ps); //判空bool STEmpty(ST* ps);  ST.c #include"ST.h" //初始化栈void STInit(ST* ps) {assert(ps);Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));if (temp == NULL) {perror("malloc fail");exit(-1);}ps->a = temp;ps->capacity = MAXCAPACITY;ps->top = 0;} //销毁栈void  STDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;} //插入数据（从栈顶）----（入栈，压栈）void STPush(ST* ps, Datastyle x) {assert(ps);//判断是否满了if (ps->top == ps->capacity) {Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle)); //扩容为当前容量的两倍比较合理if (temp == NULL) {perror("realloc fail");return;}ps->capacity *= 2;ps->a = temp;}ps->a[ps->top++] = x;} //判空bool STEmpty(ST* ps) {return (ps->top == 0);} //删除数据（从栈顶）----（出栈）void STPop(ST* ps) {assert(ps && !STEmpty(ps));--ps->top;} //访问栈顶元素Datastyle STTop(ST* ps) {return ps->a[ps->top - 1];} //得出栈的元素个数int STSize(ST* ps) {assert(ps);return ps->top;}  Sort.c #include"ST.h"//快速排序-----非递归实现------入栈元素：每次递归会发生改变的参数void QuickSortNonR(int* a, int left, int right) {//Chaucer创建栈ST st; //初始化栈STInit(&st); //先入栈STPush(&st, right);STPush(&st, left); while (!STEmpty(&st)){//因为栈先入后出的特点，所以我们先入右再入左int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st); //进行单趟排序并返回keyiint keyi = SingalQuickSort(a, begin, end);//[begin,keyi - 1] keyi [keyi + 1, end]  //因为栈先入后出的特点，所以我们先入右再入左，不过当区间内仅剩一个元素或没有元素的时候，我们也不应该入栈if (keyi + 1 < end) {STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1) {STPush(&st, keyi - 1);STPush(&st, begin);}} //销毁栈STDestory(&st);}   总结快速排序的多种版本和优化方法可以显著提高其在不同场景下的性能。选择合适的版本和优化方法，可以根据具体的数据特性和应用场景，进一步提升排序算法的效率和稳定性。希望这些介绍能帮助你更好地理解和应用快速排序算法。————————————————                             版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                        原文链接：https://blog.csdn.net/z15879084549/article/details/145091907

 一.插入排序 1.1 直接插入排序 1.已知第一个元素如果不包含其他元素，没有元素可以比较，为有序。 2.我们可以直接从第二个元素i开始，创建一个对象tmp来接下标元素，如果比前一个元素小，前一个元素往后移动，tmp插入i-1下标 3.当元素大于或者等于时，则tmp直接放在i位置即可。    public static void insertSort(int[] array){         for(int i=1;i<array.length;i++){//由数组1下标开始进行比较             int tmp=array[i];             int j=i-1;             for(;j>=0;j--){                 if(tmp<array[j]){                     array[j+1]=array[j];//将j放入j+1位置                 }else{                 //进入else则为有序，break跳出嵌套循环                     break;                 }             }       //当嵌套的for循环一直在比较最小值tmp，知道为-1跳出循环，这里需要j+1       //当大于时候，因为i-1赋值给j，break跳出后j需要+1下标值得到tmp             array[j+1]=tmp;         }     } 时间复杂度:最坏情况时间复杂度为O(N*N) 最好情况时间复杂度为O(N) 空间复杂度O(1) 稳定排序  1.2 希尔排序 希尔排序又称缩小增量法。 希尔排序的思想，定义一个整数，将待排序数组元素长度分成多个组，每一个组进行插入排序，重复上述分组，此时为预排序。当到达1时，将所有记录好的元素在一组中进行排序。 每一次分组排序后都变为有序，每组数据由少变多，越来越有序。  划分为n/2组进行比较，根据n/2的距离来划分每一组的数量。     public static void shellSort(int[] array){         int gap=array.length;         while(gap>1){             gap/=2;//将数组/2，有多组变少组直到为1             shell(array,gap);         }     }     public static void shell(int[] arr,int gap){     //从gap开始遍历         for(int i=gap;i<arr.length;i++){         //获取gap下标的值             int tmp=arr[i];             求i-gap个差距得到j值             int j=i-gap;             for(;j>=0;j-=gap){                 if(tmp<arr[j]){                     arr[j+gap]=arr[j];                 }else{                     break;                 }             }             arr[j+gap]=tmp;         }     }  时间复杂度O(N^1.25) 空间复杂度O(1)  二.选择排序 2.1 单向选择排序 单向选择排序通过定义minIndex值来获取最小的元素下标，然后与0下标进行交换     public static void selectSort2(int[] array){         for(int i=0;i<array.length;i++){             int minIndex=i;              for(int j=i+1;j<array.length;j++){                 if(array[j]<array[minIndex]){                     minIndex=j;                 }             }             swap(array,minIndex,i);         }     } 2.2双向选择排序 双向选择排序是我们通过定义起始位置和终点位置的下标作为条件，通过初始位置筛选最大值和最小值的下标，将最大值下标与尾部交换，最小值下标与初始位置交换，然后继续重复上述，知道筛选完成。  这里如果max的最大值为0下标的时候，max已经被 minIndex交换，maxIndex等于minIndex获取最大元素的下标值即可。    public static void selectSort(int[] array){         //起始位置和末尾的下标值         int left=0;         int right=array.length-1;         while(left<right){             //都从0下标开始比较             int maxIndex=left;             int minIndex=left;             for(int i=left+1;i<=right;i++){                 if(array[i]<array[minIndex]) minIndex=i;                 if(array[i]>array[maxIndex]) maxIndex=i;             }             swap(array,left,minIndex);             //如果0下标就是maxIndex的最大值，minIndex的位置就是maxIndex的最大值             if(maxIndex==left)maxIndex=minIndex;             swap(array,right,maxIndex);             left++;             right--;         }     } 时间复杂度：O(N^2) 空间复杂度：O(1)  2.3 堆排序 堆序详情堆排序   //创建二叉堆     public static void createHeap(int[] array){         for(int parent=(array.length-1-1)/2;parent>=0;parent--){             siftDown(array,parent,array.length);         }     }     private static void siftDown(int[] array,int parent,int size) {         int child=2*parent+1;         while(child<size){             if(child+1<size&&array[child]<array[child+1]){                 //child是左右孩子的最大值                 child=child+1;             }             if(array[child]>array[parent]){                 //交换孩子与父亲                 swap(array,child,parent);                 //调整父亲节点和孩子节点                 parent=child;                 child=(2*parent)+1;             }else{                 break;             }         }     }     //根据创建好的大跟堆，通过最后一个下标与0下标交换后缩小堆的范围，直到称为有序数组     public static void heapSort(int[] array){         createHeap(array);         int end=array.length-1;         while(end>0){             swap(array,0,end);             siftDown(array,0,end);             end--;         }     } 时间复杂度O(N*logN) 空间复杂度O(1) ————————————————                              版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                          原文链接：https://blog.csdn.net/weixin_60489641/article/details/144065676 

 1.题目要求 (语言: C)在生物信息学家处理基因序列时，经常需要将基因序列转化为独热码，在英文文献中称做 one-hot code, 直观来说就是有多少个状态就有多少比特，而且只有一个比特为1，其他全为0的一种码制。 如基因序列有四种状态，ATCG。分别可以转化为0001，0010，0100，1000。 如果遇到其他字符，则转化为0000。如遇到atcg，也转化为0001，0010，0100，1000。 请一次性输入若干段序列，并输入这些序列的独热码。（因段数以及序列长度不确定，需要使用动态数组,测试用例中每行长度不超过20）  如 输入： 2 ATCG AAAA 输出： 0001001001001000 0001000100010001 2.代码实现  1.方法一（二维数组） 比较科学且正常的做法  #include <stdio.h> #include <string.h>   void convert(char *sequence, char result[][5]);   int main() {     int n;     scanf("%d", &n);       char sequences[20][20];     char results[20][20 * 4];       for (int i = 0; i < n; i++) {         scanf("%s", sequences[i]);         convert(sequences[i], (char (*)[5])results[i]);         printf("%s\n", results[i]);     }       return 0; } void convert(char *sequence, char result[][5]) {     int len = strlen(sequence);     for (int i = 0; i < len; i++) {         switch (sequence[i]) {             case 'A':                 strcpy(result[i], "0001");                 break;             case 'T':                 strcpy(result[i], "0010");                 break;             case 'C':                 strcpy(result[i], "0100");                 break;             case 'G':                 strcpy(result[i], "1000");                 break;             default:                 strcpy(result[i], "0000");         }     } }  2.方法二（一维数组）  纯属瞎捣鼓，不建议......  #include<stdio.h> #include<stdlib.h>   int main() {     int n;     int count = 0;     // 提示输入要处理的序列数量     printf("请输入要处理的序列数量：");     scanf("%d", &n);     // 提示输入 n 段基因序列     printf("请输入%d段基因序列：\n", n);     char *array = (char *)malloc(n * 21 * sizeof(char));     for (int i = 0; i < n * 20; i++) {         scanf("%c", &array[i]);         if (array[i] == '\n') {             array[i] = '0';             count++;         }         if (count > n) {             break;         }     }     int countPRO = 0;     // 输出独热码的提示     printf("独热码如下：\n");     for (int i = 0; i < n * 20; i++) {         if (array[i] == 'A' || array[i] == 'a') {             printf("0001");         } else if (array[i] == 'T' || array[i] == 't') {             printf("0010");         } else if (array[i] == 'C' || array[i] == 'c') {             printf("0100");         } else if (array[i] == 'G' || array[i] == 'g') {             printf("1000");         } else if (array[i]!= '0') {             printf("0000");         } else {             if (i!= 0 && countPRO!= n) {                 printf("\n");             }             countPRO++;         }         if (countPRO > n) {             break;         }     }     free(array);     return 0; } ————————————————                              版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。                          原文链接：https://blog.csdn.net/2402_86955314/article/details/144729524 

前言在数据结构和算法中，红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在保证数据有序的同时，也保证了树的平衡性，从而提高了搜索、插入和删除操作的效率。下面我们将深入探讨红黑树的定义、与二叉树的区别、以及它的用途，并通过一个例子来加深理解。红黑树的定义红黑树是一种特殊的二叉搜索树，它在每个节点上附加一个颜色属性，可以是红色或黑色。红黑树需要满足以下五个性质（也称为“红黑性质”）：每个节点要么是红色，要么是黑色。根节点是黑色。每个叶节点（NIL或空节点）是黑色。如果一个节点是红色的，则它的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。这些性质确保了红黑树的平衡性，使得在插入、删除等操作时，树的高度能够保持在对数级别，从而保证了操作的效率。红黑树与二叉树的区别二叉树是一种简单的数据结构，每个节点最多有两个子节点（通常称为左子节点和右子节点）。然而，二叉树并不保证树的平衡性，这可能导致在插入或删除节点后，树的高度急剧增加，从而降低了搜索、插入和删除操作的效率。相比之下，红黑树通过引入颜色属性和红黑性质，保证了树的平衡性。在插入或删除节点时，红黑树会进行一系列旋转和重新着色操作，以保持树的平衡性。这些操作保证了红黑树的高度始终保持在对数级别，从而保证了操作的效率。红黑树的用途红黑树在许多场景中都有广泛的应用，包括但不限于：关联数组：红黑树可以用作一种关联数组，其中键存储在每个节点中，并且节点的颜色用于维护树的平衡。这种数据结构允许在O(log n)的时间内进行搜索、插入和删除操作。内存管理：在操作系统中，红黑树可以用于管理内存分配和释放。通过将内存块表示为红黑树的节点，并使用红黑性质来维护树的平衡性，操作系统可以在O(log n)的时间内找到可用的内存块或释放已使用的内存块。路由表：在计算机网络中，路由器使用路由表来决定数据包的转发路径。由于路由表需要频繁地进行更新和查找操作，因此使用红黑树来存储路由表可以提高这些操作的效率。例子：使用红黑树实现有序集合假设我们有一个有序集合，需要支持插入、删除和查找操作。由于红黑树具有自动排序和平衡的特性，因此它非常适合用于实现这样的有序集合。以下是一个简单的Python示例，使用红黑树（通过Python内置的collections.OrderedDict实现，尽管它不是纯粹的红黑树实现，但提供了类似的功能）来实现有序集合：from collections import OrderedDict class OrderedSet: def __init__(self): self._dict = OrderedDict() def add(self, item): self._dict[item] = True def remove(self, item): if item in self._dict: del self._dict[item] def __contains__(self, item): return item in self._dict def __iter__(self): return iter(self._dict) def __len__(self): return len(self._dict) # 使用示例 s = OrderedSet() s.add(3) s.add(1) s.add(4) s.add(1) # 重复添加不会改变集合 print(s) # 输出：OrderedDict([(1, True), (3, True), (4, True)]) print(3 in s) # 输出：True s.remove(3) print(s) # 输出：OrderedDict([(1, True), (4, True)])虽然这个示例中使用了OrderedDict而不是纯粹的红黑树实现，但它展示了红黑树在有序集合中的应用。在实际应用中，我们可以使用更高效的红黑树库来实现类似的功能。

Bitmap：说明：采用一个bit来标记某个value，可以节省存储空间。优点是占用内存少，比如N为一亿（10000 0000），只需要N/8=1250 0000个byte，约等于12Mb。缺点为不能重复数据进行排序和查找思想：利用一个byte中的8个bit来表示8个数。某数出现，利用映射将对应bit位置1。比如元素3，在8bit的映射为：00010000再来个元素5，在8bit的映射为：00010100映射表为：A[0]->0~7;A[1]->8~15;A[2]->16~23;…….具体实现：（例子为32位）#include #define BITSPERWORD 32#define SHIFT 5#define MASK 0x1F//#define N 10000000#define N 100 int a[1 + N/BITSPERWORD];//申请内存的大小 void set(int i) {// a[i>>SHIFT] |= (1<<(i& MASK)); a[i/BITSPERWORD] |= (0x01<<(i%BITSPERWORD));}//clr 初始化所有的bit位为0void clr(int i) {// a[i>>SHIFT] &= ~(1<<(i & MASK)); a[i/BITSPERWORD] &= ~(0x01<<(i%BITSPERWORD));}//test 测试所在的bit为是否为1int test(int i){ return a[i>>SHIFT] & (0x01<<(i & MASK));} int main(){ int i; for (i = 0; i < N; i++) clr(i); for(i=0;ia[i/BITSPERWORD]或a[i>>SHIFT]，实现i/32，即求出操作bit所在数的下标。0x01<<(i%BITSPERWORD)或(1<<(i& MASK))，取得该操作bit的具体位置。   实例： 1、 已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。 思路：8位数，0000 0000~9999 9999，范围为一亿。需要10^8个bit，12M左右字节。 实现： int const nArraySize = 100000000 /(sizeof(int)*8) + 1;int Bitmap[nArraySize];void MapPhoneNumberToBit(int nNumber){ Bitmap[nNumber/ (8*sizeof(int))] |= 0x00000001<<(nNumber%(8*sizeof(int)));} 2、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。思路：用两个bit来表示一个数。0表示整数未出现，1表示出现一次，2表示出现多次。在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。注意控制与置位的分离。 实现#include unsigned char flags[1000]; //数组大小自定义 unsigned get_val(int idx) { // | 8 bit | // |00 00 00 00| //映射3 2 1 0 // |00 00 00 00| //表示7 6 5 4 // …… // |00 00 00 00| int i = idx/4; //一个char 表示4个数， int j = idx%4; unsigned ret = (flags[i]&(0x3<<(2*j)))>>(2*j); //0x3是0011 j的范围为0-3，因此0x3<<(2*j)范围为00000011到11000000 如idx=7 i=1 ,j=3 那么flags[1]&11000000, 得到的是|00 00 00 00| //表示7 6 5 4 return ret; } unsigned set_val(int idx, unsigned int val) { int i = idx/4; int j = idx%4; unsigned tmp = (flags[i]&~((0x3<<(2*j))&0xff)) | (((val%4)<<(2*j))&0xff); flags[i] = tmp; return 0; } unsigned add_one(int idx) { if (get_val(idx)>=2) { //这一位置上已经出现过了？？ return 1; } else { set_val(idx, get_val(idx)+1); return 0; } } //只测试非负数的情况; //假如考虑负数的话,需增加一个2-Bitmap数组. int a[]={1, 3, 5, 7, 9, 1, 3, 5, 7, 1, 3, 5,1, 3, 1,10,2,4,6,8,0}; int main() { int i; memset(flags, 0, sizeof(flags)); printf("原数组为:"); for(i=0;i < sizeof(a)/sizeof(int); ++i) { printf("%d ", a[i]); add_one(a[i]); } printf("\r\n"); printf("只出现过一次的数:"); for(i=0;i < 100; ++i) { if(get_val(i) == 1) printf("%d ", i); } printf("\r\n"); return 0; }  3、给你一个文件，里面包含40亿个整数，写一个算法找出该文件中不包含的一个整数， 假设你有1GB内存可用。如果你只有10MB的内存呢？思路：40亿个整数（40*10^8*4byte~16GB）。A、 内存为1G显然无法将16G的数据直接放入1G内存，采用bitmap算法，40*10^8bit= 0.5G（大约），满足1G的内存。B、 内存为10M如果我们只有10MB的内存，明显使用BitMap也无济于事了。 内存这么小，注定只能分块处理。比如分块的大小是1000，那么第1块的范围就是0到999，第2块的范围就是1000 到1999……实际上并不保存这些数，而是给每一个块设置一个计数器。 这样每读入一个数，就在它所在的块对应的计数器加1。处理结束之后，我们找到一个块，它的计数器值小于块大小(1000)，说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理这个块即可。

快排是一种使用广泛的排序，它比merge需要的空间更小，而且改进过的快排速度很快，平均O(nlgn)。快排也用到了递归的思想，所以我才说递归很重要的嘛。我们大概看一下快排的基本过程：选择一个数，把小于它的放左边，不小于它的放右边。没了。那么很显然，这个算法的特点和难点就是“怎么选出一个合适的点”和“怎么实现‘放’”。选择肯定是超重要的，还记得上一节的“递归树”吗，如果采用“二路归并”，在这里就是分为2个序列，那么最好是把分开的点选在中间，因为树高是通过最长路径来计算的。另一个问题就是怎么实现这个“通过一个点把比它小的全放左边比它大的全放右边”。我们大概可以这样做：一个flag从最左端开始移动，一个flag从最右端开始移动，当碰到一个左侧的点大于被选择点，并且一个右侧的点小于被选择的点时，交换它们。当然，在执行的时候我们可以把选中的那个点放在数组的最右边，当然也可以不动，比如我们直接选择最左端和最右端的点当作我们的判断点。那么我们来实现一哈：//先实现一下主函数template <typename T>void QuickSort( T a[ ], int n ){ if (n <= 1) return; Qsort( a, 0, n-1 );} //是的，这就完了哈哈，我们赶紧来实现一哈核心功能Qsort()：template <typename T>void Qsort( T a[ ], int Left, int Right ){ if ( Left >= Right) //说明已经不能再divide了 return; int i = Left, j = Right; T pivot = a[ Left ]; //选最左端点为pivot while ( i < j ) { while ( i < j && a[ j ] >= pivot ) //这里需要 i < j 为了控制不过界 --j; //当a[ j ]比pivot大时，继续递减，直到减到不满足条件 a[ i ] = a[ j ]; //把 j 位置上的值赋给 i ，而第一个i正是pivot while ( i < j && a[i] >= pivot ) ++i; a[ j ] = a[ i ]; //继上，把这个i赋给j上一次的位置，很巧妙吧 } a[ i ] = pivot; Qsort( a, Left, i - 1 ); Qsort( a, i + 1, Right ); //分别去i-1和i+1，跳过i}简单分析一下，1）为什么要从j开始计算呢？因为我们把pivot设在了最左端，这个位置一定要当作第一个被交换的位置，才能保证程序的顺利运行（所以如果pivot在最右端，你会了吗？）。2）为什么最后是a[ i ] = pivot;结尾呢？很简单，回到程序，我们先从j计算，再计算i的移动，那么很显然是把i的位置和pivot交换啊~~不过，正如很多书上所说（就当是吧），因为现实中很多序列并不是完全无序的，取第一个比较冒险，有可能出现最差解，所以有以下2种取法：1.随机（我感觉挺好的，他们说计算量耗费大）。2.3数取中值：就是第1，最后，中间3个元素取他们的中值作为pivot。实现方法很简单：void mid3( T a[], int L, int R ){ int C = ( L + R ) / 2; if ( a[ L ] > a[ C ] ) swap( a[ C ], a[ L ] ); if ( a[ C ] > a[ R ] ) swap( a[ C ], a[ R ] ); if ( a[ R ] > a[ L ] ) swap( a[ R ], a[ L ] ); swap( a[ C ], a[ Left + 1 ] ); return a[ Left + 1 ] ;}先讲结果：分别把左中右3个数排序，然后把中数放到第2个位置。当然调用的时候也需稍作调整，此处不再赘述。一个不需要注意的地方是：这3个数比较并无特别的规则，只需要两两比较就好了（C32=3而已）。时间复杂度我就不证了，最坏是O(n2)，当每次pivot都取第一个的时候。堆排序我们先不讲了，等到聊到优先队列的时候再说吧。那么，我们第一个话题似乎就结束了~~BTW，你有没有觉得用c++写这段代码好多啊，要不然，我们用python大概写一下？def qsort(a): if len(a) <= 1: return a pivot = a[len(a)//2] # 使用py3.x，2.x的话不需要// left = [x for x in a if x < pivot] mid = [x for x in a if x == pivot] right = [x for x in a if x > pivot] return qsort(left) + mid + qsort(right) # 已经实现一次划分了是不是有点恐怖，这么复杂的算法，仅仅不到10行······补充一个Python版普通实现：def quick_sort(array, l, r): if l < r: q = partition(array, l, r) quick_sort(array, l, q - 1) quick_sort(array, q + 1, r) def partition(array, l, r): x = array[r] i = l - 1 for j in range(l, r): if array[j] <= x: i += 1 array[i], array[j] = array[j], array[i] array[i + 1], array[r] = array[r], array[i+1] return i + 1作者：吃个小烧饼链接：https://www.jianshu.com/p/bad507d62f08来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 使用HashSet判断主键是否存在 HashSet 实现 Set 接口，由哈希表（实际上是 HashMap ）实现，但不保证 set 的迭代顺序，并允许使用 null 元素。HashSet 的时间复杂度跟 HashMap 一致，如果没有哈希冲突则时间复杂度为 O(1) ，如果存在哈希冲突则时间复杂度不超过 O(n) 。所以，在日常编码中，可以使用 HashSet 判断主键是否存在。  案例：给定一个字符串(不一定全为字母)，请返回第一个重复出现的字符。  /** 查找第一个重复字符 */ public static char findFirstRepeatedChar(String string) {     // 检查空字符串     if (Objects.isNull(string) || string.isEmpty()) {         return null;     }       // 查找重复字符     char[] charArray = string.toCharArray();     Set charSet = new HashSet<>(charArray.length);     for (char ch : charArray) {         if (charSet.contains(ch)) {             return ch;         }         charSet.add(ch);     }       // 默认返回为空     return null; }  复制  其中，由于 Set 的 add 函数有个特性——如果添加的元素已经再集合中存在，则会返回 false 。可以简化代码为：  if (!charSet.add(ch)) {     return ch; } 复制  使用HashMap存取键值映射关系 简单来说，HashMap 由数组和链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。如果定位到的数组位置不含链表，那么查找、添加等操作很快，仅需一次寻址即可，其时间复杂度为 O(1) ；如果定位到的数组包含链表，对于添加操作，其时间复杂度为 O(n) ——首先遍历链表，存在即覆盖，不存在则新增；对于查找操作来讲，仍需要遍历链表，然后通过key对象的 equals 方法逐一对比查找。从性能上考虑， HashMap 中的链表出现越少，即哈希冲突越少，性能也就越好。所以，在日常编码中，可以使用 HashMap 存取键值映射关系。  案例：给定菜单记录列表，每条菜单记录中包含父菜单标识（根菜单的父菜单标识为 null ），构建出整个菜单树。  /** 菜单DO类 */ @Setter @Getter @ToString public static class MenuDO {     /** 菜单标识 */     private Long id;     /** 菜单父标识 */     private Long parentId;     /** 菜单名称 */     private String name;     /** 菜单链接 */     private String url; }   /** 菜单VO类 */ @Setter @Getter @ToString public static class MenuVO {     /** 菜单标识 */     private Long id;     /** 菜单名称 */     private String name;     /** 菜单链接 */     private String url;     /** 子菜单列表 */     private List<MenuVO> childList; }   /** 构建菜单树函数 */ public static List<MenuVO> buildMenuTree(List<MenuDO> menuList) {     // 检查列表为空     if (CollectionUtils.isEmpty(menuList)) {         return Collections.emptyList();     }       // 依次处理菜单     int menuSize = menuList.size();     List<MenuVO> rootList = new ArrayList<>(menuSize);     Map<Long, MenuVO> menuMap = new HashMap<>(menuSize);     for (MenuDO menuDO : menuList) {         // 赋值菜单对象         Long menuId = menuDO.getId();         MenuVO menu = menuMap.get(menuId);         if (Objects.isNull(menu)) {             menu = new MenuVO();             menu.setChildList(new ArrayList<>());             menuMap.put(menuId, menu);         }         menu.setId(menuDO.getId());         menu.setName(menuDO.getName());         menu.setUrl(menuDO.getUrl());           // 根据父标识处理         Long parentId = menuDO.getParentId();         if (Objects.nonNull(parentId)) {             // 构建父菜单对象             MenuVO parentMenu = menuMap.get(parentId);             if (Objects.isNull(parentMenu)) {                 parentMenu = new MenuVO();                 parentMenu.setId(parentId);                 parentMenu.setChildList(new ArrayList<>());                 menuMap.put(parentId, parentMenu);             }                          // 添加子菜单对象             parentMenu.getChildList().add(menu);         } else {             // 添加根菜单对象             rootList.add(menu);         }     }       // 返回根菜单列表     return rootList; }  复制  使用 ThreadLocal 存储线程专有对象 ThreadLocal 提供了线程专有对象，可以在整个线程生命周期中随时取用，极大地方便了一些逻辑的实现。  常见的 ThreadLocal 用法主要有两种：  1、保存线程上下文对象，避免多层级参数传递；  2、保存非线程安全对象，避免多线程并发调用。  保存线程上下文对象，避免多层级参数传递 这里，以 PageHelper 插件的源代码中的分页参数设置与使用为例说明。  设置分页参数代码：  /** 分页方法类 */ public abstract class PageMethod {     /** 本地分页 */     protected static final ThreadLocal<Page> LOCAL_PAGE = new ThreadLocal<Page>();       /** 设置分页参数 */     protected static void setLocalPage(Page page) {         LOCAL_PAGE.set(page);     }       /** 获取分页参数 */     public static <T> Page<T> getLocalPage() {         return LOCAL_PAGE.get();     }       /** 开始分页 */     public static <E> Page<E> startPage(int pageNum, int pageSize, boolean count, Boolean reasonable, Boolean pageSizeZero) {         Page<E> page = new Page<E>(pageNum, pageSize, count);         page.setReasonable(reasonable);         page.setPageSizeZero(pageSizeZero);         Page<E> oldPage = getLocalPage();         if (oldPage != null && oldPage.isOrderByOnly()) {             page.setOrderBy(oldPage.getOrderBy());         }         setLocalPage(page);         return page;     } }  复制  使用分页参数代码：  /** 虚辅助方言类 */ public abstract class AbstractHelperDialect extends AbstractDialect implements Constant {     /** 获取本地分页 */     public <T> Page<T> getLocalPage() {         return PageHelper.getLocalPage();     }       /** 获取分页SQL */     @Override     public String getPageSql(MappedStatement ms, BoundSql boundSql, Object parameterObject, RowBounds rowBounds, CacheKey pageKey) {         String sql = boundSql.getSql();         Page page = getLocalPage();         String orderBy = page.getOrderBy();         if (StringUtil.isNotEmpty(orderBy)) {             pageKey.update(orderBy);             sql = OrderByParser.converToOrderBySql(sql, orderBy);         }         if (page.isOrderByOnly()) {             return sql;         }         return getPageSql(sql, page, pageKey);     }     ... }  复制  使用分页插件代码：  /** 查询用户函数 */ public PageInfo<UserDO> queryUser(UserQuery userQuery, int pageNum, int pageSize) {  PageHelper.startPage(pageNum, pageSize);  List<UserDO> userList = userDAO.queryUser(userQuery);  PageInfo<UserDO> pageInfo = new PageInfo<>(userList);  return pageInfo; } 复制  如果要把分页参数通过函数参数逐级传给查询语句，除非修改 MyBatis 相关接口函数，否则是不可能实现的。  保存非线程安全对象，避免多线程并发调用 在写日期格式化工具函数时，首先想到的写法如下：  /** 日期模式 */ private static final String DATE_PATTERN = "yyyy-MM-dd";   /** 格式化日期函数 */ public static String formatDate(Date date) {     return new SimpleDateFormat(DATE_PATTERN).format(date); } 复制  其中，每次调用都要初始化 DateFormat 导致性能较低，把 DateFormat 定义成常量后的写法如下：  /** 日期格式 */ private static final DateFormat DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd");   /** 格式化日期函数 */ public static String formatDate(Date date) {     return DATE_FORMAT.format(date); } 复制  由于 SimpleDateFormat 是非线程安全的，当多线程同时调用 formatDate 函数时，会导致返回结果与预期不一致。如果采用 ThreadLocal 定义线程专有对象，优化后的代码如下：  /** 本地日期格式 */ private static final ThreadLocal<DateFormat> LOCAL_DATE_FORMAT = new ThreadLocal<DateFormat>() {     @Override     protected DateFormat initialValue() {         return new SimpleDateFormat("yyyy-MM-dd");     } };   /** 格式化日期函数 */ public static String formatDate(Date date) {     return LOCAL_DATE_FORMAT.get().format(date); } 复制  这是在没有线程安全的日期格式化工具类之前的实现方法。在 JDK8 以后，建议使用 DateTimeFormatter 代替 SimpleDateFormat ，因为 SimpleDateFormat 是线程不安全的，而 DateTimeFormatter 是线程安全的。当然，也可以采用第三方提供的线程安全日期格式化函数，比如 apache 的 DateFormatUtils 工具类。  注意：ThreadLocal 有一定的内存泄露的风险，尽量在业务代码结束前调用 remove 函数进行数据清除。  使用 Pair 实现成对结果的返回 在 C/C++ 语言中， Pair （对）是将两个数据类型组成一个数据类型的容器，比如 std::pair 。  Pair 主要有两种用途：  1、把 key 和 value 放在一起成对处理，主要用于 Map 中返回名值对，比如 Map 中的 Entry 类；  2、当一个函数需要返回两个结果时，可以使用 Pair 来避免定义过多的数据模型类。  第一种用途比较常见，这里主要说明第二种用途。  定义模型类实现成对结果的返回 函数实现代码：  /** 点和距离类 */ @Setter @Getter @ToString @AllArgsConstructor public static class PointAndDistance {     /** 点 */     private Point point;     /** 距离 */     private Double distance; }   /** 获取最近点和距离 */ public static PointAndDistance getNearestPointAndDistance(Point point, Point[] points) {     // 检查点数组为空     if (ArrayUtils.isEmpty(points)) {         return null;     }       // 获取最近点和距离     Point nearestPoint = points[0];     double nearestDistance = getDistance(point, points[0]);     for (int i = 1; i < points.length; i++) {         double distance = getDistance(point, point[i]);         if (distance < nearestDistance) {             nearestDistance = distance;             nearestPoint = point[i];         }     }       // 返回最近点和距离     return new PointAndDistance(nearestPoint, nearestDistance); }  复制  函数使用案例：  Point point = ...; Point[] points = ...; PointAndDistance pointAndDistance = getNearestPointAndDistance(point, points); if (Objects.nonNull(pointAndDistance)) {     Point point = pointAndDistance.getPoint();     Double distance = pointAndDistance.getDistance();     ... } 复制  使用 Pair 类实现成对结果的返回 在 JDK 中，没有提供原生的 Pair 数据结构，也可以使用 Map::Entry 代替。不过， Apache 的 commons-lang3 包中的 Pair 类更为好用，下面便以 Pair 类进行举例说明。  函数实现代码：  /** 获取最近点和距离 */ public static Pair<Point, Double> getNearestPointAndDistance(Point point, Point[] points) {     // 检查点数组为空     if (ArrayUtils.isEmpty(points)) {         return null;     }       // 获取最近点和距离     Point nearestPoint = points[0];     double nearestDistance = getDistance(point, points[0]);     for (int i = 1; i < points.length; i++) {         double distance = getDistance(point, point[i]);         if (distance < nearestDistance) {             nearestDistance = distance;             nearestPoint = point[i];         }     }       // 返回最近点和距离     return Pair.of(nearestPoint, nearestDistance); }  复制  函数使用案例：  Point point = ...; Point[] points = ...; Pair<Point, Double> pair = getNearestPointAndDistance(point, points); if (Objects.nonNull(pair)) {     Point point = pair.getLeft();     Double distance = pair.getRight();     ... } 复制  定义 Enum 类实现取值和描述 在 C++、Java 等计算机编程语言中，枚举类型（Enum）是一种特殊数据类型，能够为一个变量定义一组预定义的常量。在使用枚举类型的时候，枚举类型变量取值必须为其预定义的取值之一。  用 class 关键字实现的枚举类型 在 JDK5 之前， Java 语言不支持枚举类型，只能用类（class）来模拟实现枚举类型。  /** 订单状态枚举 */ public final class OrderStatus {     /** 属性相关 */     /** 状态取值 */     private final int value;     /** 状态描述 */     private final String description;       /** 常量相关 */     /** 已创建(1) */     public static final OrderStatus CREATED = new OrderStatus(1, "已创建");     /** 进行中(2) */     public static final OrderStatus PROCESSING = new OrderStatus(2, "进行中");     /** 已完成(3) */     public static final OrderStatus FINISHED = new OrderStatus(3, "已完成");       /** 构造函数 */     private OrderStatus(int value, String description) {         this.value = value;         this.description = description;     }       /** 获取状态取值 */     public int getValue() {         return value;     }       /** 获取状态描述 */     public String getDescription() {         return description;     } }  复制  用 enum 关键字实现的枚举类型 JDK5 提供了一种新的类型—— Java 的枚举类型，关键字 enum 可以将一组具名的值的有限集合创建为一种新的类型，而这些具名的值可以作为常量使用，这是一种非常有用的功能。  /** 订单状态枚举 */ public enum OrderStatus {     /** 常量相关 */     /** 已创建(1) */     CREATED(1, "已创建"),     /** 进行中(2) */     PROCESSING(2, "进行中"),     /** 已完成(3) */     FINISHED(3, "已完成");       /** 属性相关 */     /** 状态取值 */     private final int value;     /** 状态描述 */     private final String description;       /** 构造函数 */     private OrderStatus(int value, String description) {         this.value = value;         this.description = description;     }       /** 获取状态取值 */     public int getValue() {         return value;     }       /** 获取状态描述 */     public String getDescription() {         return description;     } }  复制  其实，Enum 类型就是一个语法糖，编译器帮我们做了语法的解析和编译。通过反编译，可以看到 Java 枚举编译后实际上是生成了一个类，该类继承了 java.lang.Enum<E> ，并添加了 values()、valueOf() 等枚举类型通用方法。  定义 Holder 类实现参数的输出 在很多语言中，函数的参数都有输入（in）、输出（out）和输入输出（inout）之分。在 C/C++ 语言中，可以用对象的引用（&）来实现函数参数的输出（out）和输入输出（inout）。但在 Java 语言中，虽然没有提供对象引用类似的功能，但是可以通过修改参数的字段值来实现函数参数的输出（out）和输入输出（inout）。这里，我们叫这种输出参数对应的数据结构为Holder（支撑）类。  Holder 类实现代码：  /** 长整型支撑类 */ @Getter @Setter @ToString public class LongHolder {     /** 长整型取值 */     private long value;       /** 构造函数 */     public LongHolder() {}       /** 构造函数 */     public LongHolder(long value) {         this.value = value;     } }  复制  Holder 类使用案例：  /** 静态常量 */ /** 页面数量 */ private static final int PAGE_COUNT = 100; /** 最大数量 */ private static final int MAX_COUNT = 1000;     /** 处理过期订单 */ public void handleExpiredOrder() {   LongHolder minIdHolder = new LongHolder(0L);     for (int pageIndex = 0; pageIndex < PAGE_COUNT; pageIndex++) {         if (!handleExpiredOrder(pageIndex, minIdHolder)) {           break;         }     } }     /** 处理过期订单 */ private boolean handleExpiredOrder(int pageIndex, LongHolder minIdHolder) {   // 获取最小标识   Long minId = minIdHolder.getValue();       // 查询过期订单(按id从小到大排序)   List<OrderDO> orderList = orderDAO.queryExpired(minId, MAX_COUNT);   if (CollectionUtils.isEmpty(taskTagList)) {     return false;   }       // 设置最小标识   int orderSize = orderList.size();   minId = orderList.get(orderSize - 1).getId();   minIdHolder.setValue(minId);       // 依次处理订单    for (OrderDO order : orderList) {        ...     }       // 判断还有订单   return orderSize >= PAGE_SIZE; }  复制  其实，可以实现一个泛型支撑类，适用于更多的数据类型。  定义 Union 类实现数据体的共存 在 C/C++ 语言中，联合体（union），又称共用体，类似结构体（struct）的一种数据结构。联合体（union）和结构体（struct）一样，可以包含很多种数据类型和变量，两者区别如下：  1、结构体（struct）中所有变量是“共存”的，同时所有变量都生效，各个变量占据不同的内存空间；  2、联合体（union）中是各变量是“互斥”的，同时只有一个变量生效，所有变量占据同一块内存空间。  当多个数据需要共享内存或者多个数据每次只取其一时，可以采用联合体（union）。  在Java语言中，没有联合体（union）和结构体（struct）概念，只有类（class）的概念。众所众知，结构体（struct）可以用类（class）来实现。其实，联合体（union）也可以用类（class）来实现。但是，这个类不具备“多个数据需要共享内存”的功能，只具备“多个数据每次只取其一”的功能。  这里，以微信协议的客户消息为例说明。根据我多年来的接口协议封装经验，主要有以下两种实现方式。  使用函数方式实现 Union Union 类实现:  /** 客户消息类 */ @ToString public class CustomerMessage {       /** 属性相关 */     /** 消息类型 */     private String msgType;     /** 目标用户 */     private String toUser;       /** 共用体相关 */     /** 新闻内容 */     private News news;     ...       /** 常量相关 */     /** 新闻消息 */     public static final String MSG_TYPE_NEWS = "news";     ...       /** 构造函数 */     public CustomerMessage() {}       /** 构造函数 */     public CustomerMessage(String toUser) {         this.toUser = toUser;     }       /** 构造函数 */     public CustomerMessage(String toUser, News news) {         this.toUser = toUser;         this.msgType = MSG_TYPE_NEWS;         this.news = news;     }       /** 清除消息内容 */     private void removeMsgContent() {         // 检查消息类型         if (Objects.isNull(msgType)) {             return;         }           // 清除消息内容         if (MSG_TYPE_NEWS.equals(msgType)) {             news = null;         } else if (...) {         ...         }         msgType = null;     }       /** 检查消息类型 */     private void checkMsgType(String msgType) {         // 检查消息类型         if (Objects.isNull(msgType)) {             throw new IllegalArgumentException("消息类型为空");         }           // 比较消息类型         if (!Objects.equals(msgType, this.msgType)) {             throw new IllegalArgumentException("消息类型不匹配");         }     }       /** 设置消息类型函数 */     public void setMsgType(String msgType) {         // 清除消息内容         removeMsgContent();           // 检查消息类型         if (Objects.isNull(msgType)) {             throw new IllegalArgumentException("消息类型为空");         }           // 赋值消息内容         this.msgType = msgType;         if (MSG_TYPE_NEWS.equals(msgType)) {             news = new News();         } else if (...) {         ...               } else {             throw new IllegalArgumentException("消息类型不支持");         }     }       /** 获取消息类型 */     public String getMsgType() {         // 检查消息类型         if (Objects.isNull(msgType)) {             throw new IllegalArgumentException("消息类型无效");         }           // 返回消息类型         return this.msgType;     }       /** 设置新闻 */     public void setNews(News news) {         // 清除消息内容         removeMsgContent();           // 赋值消息内容         this.msgType = MSG_TYPE_NEWS;         this.news = news;     }       /** 获取新闻 */     public News getNews() {         // 检查消息类型         checkMsgType(MSG_TYPE_NEWS);           // 返回消息内容         return this.news;     }          ... }  复制  Union 类使用:  String accessToken = ...; String toUser = ...; List<Article> articleList = ...; News news = new News(articleList); CustomerMessage customerMessage = new CustomerMessage(toUser, news); wechatApi.sendCustomerMessage(accessToken, customerMessage); 复制  主要优缺点:  优点：更贴近 C/C++ 语言的联合体（union）； 缺点：实现逻辑较为复杂，参数类型验证较多。 使用继承方式实现 Union Union 类实现:  /** 客户消息类 */ @Getter @Setter @ToString public abstract class CustomerMessage {     /** 属性相关 */     /** 消息类型 */     private String msgType;     /** 目标用户 */     private String toUser;       /** 常量相关 */     /** 新闻消息 */     public static final String MSG_TYPE_NEWS = "news";     ...       /** 构造函数 */     public CustomerMessage(String msgType) {         this.msgType = msgType;     }       /** 构造函数 */     public CustomerMessage(String msgType, String toUser) {         this.msgType = msgType;         this.toUser = toUser;     } }   /** 新闻客户消息类 */ @Getter @Setter @ToString(callSuper = true) public class NewsCustomerMessage extends CustomerMessage {       /** 属性相关 */     /** 新闻内容 */     private News news;       /** 构造函数 */     public NewsCustomerMessage() {         super(MSG_TYPE_NEWS);     }       /** 构造函数 */     public NewsCustomerMessage(String toUser, News news) {         super(MSG_TYPE_NEWS, toUser);         this.news = news;     } }  复制  Union 类使用:  String accessToken = ...; String toUser = ...; List<Article> articleList = ...; News news = new News(articleList); CustomerMessage customerMessage = new NewsCustomerMessage(toUser, news); wechatApi.sendCustomerMessage(accessToken, customerMessage); 复制  主要优缺点:  优点：使用虚基类和子类进行拆分，各个子类对象的概念明确； 缺点：与 C/C++ 语言的联合体（union）差别大，但是功能上大体一致。 在 C/C++ 语言中，联合体并不包括联合体当前的数据类型。但在上面实现的 Java 联合体中，已经包含了联合体对应的数据类型。所以，从严格意义上说， Java 联合体并不是真正的联合体，只是一个具备“多个数据每次只取其一”功能的类。  使用泛型屏蔽类型的差异性 在 C++ 语言中，有个很好用的模板（template）功能，可以编写带有参数化类型的通用版本，让编译器自动生成针对不同类型的具体版本。而在 Java 语言中，也有一个类似的功能叫泛型（generic）。在编写类和方法的时候，一般使用的是具体的类型，而用泛型可以使类型参数化，这样就可以编写更通用的代码。  许多人都认为， C++ 模板（template）和 Java 泛型（generic）两个概念是等价的，其实实现机制是完全不同的。 C++ 模板是一套宏指令集，编译器会针对每一种类型创建一份模板代码副本； Java 泛型的实现基于"类型擦除"概念，本质上是一种进行类型限制的语法糖。  泛型类 以支撑类为例，定义泛型的通用支撑类：  /** 通用支撑类 */ @Getter @Setter @ToString public class GenericHolder<T> {     /** 通用取值 */     private T value;       /** 构造函数 */     public GenericHolder() {}       /** 构造函数 */     public GenericHolder(T value) {         this.value = value;     } }  复制  泛型接口 定义泛型的数据提供者接口：  /** 数据提供者接口 */ public interface DataProvider<T> {     /** 获取数据函数 */     public T getData(); } 复制  泛型方法 定义泛型的浅拷贝函数：  /** 浅拷贝函数 */ public static <T> T shallowCopy(Object source, Class<T> clazz) throws BeansException {     // 判断源对象     if (Objects.isNull(source)) {         return null;     }       // 新建目标对象     T target;     try {         target = clazz.newInstance();     } catch (Exception e) {         throw new BeansException("新建类实例异常", e);     }       // 拷贝对象属性     BeanUtils.copyProperties(source, target);       // 返回目标对象     return target; }  复制  泛型通配符 泛型通配符一般是使用"？"代替具体的类型实参，可以把"？"看成所有类型的父类。当具体类型不确定的时候，可以使用泛型通配符 "？"；当不需要使用类型的具体功能，只使用Object类中的功能时，可以使用泛型通配符 "？"。  /** 打印取值函数 */ public static void printValue(GenericHolder<?> holder) {     System.out.println(holder.getValue()); } /** 主函数 */ public static void main(String[] args) {     printValue(new GenericHolder<>(12345));     printValue(new GenericHolder<>("abcde")); } 复制  在 Java 规范中，不建议使用泛型通配符"？"，上面函数可以改为：  /** 打印取值函数 */ public static <T> void printValue(GenericHolder<T> holder) {     System.out.println(holder.getValue()); } 复制  泛型上下界 在使用泛型的时候，我们还可以为传入的泛型类型实参进行上下界的限制，如：类型实参只准传入某种类型的父类或某种类型的子类。泛型上下界的声明，必须与泛型的声明放在一起 。  上界通配符（extends）：  上界通配符为 ”extends ”，可以接受其指定类型或其子类作为泛参。其还有一种特殊的形式，可以指定其不仅要是指定类型的子类，而且还要实现某些接口。例如： List<? extends A> 表明这是 A 某个具体子类的 List ，保存的对象必须是A或A的子类。对于 List<? extends A> 列表，不能添加 A 或 A 的子类对象，只能获取A的对象。  下界通配符（super）：  下界通配符为”super”，可以接受其指定类型或其父类作为泛参。例如：List<? super A> 表明这是 A 某个具体父类的 List ，保存的对象必须是 A 或 A 的超类。对于 List<? super A> 列表，能够添加 A 或 A 的子类对象，但只能获取 Object 的对象。  PECS（Producer Extends Consumer Super）原则：作为生产者提供数据（往外读取）时，适合用上界通配符（extends）；作为消费者消费数据（往里写入）时，适合用下界通配符（super）。  在日常编码中，比较常用的是上界通配符（extends），用于限定泛型类型的父类。例子代码如下：  /** 数字支撑类 */ @Getter @Setter @ToString public class NumberHolder<T extends Number> {     /** 通用取值 */     private T value;       /** 构造函数 */     public NumberHolder() {}       /** 构造函数 */     public NumberHolder(T value) {         this.value = value;     } }   /** 打印取值函数 */ public static <T extends Number> void printValue(GenericHolder<T> holder) {     System.out.println(holder.getValue()); }  ———————————————— 版权声明：本文为CSDN博主「栾还是恋」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/2301_78008478/article/details/131367225 

依赖倒置，控制反转，依赖注入及Google Guice1. 依赖倒置依赖字面意思事物之间具有的一种关系。在面向对象编程中我将其理解为一种对象之间引用的持有关系。任何系统都无法避免依赖，如果一个类或接口在系统中没有被依赖，那么他们就不应该出现在系统之中。举个简单的例子说明依赖关系：师徒四人去西天取经。我们说说唐僧，他有个徒弟，其他的东西我们暂且忽略。如果把唐僧师徒一个具体类的话，他在收服了悟空之后应该有这样的依赖关系。我们从唐僧角度考虑的话，他应该是依赖于悟空的，没有他，他可取不到经。那么我们可以说唐僧依赖于他的徒弟。在代码中，他们的关系如下：public class TangSeng { WuKong wuKong = new WuKong();}有了徒弟，唐僧就可以跟他愉快地取经了。中途遇到妖怪，也可以让徒弟去打妖怪了。public class TangSeng { WuKong wuKong = new WuKong(); public void letsFight(String name) { wuKong.fight(); }}那么问题了，唐僧在后面还会收徒弟。当他收齐之后情况应该是这样的。这里他就依赖于四个徒弟了，也就是说徒弟越多，他的依赖就越多。依赖多的话会产生什么影响呢？首先，遇到妖怪了，让谁出场是个问题了，总不能天天让一个人吃苦，这就不是一个好的领导了。所以，出战的方法也得修改。public class TangSeng { WuKong wuKong = new WuKong(); BaJie baJie = new BaJie(); LaoSha laoSha = new LaoSha(); XiaoBaiLong xiaoBaiLong = new XiaoBaiLong(); public void letsFight(String name) { if (name.equals("wuKong")) { wuKong.fight(); } else if (name.equals("baJie")) { baJie.fight(); } else if (name.equals("laoSha")) { laoSha.fight(); } else { runAway(); } } private void runAway() { System.out.println("Bye Bye ~"); }}这里代码量虽然只稍微上来一点，但是我们得看到更本质的东西。徒弟每增加一个徒弟，唐僧的依赖就会多一个，对应的代码可能就得修改一下。而且，唐僧直接依赖于具体的徒弟类，如果某个徒弟除了问题，那唐僧是不是也可能会出问题。因为他有一个具体的徒弟类，而且还会调用到具体的方法。这种耦合性比较高的代码，后期维护起来会比较糟糕，修改一个地方，其他地方可能也要跟着做很多更改。所以我们需要换个角度考虑一下。依赖倒置上面分析了问题出现在什么地方。主要是类之间直接的依赖关系导致的高耦合，那么要如何改变这种依赖关系呢？这就要改变我们思考的方式了，我们应该更多的依赖于接口（广泛概念上的接口）而不是具体的类，即要依赖于接口，而不是依赖于具体。无论是悟空，八戒还是沙僧，他们对于唐僧而言都是徒弟。我们可以将徒弟抽象成一个接口。如下：这里，具体类之间的直接依赖关系就被改变了。由类与具体类之间的依赖，转换成了类与接口之间的依赖。即唐僧类依赖于TuDi接口，而四个徒弟也依赖于TuDi接口，他们实现了接口。从上往下的依赖关系，在TuDi与徒弟实现类这里发生了改变，成了徒弟向上依赖于TuDi接口。这种倒置，就是依赖倒置。下面看看这种倒置对代码产生的影响：public class TangSeng { List<TuDi> ts = new ArrayList<TuDi>(); public TangSeng(List<TuDi> ts) { this.ts = ts; } public void letsFight(TuDi tudi) { tudi.fight(); }}实例化的语句没有了，具体类和实例对象也没有了。TuDi的具体实现对于唐生而言已经无所谓了，能打就行了。2. 控制反转（IOC）继续用上面的例子分析。我们知道师徒四人会遇到妖怪，但是遇到的妖怪是哪个？跟谁打？这个我们可能没法确定，但是在代码实现时，如果需要指定他们要面对的妖怪，我们可能就要在类中实例化这个妖怪了。public class TangSeng { List<TuDi> ts = new ArrayList<TuDi>(); LionMonster lion = new LionMonster(); public TangSeng(List<TuDi> ts) { this.ts = ts; } public void letsFight(TuDi tudi) { tudi.fight(lion); }}这里就等于写死了，他们只会跟狮子怪干架。妖怪是应用程序自己主动指定创建的。如果我们更改这种模式，他们跟哪个妖怪打架可以动态改变，由其他的配置控制。就是我们可以在需要的时候，将对象实例传递过去，这是被动的过程。这种由主动变成被动的方式，就是我理解中的反转控制。 具体的实现可能有多种方式，反射就是一种比较经典的实现。public class TangSeng { List<TuDi> ts = new ArrayList<TuDi>(); Property pro = new Property(); public TangSeng(List<TuDi> ts) { this.ts = ts; } public Monster getMonster() { Class monsterClass = Class.forName(pro.getClassName()); return monsterClass.newInstance(); } public void letsFight(TuDi tudi) { tudi.fight(getMonster); }}pro.getClassName()返回的值，可以通过配置文件更改成指定的类。3. 依赖注入(Dependency injection)注入我们再看看唐僧类中妖怪战斗的方法，圣僧是铁定上不了场的，这里我们是通过接口声明参数的，但是当真正调用方法的时候，这个地方肯定是要有个具体的徒弟实现类。所以问题就是这个徒弟怎么来。通过上面的讨论我们已经有两种方法可以实现了。其一，在代码中直接实例化好，然后传入对象，可以是通过工厂返回的对象。其二，通过配置文件指定徒弟类，在运行时动态生成徒弟类。后者变是反转控制的一种实现。反转控制是一个概念，他具体的实现方式可能有很多种。大部分场景是通过IOC容器，根据配置文件来实现注入。Druid的依赖注入都是通过Google Guice实现的，所以这里简单介绍一下它。4. Google GuiceGoogle Guice 是一款轻量级的依赖注入框架。<dependency> <groupId>com.google.inject</groupId> <artifactId>guice </artifactId> <version>4.1.0</version> </dependency> <dependency> <groupId>aopalliance</groupId> <artifactId>aopalliance</artifactId> <version>1.0</version></dependency>4.1 使用实例场景1：唐僧被妖怪抓走了，大师兄刚刚化缘回来。各位师兄弟的反应如下，沙僧：大师兄！师父被妖怪抓走了！！八戒：分行李吧！！悟空：我去看看是哪路妖怪，如此胆大！！于是，悟空出发了！！以下是悟空类，悟空多了一个拯救师父的任务public class Wukong implements Tudi { private String name = "wukong"; private Skill skill; public void toSaveMaster(){ //悟空使用它的技能(skill)对付妖怪 skill.Effect(); } @Override public void fight(Monster monster) { System.out.println("WuKong is fighting with " + monster); }}那我们知道悟空会很多的法术，妖怪也是千奇百怪，所以要对症下药，选择正确的技能才能在损失最小的情况下快速地救出师傅。那这里的技能就又要用我们上面的思想来处理了：//把Skill定义为一个接口public interface Skill { public void Effect();} //下面是悟空的几个技能class Fire implements Skill{ @Override public void Effect() { System.out.println("悟空在喷火！！对敌方造成火属性伤害100"); }}class Water implements Skill{ @Override public void Effect() { System.out.println("哇！！悟空在喷水！！对敌方造成水属性伤害100"); }}class Wind implements Skill{ @Override public void Effect() { System.out.println("悟空在刮风！！对敌方造成风属性伤害100"); }}这里我们知道了悟空会法术(Skill接口)，还知道了他的技能清单(Skill的实现类)。接下来就是根据地方选择正确的技能了。例如对面是白骨精，那我们就选择喷水技能打伤害吧(我也不知道为什么，感觉会很有效！)。那我们要做的就是把悟空的技能接口和接口的实现类Water绑定到一起。不使用框架的操作。Wukong wukong = new Wukong(); wukong.skill=new Water();使用Guice，需要做的步骤如下：1. 创建接口；2. 接口实现；3. 将接口和实现类绑定； 4. 创建接口实例。前两步已经在上面的代码中完成了，接口为Skill，实现类就是喷火、喷水、刮风。接下来我们进行接口的绑定。步骤三：将接口和实现类绑定public class SkillModule implements Module { @Override public void configure(Binder binder) { binder.bind(Skill.class).to(Water.class); } //接口和实现类绑定的一种方式就是通过实现配置模块，实现其config方法来完成。这种绑定关系，我们也可以通过配置文件指定。步骤四：创建接口的实例public static void main(String[] args) { //将配置传入 Injector injector = Guice.createInjector(new SkillModule()); skill = injector.getInstance(Skill.class); Wukong wukong = new Wukong(); wukong.skill=skill; wukong.toSaveMaster(); } 运行结果如下： 哇！！悟空在喷水！！对敌方造成水属性伤害1004.2 Guice中的注解@ImplementedBy：用于注解接口，直接指定接口的实现类而不需要在Module中实现接口的绑定；Demo//定义接口时即指定其实现类为Water@ImplementedBy(Water.class)public interface Skill { public void Effect();}在Main方法中的代码也做相应的更改：public static void main(String[] args) { Injector injector = Guice.createInjector(); skill = injector.getInstance(Skill.class); Wukong wukong = new Wukong(); wukong.skill=skill; wukong.toSaveMaster(); }运行结果一样，但是整个代码工程中少了配置module的过程。但是谁又能在定义接口时就知道其实现类呢，我觉得用处不是特别大。@Inject:使用该注解，可以将对象实例直接注入到一个对其依赖的类中。可以用在某个类的构造方法中：Demopublic class Wukong implements Tudi { private static String name = "wukong"; private static Skill skill; @Inject public Wukong(Skill skill) { this.skill = skill; } public void toSaveMaster(){ skill.Effect(); } @Override public void fightMonster() { System.out.println("WuKong is fighting !!"); }}Main方法也变了public static void main(String[] args) { Injector injector = Guice.createInjector(); Wukong wukong = injector.getInstance(Wukong.class); wukong.toSaveMaster(); }运行结果一样。@Singleton用来注解类，可以确保调用injector.getInstance时创建的是一个单例类。@Named：当一个接口实多个绑定时可以使用该注解区分。改写SkillModule类public class SkillModule implements Module { @Override public void configure(Binder binder) { binder.bind(Skill.class).annotatedWith(Names.named("Water")).to(Water.class); binder.bind(Skill.class).annotatedWith(Names.named("Fire")).to(Fire.class); }}在看看这个注解是如何发挥作用的public static void main(String[] args) { Injector injector = Guice.createInjector(new SkillModule()); @Named("Water") Skill waterSkill = injector.getInstance(Skill.class); Wukong wukong = new Wukong(); wukong.skill = waterSkill; wukong.toSaveMaster(); @Named("Fire") Skill fireSkill = injector.getInstance(Skill.class); wukong.skill = fireSkill; wukong.toSaveMaster(); }这样就可以把一个接口绑定到多个实现类上，根据不同的Name可以创建不同的实例。但是在实际中无法通过编译，还没有看出是什么问题，所以不建议使用该注解。Guice很强大，这里只是简单记录。啥？啥是控制反转，依赖注入啊！？转自 https://zhuanlan.zhihu.com/p/96108992