一、哈希函数的特征二、返回出现次数最多的数三、哈希表的实现四、设计RandomPool结构五、位图六、布隆过滤器七、一致性哈希
一、哈希函数的特征- 输入∞，输出S（有限范围）same in -> same out 不随机different in -> same out 哈希碰撞，几率很小不同的输入可以几乎均匀的离散到S区域
输入，经过哈希函数得到数在有限范围S中，模M，得到的结果在0~M-1范围内也均匀分布 二、返回出现次数最多的数
题目：无符号整数0~2^32-1，约40亿个数，每个数的值0~42亿，先有1G内存，求出现次数最多的数？
- 哈希表： key(int) 需4B，value(int)出现次数需4B，忽略索引空间，40亿*8B=320亿B=32G 不符合要求
哈希表占用空间只和不同的数有多少种有关哈希函数： 每个数调用哈希函数，得到一个值，再模100，结果在0~99范围上。分为100个小文件后，每个小文件再用哈希表。
哈希表使用的空间：32G/100
每统计完一个小文件，释放掉所占用的空间，去统计下一个小文件。
在每个文件中找出出现次数最大的数，共100个，再在这100个数中找出出现次数最大的数。
方式：单向链表
为了避免链长度过长，可进行扩容
哈希函数时间复杂度：O(1)
得到哈希值之后模一个值：O(1)
加、查、改 一个记录：O(1)
若已经加入N个字符串，则经历了logN次扩容：O(logN)
每次扩容的代价：O(N)
总的扩容代价：O(NlogN)
平均、单次扩容：O(NlogN)/N=O(logN)
技术一
设置较长的链长度，O(NlogN)/N逼近O(1)
n为底，n为扩容的倍数
技术二 -> 离线扩容技术 （JVM等一些虚拟机语言）
用离线技术，不占用用户的在线
哈希表在使用时可以认为增删改查都是O(1)，理论上是O(logN)
四、设计RandomPool结构【题目】
设计一种结构，有如下三种功能：
insert（key）：将某个key加入到该结构，做到不重复加入
delete（key）：将原本在结构中的某个key移除
getRandom（）：等概率随机返回结构中的任意一个key
【要求】
insert、delete和getRandom的时间复杂度都是O(1)
package com.zuogod.java;
import java.util.HashMap;
//使用两个哈希表
public class RandomPool {
public static class Pool{
private HashMap keyIndexMap;
private HashMap indexKeyMap;
private int size;
public Pool(){
this.keyIndexMap = new HashMap();
this.indexKeyMap = new HashMap();
this.size = 0;
}
public void insert(K key){
if (!this.keyIndexMap.containsKey(key)){ //如果没加过，则加入；加过，跳过
this.keyIndexMap.put(key,this.size); //key是第size个进来的
this.indexKeyMap.put(this.size++,key); //第size给进来的是key，size++
}
}
public void delete(K key){
if(this.keyIndexMap.containsKey(key)){
int deleteIndex = keyIndexMap.get(key);
int lastIndex = --size;
K lastKey = this.indexKeyMap.get(lastIndex);
this.keyIndexMap.put(lastKey,deleteIndex);
this.indexKeyMap.put(deleteIndex,lastKey);
this.keyIndexMap.remove(key);
this.indexKeyMap.remove(lastIndex);
}
}
public K getRandom(){
if (this.size == 0){
return null;
}
int index = (int)(Math.random() * this.size); //0 ~ size-1
return this.indexKeyMap.get(index);
}
}
public static void main(String[] args) {
Pool pool = new Pool();
pool.insert("zuo");
pool.insert("cheng");
pool.insert("yun");
pool.remove("zuo");
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
}
}
五、位图
如何使用更小的内存单元来标记一个数字，而在程序中我们最小的访问单位的bit位，所以使用比特位如何标记(映射)这些数据，成为位图。怎么做出bit类型的数组？
用基础类型拼
int a = 0; //a 32bit int[] arr = new int[10]; //32bit*10 -> 320bits // arr[0] int 0~31 // arr[1] int 32~63 // arr[2] int 64~95 int i = 178; //想取得178个bit的状态 int numIndex = 178 / 32; //到那个数上找 int bitIndex = 178 % 32; //在这个数的哪一位 //拿到178位的状态 int s = ( (arr[numIndex]) >> (bitIndex) & 1); //右移找到这一位，与1相与 //把178位的状态改成1 arr[numIndex] = arr[numIndex] | (1 << (bitIndex)); //原来的状态位 或 1左移bit数 //把178位的状态改成0 arr[numIndex] = arr[numIndex] & (~ (1 << (bitIndex)); //原来的状态位 或 1左移bit数六、布隆过滤器
布隆过滤器是一种比较紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，判断某样东西存不存在，他是用多个哈希函数将一个数据映射到位图结构中，不仅可以提升查询效率。也可以节省大量的内存空间。
解决类似黑名单查询模型
只有加入、查询，没有删除
节省内存空间，加速查询时间
有失误率，不会把对的判错，但可能把不对的判对
（1）黑 -> 白 ×不可能有这种情况
（2）白 -> 黑 √
操作
(1)加入：每个url调用k个哈希函数得到哈希值out1再模m => 得到k个数，将对应的k个数描黑
(2)查询：urlx调用k个同样的哈希函数得到哈希值out再模m => 得到k个数，查询对应k个数对应位置的状态
若全是1，则url在黑名单集合中；若不全是1，则url不在黑名单中
-根据m以及具体的样本量来定出合适的哈希函数个数来（哈希函数的个数相当于有多少个特征点，但不能过多，过多失误率也会提升）
（1）布隆过滤器只和 n=样本量，p=失误率 有关，和单样本的大小无关（即一个url是64字节没有用，只要调用的哈希函数能够接收64字节的参数就可以）
单样本的大小和布隆过滤器的大小、哈希函数的个数个数无关
（2）数组大小：m = - (n * lnp) / (ln2)^2
其中，m为需要的bite位数，n为样本量，p为预期失误率；字节数为m/8
（3）哈希函数的个数：K = ln2 * m/n = 0.7 * m/n
（4）数组大小和哈希函数个数向上取整，真实失误率为：(1 - e ^ (- n*K/m))^K
对于 K 个关键字和 n 个槽位(分布式系统中的节点)的哈希表，增减槽位后，平均只需对 K/n 个关键字重新映射。哈希指标
评估一个哈希算法的优劣，有如下指标，而一致性哈希全部满足：
（1） 均衡性(Balance)：将关键字的哈希地址均匀地分布在地址空间中，使地址空间得到充分利用，这是设计哈希的一个基本特性。
（2）单调性(Monotonicity): 单调性是指当地址空间增大时，通过哈希函数所得到的关键字的哈希地址也能映射的新的地址空间，而不是仅限于原先的地址空间。或等地址空间减少时，也是只能映射到有效的地址空间中。简单的哈希函数往往不能满足此性质。
（3）分散性(Spread): 哈希经常用在分布式环境中，终端用户通过哈希函数将自己的内容存到不同的缓冲区。此时，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
（4）负载(Load): 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。数据如何选择机器？
通过哈希环对应找离自己最近的那一台。（二分法）哈希Key的选择：
选择种类比较多，让高频、中频、低频都有数量的Key作数据的划分（均分）。
优点：能够把数据迁移的代价变得很低，同时又负载均衡
问题1：
数量很少的机器如何保证负载均衡？
问题2：
即使一开始负载均衡，如果突然增加一个机器，怎么确保负载均衡？
解决方法：虚拟节点技术 (按比例) ＝＞ 优点：管理负载
