(一)哈希函数和哈希表的实现认识哈希函数和哈希表的实现1.哈希函数的定义f(in)out(1)in-∞,out-s.比如md5算法输出的范围是0~2^64-1,SHA1算法的输入范围是0~2^128-1;(2)same in -same out.不随机(3)dif in -same out.(哈希碰撞)(4)均匀分布,散列表.固定区域的点数量差不多,满足均匀分布.示例:输入序列{in1,in2,in3......}通过哈希函数f得到输出序列{out1,out2,out3......},输出序列通过%m运算得到{m1,m2,m3....},那么它的结果必然存在在0~m-1上.它必须保证输出序列{out1,out2,out3......}在s上均匀分布,在0~m-1上均匀分布.无符号整数0~2^32-1大约有42亿个 。问题如果只有1G内存求最多次出现的数字是哪个在经典解法里我们可以设置一个Hash表key(int) value(int),用于记录次数。一记录里由于key占用4B内存value占用4B内存至少8B内存。按照最差的情况40亿条记录都不相同那么最少要320亿B内存大约是32G。显然不够会爆内存。因此需要用到hash函数。40亿个数的输入序列{a1,a2,a3......}通过哈希函数f得到输出序列{b1,b2,b3......},输出序列通过%100运算得到{m1,m2,m3....},这样可以把40亿个数分配到100个文件里面去32G/1000.32G内存不会爆得到100个0.32G的小文件这些小文件里有100个出现频率最多的数。接下来对100个小文件对出现次数最多的数统计。流程一次只读取一个文件↓在内存建立HashMap↓统计这个文件每个数字出现次数↓找这个文件出现次数最多的数字↓清空HashMap↓处理下一个文件另由于只有100个小文件会存在碰撞的情况比如1000和4327存到同一个文件里去value值分别是2和1但是碰撞不等于把1000和4327当成同一个数字能够做到词频压缩在总数上做到均分。2.哈希表的实现如图所示思考随着每一个字符的加入,hash表的链条几乎是均匀变长的。但是,随着N的增大要寻找某个字符串的位置要遍历的链条的长度是N/m,这样hash表的性能做不到O(1),假设N/m的值超过了某个阈值比若说6那么对hash表进行扩容。举例对于一个长度为17的哈希表如果其中的一条链的长度达到了6我们就对hash表进行2倍数的扩容将表长度扩容为34那么最长链条的长度会变成3。计算代价对于输入x哈希函数f的代价是O(1)得到out后对它取m的代价是O(1)当在hash表的格子中寻找时如果链的长度为k的话遍历的代价是O(k),如果k的长度很小,可以看作O(1)。如果一次扩容扩一倍1 2 4 8 ... N/2N-1数量级与N一致扩容的总代价如果加了N个字符串最差情况每个位置只放一个字符串(k到达2就扩容)那么扩容次数的的级别为O(logN)换底公式logk(N)log2(N)/log2(k),只差一个常数由于每一次都要重新计算那么重新形成hash表的代价为O(N)。不断扩容的总代价为O(N*logN)单次扩容的代价为O(N*logN)/(N-1)O(N*logN)/NO(logN)。另Java虚拟机JVM语言可以利用离线扩容技术来提高运算速度在操作hash表时做到常数级别的增删改查。原理是利用倍增扩容和均摊分析使 HashMap 的插入操作在平均意义下保持 O(1)。比如说正常情况 put / get / remove ↓ hash(key) ↓ 定位桶 ↓ 桶内元素很少 ↓ 接近 O(1) 当元素越来越多超过装载因子阈值时 旧表容量16 元素过多 ↓ 触发扩容 ↓ 新表容量32 ↓ 把旧表中的元素重新分配到新表Java HashMap通过数组扩容、较好的哈希分布以及链表/红黑树来保证增删改查通常具有很高效率。在哈希分布良好的情况下get/remove平均为O(1)put的均摊复杂度为O(1)。扩容本身不是O(1)而是一次较昂贵的O(N)级操作但由于扩容按倍数发生扩容次数很少因此均摊到每次插入后仍为O(1)。(二)相关理论1.设计RandomPool结构【题目】设计一种结构在该结构中有如下三个功能insert(key)将某个key加入到该结构做到不重复加入delete(key)将原本在结构中的某个key移除getRandom()等概率随机返回结构中的任何一个key【要求】Insert、delete和getRandom方法的时间复杂度都是O(1)。leetcode380思路对于insert,可以准备两张表map1(str-index),map2(index-str),以及一个int size0。比如说第一个加入的字符串是“A”,则map1中存为(“A”,0)map2中存为(0,A),int size1;第二个加入的字符串是“B”,则map1中存为(“B”,1)map2中存为(1,B),int size2;以此类推,直到size26。对于getrandom,没有删除行为时size26由于0~25没有任何一个区域是空着的可以做到等概率随机返回对应的字符串。如果删除若干个字符串由于随机数对应的区域可能是空的需要试很多次才能得到可行的返回字符串因此要保证index区域是连续的。假设删除的是D这个记录那么就用最后一行的Zindex最后1条记录来填补D的空缺对于map1和map2中index25的记录消失Z对应的记录变为“Z”,33,“Z”,那么在0-24这个区间上就变得连续了。代码package Class009; import java.util.HashMap; public class Code_RandomPool { public static class PoolK{ private HashMapK, IntegerkeyIndexMap; private HashMapInteger,KindexKeyMap; private int size; public Pool(){ this.keyIndexMapnew HashMapK,Integer(); this.indexKeyMapnew HashMapInteger,K(); this.size0; } public void insert(K key){ if(!this.keyIndexMap.containsKey(key)){ this.keyIndexMap.put(key,this.size); this.indexKeyMap.put(this.size,key); } } public void delete(K key){ if (this.keyIndexMap.containsKey(key)){ int deleteIndexthis.keyIndexMap.get(key); int lastIndex--this.size; K lastKeythis.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.size0){ return null; } int randomIndex(int) (Math.random()*this.size);//0~size-1 return this.indexKeyMap.get(randomIndex); } public static void main(String [] args){ PoolStringpoolnew PoolString(); pool.insert(zuo); pool.insert(cheng); pool.insert(yun); System.out.println(pool.keyIndexMap); System.out.println(pool.indexKeyMap); System.out.println(pool.getRandom()); System.out.println(\n 删除 cheng ); pool.delete(cheng); System.out.println(pool.keyIndexMap); System.out.println(pool.indexKeyMap); System.out.println(size pool.size); } } }运行结果{yun2, zuo0, cheng1} {0zuo, 1cheng, 2yun} cheng 删除 cheng {yun1, zuo0} {0zuo, 1yun} size 22.布隆过滤器布隆过滤器Bloom Filter是一种利用“bit数组 多个哈希函数”实现的概率型数据结构用来快速判断一个元素是否属于某个超大集合常用机器的内存可以运行。且容许非常小的失误比如万分之一比如将白名单列入黑名单。特点占用内存很小。查询速度很快通常接近O(1)。如果判断“不存在”则一定不存在。如果判断“存在”则只是可能存在有一定误判率。例如有100亿个危险URL每个URL最长64Byte希望限制用户访问这些URL。如果直接保存所有URL100亿 × 64Byte ≈ 640GB还没有计算HashMap等数据结构的额外空间内存开销非常大。使用布隆过滤器时不直接保存URL而是准备一个很大的bit数组0 0 0 0 0 0 0 0 0 ...再准备多个哈希函数例如hash1(url)hash2(url)hash3(url)加入危险URL例如url bad.com计算得到hash1 - 2hash2 - 7hash3 - 11于是把bit数组中的2、7、11位置设置为10 0 1 0 0 0 0 1 0 0 0 1↑ ↑ ↑所有100亿个危险URL都执行同样的操作。查询时用户访问abc.com通过三个哈希函数得到hash1 - 2hash2 - 5hash3 - 11检查对应位置2号位置 15号位置 011号位置 1只要其中有一个位置是0说明abc.com一定没有加入过布隆过滤器因此一定不是这100亿个危险URL之一。如果三个位置全部为11 1 1只能说明这个URL“可能”属于危险URL。因为这些1也可能是其他URL产生的哈希结果。因此实际流程通常是用户访问URL↓布隆过滤器↓只要有一个bit0↓一定不在危险URL集合↓直接放行所有bit都是1↓可能是危险URL↓再去数据库或真实URL集合中确认↓确认危险后拦截一句话总结布隆过滤器用少量bit位代替大量原始数据可以快速判断一个URL“一定不在危险集合中”还是“可能在危险集合中”。核心特点判断不存在 - 一定不存在判断存在 - 可能存在有误判可能因此特别适合100亿URL这种“数据量巨大、查询次数很多”的场景。接下来介绍一下位图bit arr,或bit map。int [ ] 类型的数组设其长度为100占400Byte,共有[0~99]个格子每个格子4字节总共32bitlong [ ] 类型的数组设其长度为100占800Byte,共有[0~99]个格子每个格子8字节总共64bit那么能不能有以下数组bit [ ] 类型的数组设其长度为100占100/8Byte,共有[0~99]个格子总共1bit方法是用基础数据类型拼。示例代码package Class009; public class Code_BitMap { public static void main(String [] args){ int a0; //a 32bit int[] arrnew int[10];//32bit*10-320bit //arr[0] int 0~32 //arr[1] int 32~63 //arr[2] int 64~95 int i178;//想取得178个bit的状态 int numIndex178/32;//定位出应该在哪个数上找 int bitIndex178%32;//定位到哪个位 //拿到178位的状态这个数右移bitIndex位那么这个位的信息跑到了最右侧 // 然后把它和1与操作得到了这个位的状态 //这个位上是1那么s就是1这个位上如果是0那么s就是0 int s((arr[numIndex](bitIndex))1); //请把178位的状态改为1 //1先向左移bitIndex位然后将这个位上找到的数相或将老信息改成新信息 arr[numIndex]arr[numIndex]|(1(bitIndex)); //请把178位的状态改为0 //1先向左移bitIndex位后取反然后将这个位上找到的数相与将老信息改成新信息 i178; arr[numIndex]arr[numIndex](~(1bitIndex)); //请把178位的状态拿出来 i178; //bit 0 1 int bit(arr[i/32](i%32))1; } }解释可以直接把 Bitmap 理解成用一个 int 的 32 个二进制位分别保存 32 个状态。 例如 int[] arr new int[10]; 一个 int 有 32bit所以 arr[0] 管理第 0~31 位 arr[1] 管理第 32~63 位 arr[2] 管理第 64~95 位 ... arr[5] 管理第 160~191 位 现在 i 178 先定位 numIndex 178 / 32 5 bitIndex 178 % 32 18 所以第178个状态其实就是 arr[5] 的第18个bit 一、查询第178位的状态 代码 int s (arr[5] 18) 1; 假设 arr[5] 的二进制状态是 00000000 00000100 00000000 00000000 ↑ 第18位是1 用汇编思想理解 MOV EAX, arr[5] SHR EAX, 18 也就是把整个32位数据向右移动18位。 原来 00000000 00000100 00000000 00000000 ↑ 第18位 右移18位以后 00000000 00000000 00000000 00000001 ↑ 最低位 目标bit被移动到了最右边。 然后 AND EAX, 1 即 00000000 00000000 00000000 00000001 00000000 00000000 00000000 00000001 ----------------------------------- 00000000 00000000 00000000 00000001 所以 s 1 说明第178位状态是1。 如果第178位原来是0 00000000 00000000 00000000 00000000 右移18位后最低位也是0 00000000 00000000 00000000 00000000 再 1 结果 0 所以查询可以理解成 右移 把目标bit搬到最右边 1 只保留最右边这一位 因此 (arr[i / 32] (i % 32)) 1 就是“取出第i位的状态”。 二、把第178位状态改成1 代码 arr[5] arr[5] | (1 18); 先看 1 18 汇编思想 MOV EAX, 1 SHL EAX, 18 最开始 00000000 00000000 00000000 00000001 左移18位 00000000 00000100 00000000 00000000 ↑ 第18位是1 这个数叫“掩码”。 假设原来的 arr[5] 00000000 00000000 00000000 00001010 和掩码做 OR 原数据 00000000 00000000 00000000 00001010 掩码 00000000 00000100 00000000 00000000 OR 00000000 00000100 00000000 00001010 ↑ 第18位变成1 为什么 因为 0 | 1 1 1 | 1 1 所以目标位置无论原来是0还是1最后一定是1。 而其他位置掩码都是0 x | 0 x 所以其他bit保持不变。 因此 arr[i / 32] | 1 (i % 32); 意思就是 制造一个“只有目标位置是1”的掩码 然后用 OR 把目标bit打开。 三、把第178位状态改成0 代码 arr[5] arr[5] (~(1 18)); 先生成 1 18 得到 00000000 00000100 00000000 00000000 ↑ 1 然后取反 ~(1 18) 得到 11111111 11111011 11111111 11111111 ↑ 0 也就是说 目标位置 0 其他位置 1 假设原数据 00000000 00000100 00000000 00001010 ↑ 第18位为1 做 AND 原数据 00000000 00000100 00000000 00001010 掩码 11111111 11111011 11111111 11111111 AND 00000000 00000000 00000000 00001010 ↑ 第18位被清零 因为 x 0 0 x 1 x 所以 目标位置和0与 - 强制变成0 其他位置和1与 - 保持原值 因此 arr[i / 32] ~(1 (i % 32)); 意思就是 先制造一个“只有目标位置是0”的掩码 再通过 AND 把目标bit关闭。 四、完整例子 假设 int[] arr new int[10]; int i 178; 开始时 arr[5] 00000000 00000000 00000000 00000000 第178位状态 0 执行 arr[5] | (1 18); 变成 00000000 00000100 00000000 00000000 ↑ 第178位1 查询 (arr[5] 18) 1 过程 00000000 00000100 00000000 00000000 ↓ 右移18位 00000000 00000000 00000000 00000001 1 结果 1 然后执行 arr[5] ~(1 18); 变成 00000000 00000000 00000000 00000000 再次查询 (arr[5] 18) 1 结果 0 最终可以这样记 查询某位 右移 - 把目标bit移动到最右边 1 - 只保留这一位 设置为1 1左移 - 制造目标位为1的掩码 OR - 把目标位强制变成1 设置为0 1左移 - 找到目标位 取反 - 让目标位变成0其余都是1 AND - 把目标位强制变成0 从汇编角度可以近似理解成 查询 MOV SHR AND 置1 MOV SHL OR 置0 MOV SHL NOT AND 所以 Bitmap 的本质就是 利用 CPU 的 SHL、SHR、AND、OR、NOT 等位运算指令直接操作整数内部的某一个二进制位。最后来解释布隆过滤器。leetcode705布隆过滤器可以看成一个大位图长度为m类型为bit,占用m/8字节的内存同时有k个哈希函数。第一个url,记为u1,先通过哈希函数f1得到out1,out1%m,得到它在0~m-1中的位置(哪个格子)接着把这个位置描黑第一个url同样,记为u1,先通过哈希函数f2得到out2,out2%m,得到它在0~m-1中的位置(哪个格子)接着也把这个位置描黑......假设有k个哈希函数那么url1会调用k个哈希函数得到k个位置有可能两或多个个格子一样也有可能都不同同样的url2,也调用k个哈希函数得到k个位置也把这些位置描黑......直到url(100亿)每个url都如此操作。这样布隆过滤器版本的黑名单集合建立好了。接下来我们对这个黑名单进行查询对于某一个urlx,算k个哈希函数得到的值都%m,然后在位图中拿状态只有位图中全是1的时候那么urlx在这个集合里面有一个位置不是1那么urlx就不在这个集合里面。一旦有一个位置是白那么就说明这个urlx之前没有映射过则必然不存在于黑名单中。失误的情形第一在于m的数量非常小经过100亿次映射的时候m个格子都被占满了无论怎么查都是黑名单第二在于哈希函数k的多少如果k的规模很大那么特征采集的点就会变得非常密集第一种是有决定作用的而第二种中的k应该根据m的大小来定多少。设m是轴P是失误比率为y轴在n100亿时P与m成反比例关系设k是轴P是失误比率为y轴在n100亿时P与k成开口向上的二次函数关系关系。利用两个图像可以决定m和k的关系。如图所示接下来给出三个公式用以设计布隆过滤器面试套路数学推导略。条件n样本量P失误率判断是不是集合查询结构有没有失误率限制注意它与单样本大小无关。1m-n*lnp/(ln2)^2,如果失误率为0.0001,带入算出m的值除以8得到比特值接着计算出n约为26G,2kln2*m/n0.7*m/n向上取整3P(真)1-e^(-n*k(真)/m(真))^(k(真))示例三个公式可以分别理解成三个问题 条件 n 样本量 P 允许的误判率 m 位图长度单位是 bit k 哈希函数个数 注意布隆过滤器只关心“有多少个样本”和“允许多大的误判率”与单个样本本身占多少字节基本无关。 1计算位图大小 m 公式 m -n * ln(P) / (ln2)^2 作用 已知 n 样本数量 P 允许误判率 求 需要多大的位图 m 计算样例 假设 n 100亿 10,000,000,000 P 0.0001 已知 ln(0.0001) ≈ -9.2103 ln2 ≈ 0.6931 (ln2)^2 ≈ 0.48045 代入 m -100亿 × (-9.2103) / 0.48045 ≈ 1917亿 bit 所以需要的位图长度约为 1917亿 bit 转换成字节 1917亿 / 8 ≈ 239.6亿 Byte 约 23.96 GB 所以可以记 100亿个样本 允许误判率 0.0001 大约需要 24GB 的位图。 注意 m / 8 得到的是 Byte不是 bit。 2计算哈希函数数量 k 公式 k ln2 * m / n 也可以近似写成 k ≈ 0.7 * m / n 作用 已经知道位图大小 m 和样本量 n 计算每个样本应该经过多少个哈希函数最合适。 计算样例 沿用上面的数据 m ≈ 1917亿 bit n 100亿 代入 k 0.693 × 1917亿 / 100亿 0.693 × 19.17 ≈ 13.29 所以最优的哈希函数数量大约是 13.29个 但哈希函数不可能有0.29个所以只能取整数。 可以取 13个 或者按照“向上取整”的规则 14个 也就是说 每加入一个URL大约计算13~14次哈希 在位图中设置13~14个位置。 3计算实际误判率 P(真) 公式 P(真) (1 - e^(-n*k(真)/m(真))) ^ k(真) 作用 实际程序中使用的 m 和 k 往往经过取整 所以用这个公式检查实际误判率到底是多少。 计算样例 假设最终实际采用 n 100亿 m(真) 1917亿 bit k(真) 13 代入 P(真) (1 - e^(-100亿 × 13 / 1917亿))^13 先算指数部分 100亿 × 13 / 1917亿 ≈ 0.678 所以 P(真) ≈ (1 - e^(-0.678))^13 ≈ 0.00010013 也就是 P(真) ≈ 0.010013% 非常接近最初要求的 P 0.0001 0.01% 如果实际使用14个哈希函数 k(真) 14 则 P(真) ≈ 0.00010079 也就是 约0.010079% 也非常接近目标。 三个公式可以这样记 第一步 n P ↓ 算m m -n * ln(P) / (ln2)^2 回答 “需要多大的位图” 第二步 m n ↓ 算k k ln2 * m/n ≈ 0.7 * m/n 回答 “需要几个哈希函数” 第三步 实际m 实际k n ↓ 算P真 P真 (1-e^(-nk/m))^k 回答 “最终真实误判率是多少” 完整样例 n 100亿 P 0.0001 第一步 m ≈ 1917亿 bit ≈ 24GB 第二步 k ≈ 13.29 取13或14 第三步 如果k13 P真 ≈ 0.00010013 ≈ 0.010013% 所以这个布隆过滤器基本满足最初要求。3.一致性哈希原理主要是用来讨论数据服务器的问题。可以将它们分为逻辑端和数据端两部分逻辑端是可以一致的但数据端可能会分布式存储机器1机器2......机器n比如将姓名表中的“namekey”字段记录通过hash函数得到不同的hash值存到不同的机器上(每个机器存储不同hash值的字段)。hash key的选择要让不同机器上高中低频率的数据尽量平衡比如一个几百万行的表name,country,sex,如果选择country字段那么印度和中国的数据最多对应服务器负载大如果选择sex那么通常情况下只有两种划分两台服务器负载特别大如果选择name划分由于A-Z均匀分布可以做到不同数据服务器负载均衡。。此外如果开拓海外市场数据量扩充要求增加几台数据机器所有数据机器都需要重新计算hash值来存储数据数据迁移的代价特别大。那么如何减少这个代价此时需要采用一致性hash原理。在md5算法中输入经过映射可以得到0~2^64-1个范围内的数我们把这2^64个数想象成一个环。假设有三台机器:m1,hostname1;m2,hostname2;m3,hostname3。h1经过hash运算可以得到hashcode;h2经过hash运算可以得到hashcode;h3经过hash运算可以得到hashcode。将这三台机器插入到这个环里面去m1-hash-10亿m2-hash-5347亿m3-hash-7万万亿按照顺时针依次排列(m1~m2)归属于m2,(m2~m3)归属于m3,(m3~m1)归属于m1。假设“zuo”这个字符串经过hash运算后得到一个数假设是3457亿就按照之前机器的分布顺时针找离它最近的机器也就是m2。此时假设加入一台m4机器3万万亿位于m2和m3之前则数据划分区域变成了(m1~m2)归属于m2,(m2~m4)归属于m4,(m4~m3)归属于m3(m3~m1)归属于m1.此时m4只需要向m3索取(m2,m4)之间的数据即可实现少量的数据迁移这样比全量的数据迁移少很多开销。就以上的讨论此时假设减少一台m4机器3万万亿位于m2和m3之前则数据划分区域变成了(m1~m2)归属于m2,(m2~m3)归属于m3,(m3~m1)归属于m1。此时m3只需要向m4索取原来(m4,m2)之间的数据即可实现少量的数据迁移这样比全量的数据迁移少很多开销。但是这样存在潜在的划分问题:机器数量很少的时候做不到环的均衡即使之前能够做到环的均衡但是如果增加或减少机器的时候环就不均衡了。解决方案虚拟节点技术。假设有三台机器拥有1000个字符串m1(a1,a2,a3,......a1000),m2(b1,b2,b3,......b1000),m3(c1,c2,c3,......c1000假设有3台真实机器M1 M2 M3不是让每台机器在环上只有一个位置而是创建很多虚拟身份M1#1 M1#2 M1#3 ... M1#1000 M2#1 M2#2 ... M2#1000 M3#1 M3#2 ... M3#1000然后分别 hashhash(M1#1) hash(M1#2) ...这样一共3000个虚拟节点被均匀打散到环上。例如M1#2 ● M3#1 M2#3 ● ● M2#1 M1#1 ● ● M1#3 M3#2 ● ● M2#2 ●虽然物理上只有3台机器逻辑上环中却有几千个节点。所以每台机器会负责很多零散的小区间而不是一个巨大的连续区间。结果就更加接近M1 ≈ 1/3 M2 ≈ 1/3 M3 ≈ 1/3如果要增加一台机器(m4)则设置一个虚拟节点按照比例索取m1,m2,m3上的字符串如果要减少机器(m4)则去掉虚拟节点按照比例将自己的字符串分配给m1,m2,m3。M4的多个虚拟节点随机/均匀地落在环的不同位置每个虚拟节点自动接管它前面的区间。因为虚拟节点很多统计结果自然接近从多台机器分别拿走一部分数据。此外如果不同机器的性能不同比如m1可以管理1500个字符串m2可以管理1000个字符串m3只能管理500个字符串还可以利用虚拟节点来调整m1和m3的管理的数据的量以上是一致性哈希和redis集群之间的区别是经典一致性哈希hash环 虚拟节点Redis Cluster固定16384个hash slots 节点负责若干slots
