哈希表：空间换时间的存储艺术

哈希表与散列技术散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f使得每个关键字key对应一个存储位置fkey在查找时根据这个确定的对应关系找到给定key的映射f(key)如果待查找集合中存在这个记录则必定在fkey的位置上简单来讲元素的值通过一个映射关系找到元素在表中存储的位置。我们把这种对应关系f称为散列函数又称为哈希函数。采用散列技术将记录存储在一块连续的存储空间中这块连续的存储空间称为散列表或者哈希表。优势适用于快速的查找时间复杂度O(1)。缺点占用内存空间比较大。哈希表的空间效率还是不够高。如果用哈希表存储一亿个垃圾邮件地址每个email地址对应 8bytes, 而哈希表的存储效率一般只有50%因此一个email地址需要占用16bytes. 因此一亿个email地址占用1.6GB如果存储几十亿个email address则需要上百GB的内存。除非是超级计算机一般的服务器是无法存储的。是典型的空间换时间。对于散列函数设计特点计算简单复杂会降低查找的时间散列地址分布均匀减少哈希冲突散列结构越离散越好。例如直接定址法直接用或者做个简单的线性变换后作为数组的下标数据直接存在对应下标的位置存取的时候一步算出位置就能拿到不需要额外挨个查找(适合关键字范围小、分布集中连续有时会导致内存浪费)。数字分析法(身份证后四位不同概率高)当你要存储的关键字都是很长的数字能明显看出这些数字里有些位置的数字重复率高、大家都差不多另一些位置的数字随机性强、每个人差别很大那就直接把变化大的那几位抽出来直接当这个关键字在哈希表里的存储地址这样就能大幅减少不同关键字撞到同一个地址的概率也就是哈希冲突。平方取中法取关键字key的平方后的中间部分数字作为散列地址。折叠法随机数法除留余数法不仅可以对关键字直接取模也可以折叠、平方取中法等运算之后取模。p的取值很重要一般取素数否则冲突的概率会比较大。md5、sha加密hash算法等散列冲突处理线性探测开放定址法当哈希函数计算出的地址已被占用时会顺序向后找最近空闲单元存储。二次探测二次探测是对线性探测法的改进在散列冲突位置的前后都可以查找空位置。链地址法用链表存储组织产生哈希冲突的key。将具有相同哈希地址的元素组织成一个链表(或其他线性结构)哈希表的每个槽位存储该链表的头指针。哈希表删除操作比如删除18哈希函数为除留余数法得到18的余数为4在访问第4号位元素如果不为18那么发生哈希冲突用线性探测法解决哈希冲突顺序查找下一个空闲位置存储数据。最终找到18在删除。取模操作为O(1),但产生了哈希冲突慢慢变成O(n)。哈希表的时间复杂度趋近于O(1)我们只能减少哈希冲突的概率当哈希表放的元素越来越多的时候发生冲突的概率增加。所以我们要对哈希函数进行优化对于除留余数法让哈希表(桶)的长度取素数。让哈希函数从原始数据映射到哈希表存储位置的时候能够减少哈希冲突的概率。引入哈希表的装载因子(已占用的桶的个数/桶的总个数)0.75哈希表就需要扩容了相当于数组的扩容(线性探测哈希表)原来哈希表中的元素需要在新的哈希表中重新哈希O(n)以及线性探测哈希表均摊时间复杂度为O(1)。线性探测哈希表实现增加:通过哈希函数计算数据存放位置该位置空闲直接存储元素完成。该位置被占用从当前位置向后找空闲位置存放该元素。查询通过哈希函数计算数据存放的位置从该位置取值如果该值等于要查询元素值找到了如果不等于说明之前往这个位置放元素时发生哈希冲突了继续遍历往后找该元素如果遇到这个位置一直是空的没放过元素不需要继续往后搜索了。如果这个位置是空是因为以前放过元素后来被删除了需要继续往后搜索。所以用一个Node结构体表示元素的内容元素值加状态。删除通过哈希函数计算数据存放的位置从该位置取值判断状态是否为正在使用该值等于要删除的值直接修改当前位置的状态就可以如果该值不等于发生哈希冲突从当前位置向后遍历找到该元素如果遇到从未使用过的状态结束。#include iostream using namespace std; //桶的状态 enum State { STATE_UNUSE, //从未使用的桶 STATE_USING, //正在使用的桶 STATE_DEL, //元素被删除的桶 }; //桶的类型 struct Bucket { Bucket(int key 0, State state STATE_UNUSE) //指针指向堆上动态开辟内存 初始化 : key_(key) , state_(state) {} int key_; //存储的数据 State state_;// 桶的当前状态 }; // 线性探测哈希表类型 class HashTable { public: HashTable(int size primes_[0], double loadFactor 0.75)//primes_[0] 3 : useBucketNum_(0) , loadFactor_(loadFactor) , primeIdx_(0) { // 把用户传入的size调整到最近的比较大的素数上 if (size ! primes_[0]) { for ( ; primeIdx_ PRIME_SIZE; primeIdx_) { if (primes_[primeIdx_] size) break; } //用户传入的size值过大已经超过最后一个素数调整到最后一个素数 if (primeIdx_ PRIME_SIZE) { primeIdx_--; } } tableSize_ primes_[primeIdx_]; table_ new Bucket[tableSize_]; } ~HashTable() { delete[]table_; table_ nullptr; } public: //插入元素 bool insert(int key) { // 考虑扩容 double factor useBucketNum_*1.0 / tableSize_; cout factor: factor endl; if (factor loadFactor_) { //哈希表扩容 expand(); } int idx key % tableSize_; int i idx; do { if (table_[i].state_ ! STATE_USING) { table_[i].state_ STATE_USING; table_[i].key_ key; useBucketNum_; return true; //O(1) } i (i 1) % tableSize_; } while (i ! idx); // O(n) return false; } //删除元素 bool erase(int key) { int idx key % tableSize_; int i idx; do { if (table_[i].state_ STATE_USING table_[i].key_ key) { table_[i].state_ STATE_DEL; useBucketNum_--; } i (i 1) % tableSize_; } while(table_[i].state_ ! STATE_UNUSE i ! idx); return true; } //查询 count(key) bool find(int key) { int idx key % tableSize_; int i idx; do { if (table_[i].state_ STATE_USING table_[i].key_ key) { return true; } i (i 1) % tableSize_; } while(table_[i].state_ ! STATE_UNUSE i ! idx); return false; } private: //扩容操作 void expand() { primeIdx_; //如果指向末尾元素 if (primeIdx_ PRIME_SIZE) { throw HashTable is too large, can not expand antmore!; } Bucket* newTable new Bucket[primes_[primeIdx_]]; for (int i 0; i tableSize_; i) { if (table_[i].state_ STATE_USING) { //旧表有效的数据重新哈希放到扩容后的新表 int idx table_[i].key_ % primes_[primeIdx_]; int k idx; do { if (newTable[k].state_ ! STATE_USING) { newTable[k].state_ STATE_USING; newTable[k].key_ table_[i].key_; break; } k (k 1) % primes_[primeIdx_]; } while (k ! idx); } } delete[]table_; table_ newTable; tableSize_ primes_[primeIdx_]; } private: Bucket* table_; //指向动态开辟的哈希表 int tableSize_; //哈希表当前的长度 int useBucketNum_;//已经使用的桶的个数 double loadFactor_;//哈希表的装载因子 static const int PRIME_SIZE 10; //素数表大小 const静态成员可能在类内初始化静态常量的整型类型 static int primes_[PRIME_SIZE]; //素数表 需要在类外单独初始化一下 int primeIdx_; //当前使用的素数下标 每个哈希表不一样 }; int HashTable ::primes_[PRIME_SIZE] { 3, 7, 23, 47, 97, 251, 443, 911, 1471, 42773}; int main() { /* int data 3; //素数表 for (int i data; i 10000; i) { int j 2; for ( ; j i; j) { if (i % j 0) break; } if (j i) { cout i ; } }*/ HashTable htable; htable.insert(21); htable.insert(32); htable.insert(14); htable.insert(15); htable.insert(22); cout htable.find(14) endl; htable.erase(14); cout htable.find(14) endl; }线性探测哈希表的缺点发生哈希冲突时会逐渐趋于O(n)的时间复杂度存储变慢了(不能优化)。多线程同时在一个数组中进行查询修改不是线程安全的在多线程环境中线性探测所用到的基于数组实现的哈希表只能给全局的表用互斥锁来保证哈希表的原子操作保证线程安全映射后不在同一位置都不能并发执行。链式哈希表在多线程环境下可采用分段的锁既保证了线程安全又有一定的并发量提高了效率。解决哈希冲突的方式采用链地址法把所有哈希索引相同的冲突元素全部存储在同一个额外的动态结构通常是链表或红黑树中哈希表主数组的每个位置桶不直接存元素只存一个链表头指针所有哈希到同一个桶的冲突元素都会作为节点挂在对应桶的链表下(vectorlistint table)。哈希表因哈希冲突的存在增删查无限趋近于O(1)。每个桶的链表比较长链表搜索花费的时间就大优化一当链表长度大于某个值把桶里面的这个链表转化成红黑树O(logn)。优化二链式哈希表每个桶都可以创建自己的互斥锁不同桶中的链表操作可以并发执行起来。#include iostream #include vector #include list #include algorithm //泛型算法 using namespace std; //链式哈希表 class HashTable { public: HashTable(int size primes_[0], double loadFactor 0.75) : useBucketNum_(0) , loadFactor_(loadFactor) , primeIdx_(0) { if (size ! primes_[0]) { for (; primeIdx_ PRIME_SIZE; primeIdx_) { if (primes_[primeIdx_] size) break; } if (primeIdx_ PRIME_SIZE) { primeIdx_--; } } table_.resize(primes_[primeIdx_]);//开辟空间创建元素 } public: //增加元素 不能重复插入key void insert(int key) { //判断扩容 double factor useBucketNum_ * 1.0 / table_.size(); cout factor: factor endl; if (factor loadFactor_) { expand(); } int idx key % table_.size(); //O(1) if (table_[idx].empty()) { useBucketNum_; //只有第一次桶为空的时候添加第一个元素时桶要加加 table_[idx].emplace_front(key); //链表元素的插入 }else{ //泛型搜索 通过迭代器 判断是否重复 //使用全局的:: find泛型算法而不是调用自己的成员方法find auto it ::find(table_[idx].begin(), table_[idx].end(), key); //去重On 优化可转为红黑树 if (it table_[idx].end()) { //等于链表的迭代器没找到了 // key不存在 table_[idx].emplace_front(key); } } } //删除元素 void erase(int key) { int idx key % table_.size(); //O(1) //如果链表节点过长 如果散列结果比较集中 散列函数有问题 //如果散列结果比较离散 链表长度一般不会过长 因为有装载因子 auto it ::find(table_[idx].begin(), table_[idx].end(), key); //O(n) if (it ! table_[idx].end()) { //找着 table_[idx].erase(it); if (table_[idx].empty()) { //判断是否空桶 useBucketNum_--; } } } //搜索元素 bool find(int key) { int idx key % table_.size(); //O(1) auto it ::find(table_[idx].begin(), table_[idx].end(), key); //O(n) if (it ! table_[idx].end()) { //找着 return true; } //return it ! table_[idx].end(); return false; } private: //扩容函数 void expand() { if (primeIdx_ 1 PRIME_SIZE) { //已经到头了 throwhashtable can not expand anymore!; } primeIdx_; useBucketNum_ 0;//扩容后桶的个数会改变 vectorlistint oldTable; //容器元素太多swap的效率很低?? 交换了两个容器的成员变量 没有交换堆上的内存 table_.swap(oldTable);//调用容器的swap函数交换一下 table_.resize(primes_[primeIdx_]); //table为空重新resize 加加后的 for (auto list : oldTable) { for (auto key : list) { int idx key % table_.size(); if (table_[idx].empty()) { useBucketNum_; } table_[idx].emplace_front(key); } } } private: vectorlistint table_; //哈希表的数据结构 int useBucketNum_; //记录桶的个数 double loadFactor_; //记录哈希表装载因子 static const int PRIME_SIZE 10; //素数表大小 const静态成员可能在类内初始化静态常量的整型类型 static int primes_[PRIME_SIZE]; //素数表 需要在类外单独初始化一下 int primeIdx_; //当前使用的素数下标 每个哈希表不一样 }; int HashTable ::primes_[PRIME_SIZE] { 3, 7, 23, 47, 97, 251, 443, 911, 1471, 42773}; int main() { HashTable htable; htable.insert(21); htable.insert(32); htable.insert(14); htable.insert(15); htable.insert(22); htable.insert(67); cout htable.find(14) endl; htable.erase(14); cout htable.find(14) endl; return 0; } //vectorint nums {1, 2, 3, 4, 5}; // 定义一个vector容器 // 1. 获取迭代器begin()返回指向第一个元素的迭代器end()返回指向末尾元素的下一个位置的迭代器哨兵位置 //vectorint::iterator it nums.begin(); // 等价于 auto it nums.begin();C11及以上 //vectorint::iterator end nums.end();哈希表解决大数据查重或者统计重复的次数。查询效率高但是占用内存空间较大。#include iostream #include vector #include unordered_set//只存key #include unordered_map//存键值对 #include stdlib.h #include time.h #include string using namespace std; int main() { //模拟问题,vector中放原始的数据 vectorint vec; srand(time(NULL)); for (int i 0; i 10000; i) { vec.push_back(rand() % 10000); } //找第一个出现重复的数字用一个set只存数字每遍历一个放到哈希表里面 //找所有重复出现的数字(去掉break即可) unordered_setint s1; for (auto key : vec) { auto it s1.find(key); //O(1) 哈希表的查询 if (it s1.end()) { //it已经到末尾了 没有重复 第一次出现 s1.insert(key); }else { cout key: key endl; //第一个重复的数字 break; } } //统计重复数字出现的次数 数据加统计的结果 用键值对 unordered_mapint, int m1; for (int key : vec) { //映射表里面用pair类型 键first 值用second存 打包键值对 auto it m1.find(key); //O(1) if (it m1.end()) { m1.emplace(key, 1); //O(1) }else { it-second 1;//给他的值加个一 } } //m1[key]; for (auto pair : m1) { //遍历键值对 if (pair.second 1) { //等于1就是没有重复的数字 cout key: pair.first cnt: pair.second endl; } } //一组数据有些数字是重复的把重复数字过滤掉每个数字只出现一次 unordered_multiset允许k重复 unordered_setint s1; for (auto key : vec) { s1.emplace(key); } } int main() { string src fhusufhjsjjfijioewfw; //找出来第一个没有重复出现过的字符 unordered_mapint, int m; for (char ch : src) { m[ch]; } for (char ch : src) { if (m[ch] 1) { cout 第一个没有重复出现过的字符是 ch endl; return 0; } } cout 所有字符都有重复出现过 endl; return 0; } //有两个文件分别是a和b里面放了很多ip地址(url地址 email地址) 让你找出两个文件夹重复的ip 输出出来 //把a文件中所有的ip存放在一个哈希表中然后依次遍历文件b里面的ip每遍历一个ip在哈希表中搜索一下搜到的既是两个文件重复的ip并输出 //用到了哈希表的查询O(1) //有两个文件分别是a和b,各自存放在约一亿条ip地址每个ip地址是4个字节,限制内存使用100M让找出来两个文件中重复的ip地址并输出 800M分治算法 //先把文件a和文件b分解成11个小文件把a文件里的每一个ip散列的放在11个小文件当中依次读取出来% //11得到桶的下标写到不同的小文件当中文件b也如此然后对应的a1与b1查重2与2查重即可(因为用的相同的哈希函数)。建一个哈希表另一个文件依次读ip在哈希表中搜索即可。分文件的数量保持一致。位图法解决大数据查重位图法就是用一个位0或者1来存储数据的状态比较适合状态简单数据量比较大要求内存使用率低的问题场景。位图法解决问题首先需要知道待处理数据中的最大值然后按照size maxNumber / 321的大小来开辟一个char类型的数组当需要在位图中查找某个元素是否存在的时候首先需要计算该数字对应的数组中的比特位然后读取值0表示不存在1表示已存在。位图法有一个很大的缺点就是数据没有多少但是最大值却很大比如有10个整数最大值是10亿那么就得按10亿这个数字计算开辟位图数组的大小太浪费内存空间。数字是否出现过的状态存储到一个位图数组当中。需要知道元素序列的最大值根据最大值来定义bitmap位图数组如果是char类型的bitmap大小就是最大值/8在加1根据/%两个操作映射到元素对应的位/%几号位元素的第几位比如7 int index 7/80int offset 7%87零号位元素的第7位在读取该位的值01出现过的次数。判断某个特定位置的比特位是否为1(按位与):bitmap[index] (1offset)如何把这个位置置成1(按位或):bitmap[index] | (1offset)。#include iostream #include vector #include stdlib.h #include time.h #include memory//智能指针 using namespace std; /* 有一亿个整数最大值不超过一亿问都有哪些元素重复了 谁是第一个重复的? 谁是第一个不重复的(1个位保存数据的状态2个位保存数据的状态012) 内存限制100M 1亿 100M 100M * 4 * 2 800M 位图算法 int bitmap[100000000/321] 3.2M 缺陷 int 20亿 unsigned int 40亿 1 3 100000000 int bitmap[10000000/321] 30M 推荐的数据序列:数据的个数 和序列里面数字最大值相当 */ int main() { vectorint vec{12, 78, 90, 123, 8, 9}; //定义位图数组 int max vec[0];//找最大值 for (int i 1; i vec.size(); i) { //O(n) if (vec[i] max) max vec[i]; } int* bitmap new int[max / 32 1](); //变量动态定义到堆上 unique_ptrint[] ptr(bitmap); //内存自动释放 //找第一个重复出现的数字 for (auto key : vec) { int index key / 32; int offset key % 32; //取key对应的位的值 if (0 (bitmap[index] (1 offset))) { //表示key没有出现过 bitmap[index] | (1 offset); }else { //cout key 是第一个重复出现的数字 endl; //return 0; cout key 重复出现过 endl; } } }搜索查找问题经常会考察到除了考察二分查找哈希表还有BSTAVL红黑树等等。在内存有所限制的情况下快速判断一个元素是否在一个集合容器当中还可以使用布隆过滤器。布隆过滤器到底是个什么东西呢通俗来讲在使用哈希表比较占内存的情况下它是一种更高级的“位图法解决方案(省内存速度快)。Bloom Filter是通过一个位数组k个哈希函数构成的。Bloom Filter的空间和时间利用率都很高但是它有一定的错误率虽然错误率很低BloomFilter判断某个元素不在一个集合中那该元素肯定不在集合里面Bloom Filter判断某个元素在一个集合中那该元素有可能在有可能不在集合当中。Bloom Filter的查找错误率当然和位数组的大小以及哈希函数的个数有关系。Bloom Filter默认只支持add增加和query查询操作不支持delete删除操作因为存储的状态位有可能也是其它数据的状态位删除后导致其它元素查找判断出错。Bloom Filter增加元素的过程把元素的值通过k个哈希函数进行计算得到k个值然后把k当作位数组的下标在位数组中把相应k个值修改成1。Bloom Filter查询元素的过程把元素的值通过k个哈希函数进行计算得到k个值然后把k当作位数组的下标看看相应位数组下标标识的值是否全部是1如果有一个为0表示元素不存在判断不存在绝对正确如果都为1表示元素存在判断存在有错误率。很显然过小的布隆过滤器很快所有的bit位均为1那么查询任何值都会返回“可能存在”起不到过滤的目的。布隆过滤器的长度会直接影响误报率布隆过滤器越长其误报率越小。另外哈希函数的个数也需要权衡个数越多则布隆过滤器bit位置为1的速度越快且布隆过滤器的效率越低但是如果太少的话那误报率就会变高。场景一提示过滤一些非法或者钓鱼网站。布隆过滤器把所有可能怀疑有问题的网站的URL(域名)添加到布隆过滤器当中。在用浏览器访问网址的时候查找当前访问的网址URL是否在黑名单中如果网址URL不存在那肯定是白名单上的合法网站直接访问。如果存在(有误判率)会进行提示当前网站有风险禁止访问。场景二redis缓存中的应用(快速判断key存在与否)客户端请求输URL到IO模块网络层接收用户请求做分发到不同工作线程(服务层)涉及数据的增删改查在redis缓存层查key到底在不在而且效率要求高最好还省内存。所有的key通过redis提供的setBit(key)方法直接操作底层实现的布隆过滤器把所有的key放进去在查询的时候可以根据getBit(Key)去判断如果key不存在不用去redis里面去找了直接去数据库里面查数据在缓存redis在给用户返回。如果key存在去redis中找key(有误判但概率低)。#include iostream #include vector #include stringhash.h #include string using namespace std; //布隆过滤器实现 没有自己开辟过资源 不用析构函数 class BloomFilter { public: BloomFilter(int bitSize 1471) //位的大小 : bitSize_(bitSize) { bitMap_.resize(bitSize_ / 32 1);//数组大小 } public: //添加元素 O(1) void setBit(const char* str) { //计算k组哈希函数的值 int idx1 BKDRHash(str) % bitSize_; //字符串转整数 int idx2 RSHash(str) % bitSize_; int idx3 APHash(str) % bitSize_; //把相应的idx1 idx2 idx3 这几个位全部置一 int index 0; int offset 0; index idx1 / 32; offset idx1 % 32; bitMap_[index] | (1 offset); index idx2 / 32; offset idx2 % 32; bitMap_[index] | (1 offset); index idx3 / 32; offset idx3 % 32; bitMap_[index] | (1 offset); } //查询元素 O(1) bool getBit(const char* str) { //计算k组哈希函数的值 int idx1 BKDRHash(str) % bitSize_; int idx2 RSHash(str) % bitSize_; int idx3 APHash(str) % bitSize_; int index 0; int offset 0; index idx1 / 32; offset idx1 % 32; if (0 (bitMap_[index] (1 offset))) { return false; } index idx2 / 32; offset idx2 % 32; if (0 (bitMap_[index] (1 offset))) { return false; } index idx3 / 32; offset idx3 % 32; if (0 (bitMap_[index] (1 offset))) { return false; } return true; } private: int bitSize_; //位图的长度 vectorint bitMap_; //位图数组 }; //URL黑名单 class BlackList { public: void add(string url) { //给黑名单添加非法的URL blockList_.setBit(url.c_str()); //给布隆过滤器添加 用于兼容需要C风格字符串的场景 } bool query(string url) { return blockList_.getBit(url.c_str()); } private: BloomFilter blockList_; }; int main() { BlackList list; list.add(http://www.baidu.com); list.add(http://www.360buy.com); list.add(http://www.tmall.com); list.add(http://www.tencent.com); string url http://www.alibaba.com; cout list.query(url) endl; }求top k问题例如求值最大的或最小的前k个。如果用排序算法那么时间复杂度O(n^2基础)O(nlogn高级)怎样可以在O(n)线性时间内找到topk的元素呢利用大/小根堆利用大根堆过滤前top k小的数据小根堆过滤前top k大的数据。利于求序列值最小的三个元素需要用一个大根堆堆顶元素的值是最大的。把大根堆堆顶的大值不断淘汰放入小值。先把前三个元素构建成一个大根堆再用第四个元素跟堆顶元素比较如果大于(说明比大根堆里所有元素都大)不管比较下一个如果小于堆顶直接出堆调整把小值放入最后。只把原始序列遍历了一遍O(n)。大根堆留下的就是序列中值最小的三个元素。调整大根堆为常数级可去掉。求最大的前3个元素利用小根堆用k个元素构建小根堆把堆顶小元素不断淘汰掉把大元素放进来。#include iostream #include time.h #include vector #include stdlib.h #include queue //队列及优先级队列(堆) #include functional #include unordered_map//哈希表 键值对 无序映射表 using namespace std; //查重和top k问题综合起来了 int main() { vectorint vec; srand(time(NULL)); for (int i 0; i 10000; i) { vec.push_back(rand() % 1000); } // 统计重复次数最小的前三个数字 引入哈希表 int k 3; unordered_mapint, int map; for (auto key : vec) { map[key]; //直接统计 } //放入大根堆的时候需要放key-value键值对 用value重复次数来排 最终打印出来是key数字本身 以pari存放 using Type pairint, int; using Comp functionbool(Type, Type); priority_queueType, vectorType, Comp maxheap([](Type a, Type b)-bool {return a.second b.second;}); //把map的前三个对象添加到大根堆来 auto it map.begin(); for (int i 0; i k; i, it) { maxheap.push(*it); } //把堆顶大的淘汰出去 for (; it ! map.end(); it) { if (maxheap.top().second it-second) { maxheap.pop(); maxheap.push(*it); } } while (!maxheap.empty()) { cout key: maxheap.top().first cnt: maxheap.top().second endl; maxheap.pop(); } // 统计重复次数最大的前3个数字 int k 3; unordered_mapint, int map; for (auto key : vec) { map[key]; } // 放入大根堆的时候需要放key-value键值对 using Type pairint, int; using Comp functionbool(Type, Type); priority_queueType, vectorType, Comp minheap( [](Type a, Type b)-bool { return a.second b.second; }); auto it map.begin(); for (int i 0; i k; i, it) { minheap.push(*it); } for (; it ! map.end(); it) { if (minheap.top().second it-second) { minheap.pop(); minheap.push(*it); } } while (!minheap.empty()) { cout key: minheap.top().first cnt: minheap.top().second endl; minheap.pop(); } } /* int main() { vectorint vec; srand(time(NULL)); for (int i 0; i 1000; i) { vec.push_back(rand() % 10000); } //求vec中值最小的前5个元素 priority_queueint maxheap;//默认大根堆 int k 5; //由前k个元素构建一个大根堆 for (int i 0; i 5; i) { maxheap.push(vec[i]); } //遍历剩余的元素直到最后 for (int i 5; i vec.size(); i) { if (maxheap.top() vec[i]) { maxheap.pop(); maxheap.push(vec[i]); } } //输出结果 while (!maxheap.empty()) { cout maxheap.top() ; maxheap.pop(); } //for (auto key : vec) { // cout key ; //} cout endl;--------------- //求vec中值最大的前五个元素 定制一下比较方式 priority_queueint, vectorint, greaterint minheap;//传一个函数对象 int k 5; //由前k个元素构建一个小根堆 for (int i 0; i 5; i) { minheap.push(vec[i]); } //遍历剩余的元素直到最后 for (int i 5; i vec.size(); i) { if (minheap.top() vec[i]) { minheap.pop(); minheap.push(vec[i]); } } //输出结果 while (!minheap.empty()) { cout minheap.top() ; minheap.pop(); } cout endl; }*/利用快排分割函数每次返回的基准数的位置找出前top k大的或者前top k小的数据。定义两个下标最左边为i最右边为j选最左边的为基准数从右往左找小于基准数的找到放在基准树的位置上i在从左往右找大于基准树找到以后放到j的位置j--再找第一个小于基准树的放到i。直到ij到同一个位置把基准树放到ij相等的位置即可基准树左边都比基准树小右边都比他大。平均时间复杂度如果一直去分成为一个等比数列求和平均下来就是O(n)最差是序列已经有序了O(n^2)每次分只少了一个元素基准树选取采用三数取中。#include iostream using namespace std; //快排分割函数 int Partation(int arr[], int begin, int end) { int val arr[begin]; int i begin; int j end; while (i j) { while(i j arr[j] val) j--; if (i j) { arr[i] arr[j]; i; } while (i j arr[i] val) i; if (i j) { arr[j] arr[i]; j--; } } arr[i] val; return i; } //求top的函数 void SelectTopK(int arr[], int begin, int end, int k) { int pos Partation(arr, begin, end); if (pos k - 1) { return; }else if (pos k -1) { SelectTopK(arr, begin, pos - 1, k);//左边继续进行快排分割 }else { //落在了右边 SelectTopK(arr, pos 1, end, k); } } int main() { int arr[] {64, 45, 52, 80, 66, 68, 0, 2, 18, 75}; int size sizeof arr / sizeof arr[0]; //求最小的前三个元素 返回下标二 访问前三个元素 int k 3; SelectTopK(arr, 0, size-1, k);//起始跟末尾元素的下标 在数组中使用递归必须标识出一段范围出来 for (int i 0; i k; i) { cout arr[i] ; } cout endl; }一致性哈希算法(分布式系统负载均衡的首选算法)服务器负载均衡环境下可以配置的负载均衡算法很多如轮询算法哈希算法权重比算法最少连接算法等且一个良好的分布式哈希方案应该具有良好的单调性即服务节点的增减不会造成大量哈希的重新定位。负载场景接入机负载均衡后端带N台服务器接入机接收到请求需要将请求平均分发到每台服务器上每台服务器负责1/N的服务处理。普通的哈希算法根据客户端的ipport经过md5哈希函数处理完%服务器的个数得到数字意味着一直分发到对应的服务器上所以同一个客户端永远被映射到一台指定的server上(这个可以有效解决会话共享的问题不用额外引入redis缓存)。但如果1号机器挂掉了nginx会动态的识别到故障重新进行哈希会影响之前服务器上登录成功的用户。场景二key-value缓存服务器要CRUD数据可以直接操作DB但做不到高并发磁盘IO较慢(即使对索引做一些优化索引大了读索引也要花费磁盘IO)所以会把热点数据储存到缓存上缓存也要集群部署。用用户的id当做key在缓存负载均衡器上用md5处理映射到某台缓存服务器上。如果某台缓存服务器掉了会映射到别的服务器上缓存中找不到相应的信息去DB上找可能会瞬间释放大量的用户信息查询到DB上导致缓存血崩MySQL挂掉业务瘫痪。总结业务服务器缓存服务器通过普通的哈希算法如果有server宕机/增加会有大量的请求变更到不同的服务器上很不稳定。理想上谁挂了不影响其他server上的客户只会把后期新的请求映射到新的server上减少改动。一致性哈希算法一致性哈希算法将整个哈希值空间理解成一个环取值范围是0-2^32-1共4G的整数空间。2.将所有服务器进行哈希传入服务器的ip地址通过md5算法得到uint的整数最终落在这个一致性哈希环上。3.进行负载时先哈希输入值得到一致性哈希环上的一个哈希值例如A的请求来了带着ipport作为输入值md5进行哈希得到整数位置然后沿着顺时针遇到的第一台服务器就是最终负载到的服务器。4.容错性(减少服务器节点)和可扩展性(添加新节点)减少一个节点不会影响在别的服务器上的客户端只影响原来映射到这台机器上的客户端增加一个节点只影响增加的服务位置按逆时针遇到的上一台服务中间的这些请求(做到了最小的改动)不会大量哈希定位。一致性哈希算法底层利用了一个set红黑树储存散列码从小到大的关系只存key(哈希环)哈希得到的值以后添加到里面。服务器经过一致性哈希处理后在哈希环上应该分散一些(每个server负载能力均衡)。采用一致性哈希环的虚拟节点就是把一台机器虚拟的看成一百台机器使用ip#...的方式ip相同#后面的数字不同得到不同位置的散列值。且md5算法哪怕输入参数值比较近似md5算法处理后结果也是非常离散的。给真实的主机放100~200个虚拟节点且虚拟节点肯定保存对应的物理节点主机的信息最终负载落在对应真实主机上。虚拟节点的目的防止物理节点过少导致哈希处理后在一致性哈希环上挤在一起导致某一台server负载太多其他的server一直很空闲。//一致性哈希 #include iostream #include string //ip地址 #include set #include list //虚拟节点存储 #include map//每一台主机 承载了几台客户端的映射 using namespace std; #include md5.h using uint unsigned int; //一致性哈希环的取值类型 //虚拟节点要访问物理节点 做一个前置声明 class PhscialHost; //虚拟节点 class VirtualHost { public: VirtualHost(string ip, PhscialHost* p) : ip_(ip) , phscialHost_(p) { md5_ ::getMD5(ip_.c_str()); //调用全局不是自己 } //提供小于运算符的重载函数 给相应的类对象提供重载函数 添加 bool operator(const VirtualHost host) const { return md5_ host.md5_;//当前节点的md5要小于传进来的md5 } //比较两个自定义如何相等 删除中的查找 相等运算符的重载函数 bool operator(const VirtualHost host) const { return ip_ host.ip_; } uint getMD5() const { return md5_; } const PhscialHost* getPhscialHost() const { return phscialHost_; } private: string ip_; //虚拟节点的ip信息 uint md5_; //虚拟节点在一致性哈希环上的位置 PhscialHost* phscialHost_;//虚拟节点隶属的物理节点 }; // 物理节点 class PhscialHost { public: PhscialHost(string ip, int vnumber) : ip_(ip) { for (int i 0; i vnumber; i) { // 虚拟节点需要一个ip还需要记录它属于哪个物理节点 virtualHosts_.emplace_back( ip # ::to_string(i), this ); } } string getIP() const //一致性哈希要访问ip 和 虚拟链表 { return ip_; } const listVirtualHost getVirtualHosts() const { return virtualHosts_; } private: string ip_;//物理机器的ip地址 listVirtualHost virtualHosts_;//存储虚拟节点列表 }; //一致性哈希 class ConsistentHash { public: // 在一致性哈希环上添加物理主机的虚拟节点 void addHost(PhscialHost host) { //获取物理主机所有虚拟节点列表 auto list host.getVirtualHosts(); for (auto host : list) { //遍历这个列表 hashCircle_.insert(host); } } //在一致性哈希环上删除物理主机的虚拟节点 void delHost(PhscialHost host) { //获取物理主机所有虚拟节点列表 auto list host.getVirtualHosts(); for (auto host : list) { //遍历这个列表 auto it hashCircle_.find(host); if (it ! hashCircle_.end()) { //在一致性哈希环上删除所有物理主机对应的虚拟节点 hashCircle_.erase(it); } } } //返回负载的真实物理主机的ip信息 string getHost(string clientip) const { uint md5 getMD5(clientip.c_str());//计算客户端的md5 for (auto vhost : hashCircle_) { if (vhost.getMD5() md5) { return vhost.getPhscialHost()-getIP(); } } //映射从0开始遇见的第一个虚拟节点 return hashCircle_.begin()-getPhscialHost()-getIP(); } private: setVirtualHost hashCircle_; //一致性哈希环 }; void ShowConsistentHash(ConsistentHash chash);//函数声明 //测试一致性哈希算法的功能 int main() { PhscialHost host1(10.117.124.10, 150); PhscialHost host2(10.117.124.20, 150); PhscialHost host3(10.117.124.30, 150); ConsistentHash chash; chash.addHost(host1); chash.addHost(host2); chash.addHost(host3); ShowConsistentHash(chash); //模拟host1有故障 chash.delHost(host1); //封装一个接口完成上述同样的操作 ShowConsistentHash(chash); } void ShowConsistentHash(ConsistentHash chash) { liststring iplists{ 192.168.1.123, 192.168.1.12, 192.168.1.13, 192.168.1.23, 192.168.1.54, 192.168.1.89, 192.168.1.21, 192.168.1.27, 192.168.1.49, 192.168.1.145, 192.168.2.34, 192.168.6.78, 192.168.2.90, 192.168.4.5 }; mapstring, liststring logMap; for (auto clientip : iplists) { string host chash.getHost(clientip); logMap[host].emplace_back(clientip); } for (auto pair : logMap) { cout 物理主机: pair.first endl; cout 客户端映射的数量: pair.second.size() endl; for (auto ip : pair.second) { cout ip endl; } cout ---------------------------- endl; } cout endl; } //每个虚拟节点通过phscialHost_指针指向所属的物理节点因此当客户端映射到某个虚拟节点时能快速找到对应的物理节点getPhscialHost()-getIP()。