哈希函数与哈希表
哈希函数的性质
哈希函数又叫散列函数，例如MD5,SHA1等，哈希函数具有以下特性：
- 一个哈希函数的输入域是无穷大的
- 一个哈希函数的输出域虽然很大，但是是有限的
例如MD5输出的hashcode为16位的16进制数，则MD5的输出域S表示的范围为：0~2^64-1 - 相同的输入具有相同的输出
即：same input , same output
例如：一个哈希函数接收一个字符串
那么有：h("A") = h("A") - 哈希碰撞
输入不同，但有可能得到相同的输出
试想，一个哈希函数的输入域无穷大但输出域有固定范围，那么必然会有几个不同的输入可能返回一样的输出，这种情况叫做哈希碰撞或哈希冲突 - 哈希函数的离散型
假设有一样本量是0~998的999个整数，现有一哈希函数，输出域固定为[0,2],那么每个样本经过哈希函数后得到的值会大致平均落在输出域上，即：
落在0上的样本有33个左右
落在1上的样本有33个左右
落在2上的样本有33个左右
这就叫做哈希函数的离散型
通过哈希函数具有离散性可以知道，哈希函数的输入和输出是无关的，如果输入和输出相关，那么结果必然不是离散的。所以即便是两个很相近的输入也有可能得到相差很大的输出，所以利用哈希函数的离散性，可以打乱输入规律。
根据哈希函数的离散性还可以推出，如果对所有输入经过hash函数得到的hashcode取模即：hashcode%M，那么在[0,M-1]这个域上结果也是均匀分布的。
哈希表
哈希表的本质是“桶”，对于哈希表而言，增删改查操作都是O(1)的时间复杂度，经典结构的哈希表使用了链地址法来解决哈希冲突的问题
链地址法
对于一个输入，通过hash函数求出它所对应的hashcode后再取模，那么结果所对应的值就会落到[0,M-1]这个区间内。
链地址法的本质就是"数组+链表",数组中存储的是一个个Node,如果出现了哈希冲突,那么就将冲突的值挂在链表的后面。
假设输入i1落到了2这个位置上，i2落到了3的位置，i3算出hashcode并取模后为2，发生哈希冲突，解决办法就是将冲突的值添加到链上。
那么哈希表是如何做到增删改查为O(1)的时间复杂度？我们说过，哈希表是一个离散表，当样本量足够大且某个链的长度达到一定的值，比如说这个值为10，那么我就可以认为，每个链的平均长度都达到了10左右，这个时候再向哈希表中put元素效率就会变差，此时对数组进行扩容操作。扩容后，"桶"的数量增加，但是也要相对付出扩容代价，因为原本哈希表上挂的每个值都要重新模上扩容后数组的长度再重新分配到新的表上。
java中的哈希表
Java中的HashMap的结构本质上是数组+TreeMap，也就是数组上挂的是一个个红黑树。
Java8以前，哈希表的结构为数组+链表，在Java8以后，当装载因子(数组承载的链表的长度)达到一定的阈值后，每个位置从链表进化成红黑树，这个阈值为8。
开放地址法
开放地址法可以做到所有输入的元素全部盛放在桶中，也就是说桶上面不需要挂链表或者红黑树，装载因子不会超过1。
开放地址法的基本思路为：当发生哈希冲突，根据再寻址的方法即，以当前地址为基准，继续探测哈希表中的其他存储单元，直到找到空位置为止。
HashMap的增删改查
Java 中 HashMap 的增删改查
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
public class HashMapTest {
public static void main(String[] args){
HashMap<String,Integer> hashMap = new HashMap<>();
hashMap.put("kim",25);
// 新的value值会覆盖掉原来的value值
hashMap.put("kim",26);
hashMap.put("dog",2);
hashMap.put("cat",2);
hashMap.put("gary",39);
hashMap.put("laowang",27);
hashMap.put("laozhang",28);
// 是否存在 key: hashMap.containsKey(key)
System.out.println(hashMap.containsKey("kim"));
System.out.println("========================");
// 获取key对应的value值: value = hashMap.get(key)
System.out.println(hashMap.get("kim"));
System.out.println("========================");
// isEmpty & size
System.out.println(hashMap.isEmpty());
System.out.println(hashMap.size());
System.out.println("========================");
// 从哈希表中删除key和value: hashMap.remove(key),返回删除的key对应的value
System.out.println(hashMap.remove("laozhang"));
System.out.println(hashMap.containsKey("laozhang"));
System.out.println(hashMap.size());
System.out.println("========================");
// 遍历
// 遍历hashMap中所有的key
for(String key : hashMap.keySet()){
System.out.print(key + " ");
}
System.out.println();
System.out.println("========================");
// 遍历hashMap中所有的value
for(Integer value : hashMap.values()){
System.out.print(value + " ");
}
System.out.println();
System.out.println("========================");
// 遍历hashMap中所有的 key 和 value
for(Entry<String,Integer> entry : hashMap.entrySet()){
System.out.println("key:"+entry.getKey()+" value:"+entry.getValue());
}
System.out.println("========================");
// 批量删除,本示例中为删除所有value为 2 的元素
List<String> removeKeys = new ArrayList<>();
for(Entry<String,Integer> entry : hashMap.entrySet()){
if(entry.getValue().equals(2)){
removeKeys.add(entry.getKey());
}
}
for(String removeKey:removeKeys){
hashMap.remove(removeKey);
}
for(Entry<String,Integer> entry : hashMap.entrySet()){
System.out.println("key:"+entry.getKey()+" value:"+entry.getValue());
}
}
}
hash的应用-海量数据分流处理
对于一个大流量请求时，通过hash函数可以将流量分流到几个服务器进行处理，因为hash函数具有离散性，所以我们认为每个服务器是负载均衡的。
但是这样做也有缺点，如果说某一台服务器出现了故障或者说需要新添加一台服务器，那么就需要重新去计算每一个请求的key的哈希值，这样一来，大量的key会被重新定位到不同的服务器而造成大量的缓存不命中。一致性哈希则能有效解决此类问题，本文后面有具体的介绍。
(以上内容参考了文章:海量数据分流处理-------一致性哈希算法)
哈希表相关题目
设计一种 RandomPool 结构
设计一种结构，在该结构中有如下三种功能：
1. insert(key)：将某个key加入到该结构，做到不重复加入。
2. delete(key)：将原本在结构中的某个key移除。
3. getRandom()：等概率随机返回结构中的任何一个key
要求 : insert、delete和getRandom方法的时间复杂度都是 O(1)
当看到插入，删除，查询的操作均为O(1)时，我们就想到了使用哈希表去实现RandomPoll结构，思路如下：
使用两个哈希表和一个size变量，map1存储的key和value类型分别为K和Integer,map2存储的key和value类型分别为Integer和K。
当向RandPool结构中插入数据时，两表同时put相应的数据和索引，变量size++;
当执行getRandom操作返回一个随机的key时，通过Math.random确定随机数，这个随机数即对应map2中的key,随之返回map2中的value即可;
当执行delete操作时，如图所示:
依次向哈希表中 put 进 A~Z 26 个字符串。假设现在要删除的key为“C”
如果删除了("C",3)这样一组元素，那么在hashmap上面就会出现“空洞”，这样就无法做到可以等概率随机返回此结构中的任何一个key了，解决方案如下：
即，将“最后一个元素”覆盖掉删除的元素，这样哈希表就可以保证连贯性。具体实现代码如下：
import java.util.HashMap;
public class RandPoolProblem {
public static class Pool<K>{
private HashMap<K,Integer> map1;
private HashMap<Integer,K> map2;
private int size;
public Pool(){
this.map1 = new HashMap<>();
this.map2 = new HashMap<>();
this.size = 0;
}
public void insert(K key){
if(!map1.containsKey(key)){
map1.put(key,size);
map2.put(size,key);
size++;
}
}
public void delete(K key){
if(map1.containsKey(key)){
int delIndex = map1.get(key);
int lastIndex = --size;
K lastKey = map2.get(lastIndex);
map1.put(lastKey,delIndex);
map2.put(delIndex,lastKey);
map1.remove(key);
map2.remove(lastIndex);
}
}
public K getRandom(){
if(size == 0){
return null;
}
int randomIndex = (int)(Math.random() * size);
return map2.get(randomIndex);
}
}
}
布隆过滤器
布隆过滤器(Bloom Filter)实际上是一个比特数组。布隆过滤器可以用于检测一个元素是否在一个集合中，它的优点是省空间，以及时间，缺点是有误差率。
布隆过滤器的应用案例主要有：爬虫去重，黑名单问题等，我们从黑名单问题开始认识布隆过滤器
黑名单问题
现在有10亿个URL黑名单，每个URL固定为32字节
需要设计一种结构，当一个URL传过来时，判断这个URL是否在黑名单中。
如果我们使用HashSet，可以做到准确查询以及查询的时间复杂度为O(1),但是这样一来哈希表在服务器内存上的消耗将会是巨大的，至少需要320亿字节。
布隆过滤器则可以做到减少内存压力，快速查询。
首先准备一个足够大的长度为M的int类型的数组
int[] arr = new int[M];
因为int类型为4字节，每个字节有8位，所以开辟的数组空间可以存放32M个bit。现在准备K个哈希函数，对10亿个URL依次求出hashcode并取模
那么如何判断hashcode取模后落在bit数组上的位置呢？拿hash1()%M举例，假设该值为code1
int intIndex = code1 / 32; // 在int数组上的哪一个位置
int bitIndex = code1 % 32; // 在对应的int数组上的哪一个bit位
arr[intIndex] = (arr[intIndex] | (1 << bitIndex));
// 1 << bitIndex 即，除了bitIndex外的bit位都为0，通过和arr[intIndex]进行或运算后
// code1在bit数组上对应的位置被“抹黑”（该位置值为1）
除了code1以外，其他的哈希函数也在32M长度的bit数组上分别"抹黑"了相应的位置
十亿个URL在K个哈希函数下，标记的位置变为1，首先要确定的是M要足够大，要不然可以试想一下，如果32M个位置几乎全部抹黑，那么误差率就会大大提升，另外我们也可以解释为什么布隆过滤器会产生误差，产生的误差类型是有可能为不在黑名单的URL,但是碰巧算出的hashcode都为黑，这样就会返回true,不过可以确定的是如果是在黑名单的URL那么返回值一定为true,其通过hash函数后落在bit数组上的位置必然均为1，布隆过滤器的误差率可以形象地说是“宁可错杀一千，绝不放过一人”。
不难看出，当检验的哈希函数的个数K增加，误差率必然下降；如果bit数组的长度增加，误差率也必然下降。
布隆过滤器样本量n,bit数组长度m,哈希函数个数k与失误率p的关系
给定样本量以及预期失误率可以推断出需要开辟多少bit长度的数组
计算出需要开辟多少bit长度的数组后，可以推断出需要多少个hash函数
直到m以及k的取值后，可以重新计算失误率。试想公式一推断出的m值向上取值，那么m的数量增加，bit数组长度增加失误率则会相应减少；通过公式二推断出k值也向上取值，k的数量增加，哈希函数校验的个数增加失误率也会相应地减少，所以得到的真实失误率必然要比预期失误率好。
布隆过滤器的重要应用
参考文章:大白话布隆过滤器
一致性哈希
在hash应用-海量数据分流一节中：
我们知道，当发起大流量的请求时，后端的服务器负载均衡，但是也有缺点，如果某台服务器故障，或者需要新增加一台服务器的时候，那么所有的请求元都要在重新计算自己分配到了哪一台服务器上。有没有方法可以优化这一点并且还能做到负载均衡呢？一致性哈希和虚拟节点技术就解决了这样的问题。
一致性哈希
以MD5举例，MD5的S域表示的范围为[0,2^64],那么就假想一个环：
假设对每台服务器的ip求hashcode后分布在环上的情况如下
某数据经过前端的MD5哈希函数得到的数值必然落在环上，从落点开始顺时针走，最近的服务器则会被分流到。如果增加服务器或者减少服务器：
如图所示，新增s4，那么原本在s3的黄色部分数据就会转到s4上，减少服务器也是同理，可见不需要太大的牺牲。
每一台前端服务器记录着排好序的后端服务器hash(ip),当有新的数据需要分配到后端服务器，则在前端服务器上通过二分法找到大于等于新的数据的那个server，然后再进行分配。
不过，这种环结构却牺牲了传统哈希分流负载均衡的优点，虚拟节点则解决了这一问题
虚拟节点
还是有三台服务器，不过现在为每个服务器配1000个虚拟节点。虚拟节点负责"抢"数据。通过路由表可以知道哪一个服务器对应着那些虚拟节点。因为这样下来平均就是3000个虚拟节点，在整个S域上可以做到负载均衡，抢数据的原理和上面介绍的一样，顺时针走，遇到最近的虚拟节点然后通过路由表看该虚拟节点对应的是哪一个实体服务器，那么数据就被分配到哪个服务器上。
新增服务器或者是减少服务器也是一样的，如果新增服务器，那么就再原有虚拟节点的基础上再次增加1000个虚拟节点，原本散布在别的服务器上的数据，也会通过虚拟节点移至新的服务器上，这样一来通过一致性哈希不仅可以做到新增或减少服务器不需要消耗巨大代价，也可以做到服务器之间负载均衡。
