一、哈希函数的特征

输入∞，输出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<K>{
        private HashMap<K, Integer> keyIndexMap;
        private HashMap<Integer, K> indexKeyMap;
        private int size;
        
        public Pool(){
            this.keyIndexMap = new HashMap<K, Integer>();
            this.indexKeyMap = new HashMap<Integer, K>();
            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<String> pool = new Pool<String>();
        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作数据的划分（均分）。