在实际的项目场景中，客户端需要对数据进行判重，同时需要兼顾性能和内存消耗。
一、判重KEY单调递增一般的通信类产品，需要确保一个聊天会话里面的消息的唯一性。我们假设消息的KEY是个uint64_t的整型，而且后台确保同一个会话的消息的Seq是唯一单调递增的。为了确保消息的可靠性，后台可能不止一次将同一条消息推送下来，也就是同一个客户端可能不止一次的收到同一条消息，而且客户端不一定是按顺序接收消息。
在一个聊天会话里面，特别是群消息（比如万人群、直播群等），客户端可能存在成千上万条消息。客户端需要一种高效的方式去判重。
收到的消息Seq是唯一单调递增的，但是可能接收的顺序不是连续的。这样收到的Seq就存在非连续的情况，我们可以把其中一段连续的合并起来，作为一个范围去存储判重（只存储起始和结尾）。
实现代码//判断Seq是否重复的逻辑classDupCheker{public:staticDupChekerGetInst(){staticDupChekerdup;returndup;}/**
paramcur_seq需要被判重的seq*returnbooltrue表示seq重复，false表示seq不重复*/boolIsDup(uint64_tcur_seq){intseq_insert_range_count=0;size_tindex=-1;for(std::size_ti=0;iseq_range_list_.size();i++){SeqRangerange=seq_range_list_[i];//查找到，检测为重复,返回trueif((cur_seq=range.start_)(cur_seq=range.end_)){returntrue;}//没找到，则更新seq范围if(cur_seqrange.start_){//刚好是范围起始Seq的前一个，则更新此范围的起始Seqif(cur_seq==(range.start_-1)){range.start_=cur_seq;seq_insert_range_count++;break;}//记录当前范围的下标index=i;break;}//刚好是范围末尾的后一个，则更新此范围的末尾Seqif(cur_seq==(range.end_+1)){range.end_=cur_seq;seq_insert_range_count++;}}//如果要查找的Seq不与任何一个范围相邻，则单独作为一个范围存在。确保从小到大排序if(seq_insert_range_count==0){SeqRangerange;range.start_=cur_seq;range.end_=cur_seq;if(index!=-1){//如果要查找的Seq比某个范围的起始Seq小，则将新增范围插入该范围前面，确保seq_range_list_是从小到大排序seq_range_list_.insert(seq_range_list_.begin()+index,range);}else{//如果要查找的Seq比任何返回的Seq都大，则将新增范围插入范围列表末尾，确保seq_range_list_是从小到大排序seq_range_list_.insert(seq_range_list_.end(),range);}returnfalse;}//要查找的Seq刚好相邻两个范围，则合并这两个范围为一个if(seq_insert_range_count==2){for(std::size_ti=0;iseq_range_list_.size()-1;i++){//此时的范围列表大小肯定大于1if(seq_range_list_[i].end_!=seq_range_list_[i+1].start_){continue;}seq_range_list_[i].end_=seq_range_list_[i+1].end_;//后一个范围纳入前一个范围seq_range_list_.erase(seq_range_list_.begin()+i+1);//删掉后一个范围break;}returnfalse;}//未找到Seq，为非重复Seq，返回falsereturnfalse;}voidLog(){for(std::size_ti=0;iseq_range_list_.size();i++){SeqRangerange=seq_range_list_[i];printf("range:%lustart:%lluend:%llu\n",i,range.start_,range.end_);}}private:DupCheker()=default;~DupCheker()=default;DupCheker(constDupChekerobj)=default;DupChekeroperator=(constDupChekerobj)=default;DupCheker(DupChekerobj)=default;DupChekeroperator=(DupChekerobj)=default;typedefstructSeqRange{uint64_tstart_;uint64_tend_;}SeqRange;std::vectorSeqRangeseq_range_list_;};从上面的逻辑可以看到如果判重KEY满足单调递增，可以把KEY的范围存放内存中（范围还会自己合并更新），除非极端情况，可以不用担心内存和性能的消耗。
针对极端情况，可以做好数据上报，这种极端情况需要进一步分析解决。
二、判重KEY非单调递增，但是可排序1、内存缓存数据进行判重如果判重KEY不是单调递增，则无法使用上面的方法。STL给我们提供了一个非常方便的模板std::set用于判重。
templateclassTclassDupCheker{public:staticDupChekerGetInst(){staticDupChekerdup;returndup;}/**
paramkey需要被判重的key*returnbooltrue表示key重复，false表示key不重复*/boolIsDup(Tkey){if(key_set_.find(key)!=key_set_.end()){//找到重复的keyreturntrue;}//未找到重复的keykey_set_.insert(key);returnfalse;}private:DupCheker()=default;~DupCheker()=default;DupCheker(constDupChekerobj)=default;DupChekeroperator=(constDupChekerobj)=default;DupCheker(DupChekerobj)=default;DupChekeroperator=(DupChekerobj)=default;std::setTkey_set_;};如果数据量巨大，判重KEY全部存放在内存，这样对内存消耗会很大。此时我们可以考虑将数据存放在数据库，key_set_只存限定数量的KEY，超过一定数量就移除一半的数据，如果key_set_找不到判重KEY，则去数据库里面查找。
2、数据库辅助判重templateclassTclassDupCheker{public:staticDupChekerGetInst(){staticDupChekerdup;returndup;}/**
paramkey需要被判重的key*returnbooltrue表示key重复，false表示key不重复*/boolIsDup(Tkey){if(key_set_.find(key)!=key_set_.end()){//找到重复的keyreturntrue;}//未找到重复的key//当个数大于等于kMaxKeySize时，删除前面的一半if(key_set_.size()=kMaxKeySize){std::size_tcount=0;autoitr=key_set_.begin();while(itr!=key_set_.end()){itr=key_set_.erase(itr);count++;if(count=(kMaxKeySize/2)){break;}}}key_set_.insert(key);returndb_.IsDup(key);}private:DupCheker()=default;~DupCheker()=default;DupCheker(constDupChekerobj)=default;DupChekeroperator=(constDupChekerobj)=default;DupCheker(DupChekerobj)=default;DupChekeroperator=(DupChekerobj)=default;std::setTkey_set_;conststd::size_tkMaxKeySize=;SqliteDBTdb_;};数据库的查找逻辑省略，读者可自行实现，这个方案有个需要注意的地方，如果判重判断该数据不重复，记得将数据存入数据库，后续的判重依赖数据库。
经过优化后，没有内存消耗的问题，但是如果key_set_查找不到数据，必须查数据库，才能进一步确认key是否重复，也就是说大部分情况下都需要查数据库。
可不可以优化下呢？
3、减少数据库的操作设计的判重KEY是可排序的，std::set会自动排序，假设我们提供的类型T提供了一个排序算法，确保key_set_的存储的数据是从旧到新，超过一定数量就移除前面一半的数据，相当于把比较旧的数据清理。而我们实际的场景中，随着时间的流逝，新产生的数据都是新的，比如聊天过程中的消息，肯定先发的消息旧，后发的消息新。
这样我们可以把判重的逻辑分成三步：
在key_set_中查找key，找到说明重复，直接返回true表示key重复；找不到，进入第二步判断新来的key是不是比key_set_中最新的都新，如果是，则将key保存到key_set_，并返回false表示key不重复；如果是否，则进入第三步查找数据库，判断key是不是重复templateclassTclassDupCheker{public:staticDupChekerGetInst(){staticDupChekerdup;returndup;}DupCheker()=default;~DupCheker()=default;/**
paramkey需要被判重的key*returnbooltrue表示key重复，false表示key不重复*/boolIsDup(Tkey){if(key_set_.find(key)!=key_set_.end()){//找到重复的keyreturntrue;}//未找到重复的key//当个数大于等于kMaxKeySize时，删除前面的一半if(key_set_.size()=kMaxKeySize){std::size_tcount=0;autoitr=key_set_.begin();while(itr!=key_set_.end()){itr=key_set_.erase(itr);count++;if(count=(kMaxKeySize/2)){break;}}}//如果key比key_set_最新的数据都新，则返回不重复if((key_set_.size()0)(key(*key_set_.rbegin()))){key_set_.insert(key);returnfalse;}//查找数据库key_set_.insert(key);returndb_.IsDup(key);}private:std::setTkey_set_;conststd::size_tkMaxKeySize=;SqliteDBTdb_;};经过优化，可以减少大量的数据库操作，因为大部分要判重的数据都是新的数据，不用查找数据库，就能确认该数据是不重复的。也就是在第二步就直接返回了。
三、判重KEY不可排序剩下最后一种情况，判重KEY不可排序。这时可以采用通过内存缓存一部分数据，以及数据库判重的方式，也就是第二小节里面提到的内存缓存部分数据进行判重+数据库辅助判重。
cldz欢迎