构建一个完美无冲突的 hashmap（上图附代码)

贴一下代码

 vector<string> keydata; // 从文件里读取的字符串集合 int elemsize = keydata.size(); // 字符串集合总大小 int seedsize = elemsize * 1.6180339887498948482;// 种子大小，使用黄金分割率；太大会多占用空间，太少会增加计算耗时，也有可能没有完美解。 vector<int> seedset; // 种子空间是否被占用 vector<int> dataset; // 对应原始的字符串ID vector<int> keyseed; // 和key对应的种子seed seedset.resize(seedsize, 0); // resize同时并初始化为0 dataset.resize(seedsize, 0); keyseed.resize(elemsize, 0); // 构建算法: 查找空余的桶，如果已经被占用，则循环查找，一直到找到空位为止。 for (i=0;i<elemsize;i++) { for (int s=0;;s++) { uint hashval = crc32(s, (const byte*)keydata[i], keydata[i].size()) % seedsize; if (seedset[hashval] == 0) { seedset[hashval] = 1; // 声明此桶被占用 dataset[hashval] = i; // 字符串id号会重排 keyseed[i] = s; // 保存seed种子 break; } } } 

 // 查找测试 int id = 50; uint hashval = crc32(keyseed[id], (const byte*)keydata[id], keydata[id].size()) % seedsize; int findid = dataset[hashval]; 

以上查找代码有两点优化空间

第一是% seedsize取余数可以改成 & seedmask。 第二是crc函数不快，hash函数可以换成更快的。

这个是图片上vs2022的hashmap对比测试代码 http://www.dooccn.com/cpp/#id/b493ff0ca2ba66c061a59b8aa1f78dbe