哈希函数
- 输入时无穷的，输出时有穷的
- 每个相同输入得到的返回值一定是一样的。
- 当两个不同输入也有可能得到相同的结果。出现hash冲突
- 离散性：比如：输入的样本0-93，输出S时0-2，那么所有的样本hash的结果就是相对均匀的帆布在0-2上，也就是0可能大约有33个输入等等。input量起来之后，output是均匀分布的
如何生成1000个hash函数？如果已经有了一个hash函数的输出，那么将输出split，h1+1xh2就是一个新hash值,h1+2xh2就是hash值。这么一个hash函数就可以扩展成1000个hash函数，形成结果
[h2]1、设计RandomPool的结构[/h2]设计一种结构，可以insert(Key)不重复加入key, delete(key), getRandom()等概率随机返回结构一个key。且三个函数的复杂度都是o(1);
- 准备两个hash表map1, map2
- map1里面放字符串与第几个数，map2放第几个数与放的字符串。那么add的时候，就两个map都添加。随机取数的时候，根据size的大小，随机出一个int，从map2中返回
- 主要就是删除元素怎么实现，delete(key);首先通过map1,找到第几个删除，并把map1的记录删了，把map2中的记录也删了。但是这样会在0-size中形成一个洞。那么如果下次random(size)就会恰好random这个洞。
- 为了解决size范围内删除导致的洞，可以想象用最后一个key把待删除的给替换了。那么同时map2中的那个第几个对应的key，就可以换成替换后的key。然后此时相当于待删除的被替换了，同时重复了最后一个key。在同时把最后一个去除，size--即可。
[code] 1class RandomPool 2{ 3public: 4 RandomPool() : size(0) {}; 5 6 void insert(string key) 7 { 8 if (map1.find(key) == map1.end()) 9 {10 map1.insert(make_pair(key, size));11 map2.insert(make_pair(size++, key));12 }13 }1415 string random()16 {17 if (size == 0)18 return NULL;19 srand(time(NULL));20 int result = (rand() % (size - 0 + 1)) + 0;21 return map2.at(result);22 }2324 void deletekey(string key)25 {26 int deleteindex = map1.at(key);27 int lastIndex = --size;28 string lastStr = map2.at(lastIndex);29 //在map2中，把最后一个进来的元素放在deleteindex上30 map2.insert(make_pair(deleteindex, lastStr));31 //map1也需要更新元素位置32 map1.insert(make_pair(lastStr, deleteindex));33 //在把待删除的元素和map2中最后一个位置去除34 map1.erase(key);35 map2.erase(lastIndex);36 }3738 void printfMap()39 {40 for (auto it = map2.begin(); it != map2.end(); it++)41 {42 cout first |
|
转播
