关于哈希表 哈希函数
特征：
（1）输入域无穷大，输出域有限，且输出确定（即可能有多个不同的输入得到相同的输出，哈希碰撞）
（2）假设将输出域抽象成一个区域，那么用一个小圈在范围内任意挪动，圈内点的数目都是差不多的，即输出点均匀离散的分布。（当然是在输入量相对大的情况下）
现有40亿个无符号整数（4字节）的文件，只给1G内存，要求得到出现频率前十的整数。
分析：
（1）如果我们用哈希表来记录，那么无符号整数是0 ~ 42亿多，一条记录<整数，词频>需要8个字节，现有40亿个整数，故共需要320亿个字节即32G内存，这无疑是灾难性的。
（2）先反推1G内存可以容纳多少条记录，大概假设可以存放1亿条记录（10亿/8）。即表示数字的种类不可大于1亿。
解法：
（1）将40亿个整数，分别通过哈希函数算出来一个值，再除余100（假设是100，范围的选择后面会分析；即把其分成100份，100个小文件），得到的数会在0 ~ 99内，那么就把这个数放到相应标号的小文件内。由哈希函数的性质，40亿个数在这100个小文件内的数量是均匀分布的，即每个小文件内数的种类大致是K/100（k即40亿个数中数的种类数）。
（2）那么每个小文件里的数的种类就不超1亿种了（即1G可以完全处理），我们再把这100个小文件分别求出Top前十，后即可求总的Top前十。
·结构
数组大小一般为质数（stl以质数设计），因为质数长度会使分布更加均匀，即每个数组链表长度相对平均。
那么由于需要遍历，那么链表长度也要有相应限定以保证查询速度。假如我要求链表长度不得超过30，当数据量超过30000，我们就要进行扩容操作。把数组数翻倍，再把原来的全部数据重新算哈希函数，然后模新的值，即200，来将值重新分配到数组上。
下面分析扩容的代价，时间复杂度。
如上述，第一次扩容是数据量超过3000，第二次扩容是数据量超过20030 = 6000，第三次扩容是40030 = 12000，以此类推。
那么我们可以知道，数据量N，需要扩容logN次（每次翻倍，乘2）每次扩容需要对全部数据N进行重新处理，那么从0~N，每次扩容时间复杂度为O（N）*O（logN），那么均分到每条记录就是O（logN）。我们可以认为哈希表增删改查时间复杂度都是O（1），是因为数据量相对较小，但并非理论上是O（1）。
分析：
利用两个哈希表，一个是<字符串，val>，另一个是<val,字符串>，还有一个整形size记录map中记录数。Val相当于编号。
（1）插入：直接看map1中有无该字符串，无则直接插入，size++。
（2）删除：