哈希函数与哈希表

摘要：哈希函数与哈希表一哈希函数哈希函数性质输入域是无穷的输出域有穷的当输入参数固定的情况下，返回值一定一样当输入不一样，可能得到一样的值。

input输入域是无穷的

output输出域有穷的

当输入参数固定的情况下，返回值一定一样

当输入不一样，可能得到一样的值。(必然会出现，因为输入域很大，输出域很小)，产生哈希碰撞

均匀分布的特征，就相当于一个香水喷了房间，让它自由的布朗运动，那么房间内就漫步了香水分子

Input计算哈希值后的结果都很大，但是如果把他们都与m取余，那么就在一个0-m-1的这个域(hashmap就是这样找下标的)。如果在S域上是均匀分布的，那么在mod上0~m-1也是均匀分布的。

先将一个hash结果拆分两个(高8位，低8位，是相互独立的)得到两个h1,h2，然后组合，如h1+i*h2 得到1000个哈希函数。

注意每个下标的链表是均匀往下涨的，哈希函数第五点性质

哈希表扩容(可以认为扩容代价为O(1)，因为优化技巧很多，实际数学上不是)：

假设一个哈希表长度为17，某个下标的个数为5，那么可以认为其他下标也放置了5个节点，假设效率不行，就需要扩容了。如扩容到104，那原来的mod（17）就失效了，

离线扩容就是原来的哈希表还在使用(用户不需要等待扩容过程)，在后台拿一个桶来，等数据都导入到新的桶，下一个请求就转到新的桶。不存在在Java的JVM中(Java是用红黑树)。

Java中是怎么实现的呢？
一个桶，桶里放的是什么？不是链表而是红黑树treemap。是个平衡搜索二叉树。

技巧：哈希函数做分流(利用哈希函数相同输入相同输出，不同输入均匀分布的性质)
题目：假设有一个大文件(比如100T)，大文件里每行是个字符串，但是是无序的，把所有重复的字符串打印出来。
假设有1000台机器，标号，0-999台机器。大文件存储在一个分布式文件上，按行读取字符串 计算哈希值，mod1000，然后分到1000台机器，相同的文本一定会分到一台机器上(相同hash输入，得到的结果一定是一样的)。

题目：设计randomPool结构
题目内容：设计一种结构，在该结构中有如下三个功能：
insert(key):将某个key加入到该结构，做到不重复加入
delete(key):将原本在结构中的某个key移除，
getRandom():等概率随机返回结构中的任何一个key
要求：三个方法的时间复杂度都是O(1)

解法：准备两张hash表(一张hash表无法做到严格等概率随机返回一个)

HashMap keyIndexMap = new HashMap();
HashMap indexKeyMap = new HashMap();

做法：
A 第0个进入hash表 ， 表A key A value 0 表B key 0 value A
B 第1个进入hash表 ， 表A key B value 1 表B key 1 value B
insert(key)代码实现：

public void insert(String key){
    if(keyIndexMap.containsKey(key)){
        return;
    }else{
        keyIndexMap.put(key,number);
        indexKeyMap.put(number,key);
        number++;
    }
}

利用math的random函数，随机从size取一个数字，在哈希表2取对应数字的key，就是随机等概率的
getRandom()代码实现：

public String getRandom(){
    if(size ==0){
        return null;
    }
    int index = (int)(Math.random()*size);
    return map2.get(index);
}

如果要remove呢？
直接remove会出现问题：删除key对应要删除某个index，那么就会产生“洞”，调用getRandom就一次调用得到等概率结果。
那么该如何去删呢？
如假设有1000个key,要删除str17，那么找到index17, 把str999在keyIndexMap的index变为17，map2的17改为str999，删除index999的洞，即产生洞的时候删除最后一条，再删除函数需要删除的key。通过交换最后一行数据保证index是连续的。

public void delete(String key){
    if(keyIndexMap.containsKey(key)){
        Integer deleteIndex = keyIndexMap.get(key);
        int lastIndex = --number;
        String lastKey = indexKeyMap.get(lastIndex);
        indexKeyMap.put(deleteIndex,lastKey);
        keyIndexMap.put(lastKey,deleteIndex);
        keyIndexMap.remove(key);
        indexKeyMap.remove(number);
    }
}

解决的问题：爬虫去重问题。

黑名单问题(100亿个url,每个url64字节，当用户搜索某个url的时候，过滤。属于黑名单返回true，不属于返回false；用哈希表hashset做的话那么至少要6400亿字节，实际还不止！640G放到内存耗费巨大代价；也可以用哈希分流给多个机器做，但是需要的机器较多)

布隆过滤器可能存在较低失误率：可能会把清白的判断为黑名单，但是只要是黑名单，必会判断为黑名单。

因此，如果面试官问这种问题：可以先用哈希分流的方法回答，再则问面试官是否允许较低失误率？如果允许的话，采用布隆过滤器。

布隆过滤器：比特数组
如 int[] arr = new int[1000]; 那么就有32000比特(int 4个字节 32位)
怎么给某个位的比特抹黑？

int index = 30000; //要描黑的位置
int intIndex = index/32;  //找打数组的下标
int bitIndex = index%32;  //下标对应元素的哪个位置应该被描黑
arr[intIndex] = (arr[intIndex] | (1<
黑名单应该怎么设计？
思路：url -> 计算哈希值，%m,得到的结果可以对应到0~m-1的位置，算到的地方描黑；
此时并不是布隆过滤器。
准备hash1,hash2,…,hashk 个哈希函数描黑(可能多个hash函数会到同一个位置,url描黑意味着这个url进到这个布隆过滤器)
比特数组应该尽可能大一些，不然小了一下就数组全描黑了
利用布隆过滤器判断：来一个url，就在这k个hash函数得到K个位置，如果都是黑的，就是在黑名单，如有一个不是，就不在黑名单内。
解释：如果url曾经进过，肯定都是黑的。有一个位置不是黑的，那肯定没进过,就是白的。
失误原因：

数组长度不够！导致都是黑的。
正常非黑名单用户可能结算的结果也对应在描黑位置

数组空间越大，失误率越低。
哈希函数好处：数组空间开多大与单样本的大小无关，而和url的样本个数有关。
四、认识一致性哈希技术
几乎集群都用到这个，需要抗压服务器(牵扯，服务器设计，负载均衡)
服务器如何进行抗压的呢？
如前端要存储
做法：存储的数据，计算哈希值%后台服务器数，然后存到对应机器
前端计算分配到后台服务器的数目会巨均衡。
问题：当想要加机器和减机器就出现问题了，因为%的服务器数目变了。
解决方法：通过一致性哈希就能解决问题，迁移成本低
通过机器的IP或者MAC来计算哈希的位置，划分哈希值的环(把整个哈希结果想象成一个环)来管理。
存在问题：机器少的时候，不能均分这个哈希的环。有可能只有两个机器的情况，两个机器很近，负载很不均匀！
解决方法：虚拟节点技术
m - 1（分配1000个虚拟节点）:m - 1 - 1, m-1-2,m-1-3,m-1-4,.. 
m - 2:m-2-1,m-2-3,m-2-3,…
m - 3…
用这3000个虚拟节点抢这个环。抢到的给对应机器处理。这样就比较均匀了。几乎均分这个环。