问题一：哈希函数和哈希表
哈希函数的性质：①输入域无穷大；②输出域有穷尽；③哈希函数不是随机的，多次相同输入计算返回值都一样；④有多个不同输入计算的哈希值相同，即哈希碰撞；⑤哈希函数的离散性，即所有输入计算后会在输出域中均匀分布
哈希函数的输出与输入域中原有规律无关，可以用来打乱原有数据分布，这也是输出域中均匀分布的原因。对于哈希函数的输出域S，如果所有输出值对m取模，得到的0~m-1的输出域也是均匀分布的
用一个哈希函数构造多个哈希函数，并且这些哈希函数之间相互独立：例如把16位输出分为前8位和后8位，构造哈希函数h1和h2，然后以h1+a*h2（a任意取整数）的方式构造，这样构造的哈希函数和h1，h2独立。或者准备两个哈希函数作为种子按上述方式生成新哈希函数。因为哈希函数每一位和其他位之间也是独立的，可以理解成哈希函数是16个输出为1位的函数拼成的哈希函数（16位是md5算法）
哈希表：这块有点多来不及记录，哈希表的增删改查是O(1)，即使考虑了扩容过程
问题二：设计RandomPool结构
设计RandomPool结构
准备两张哈希表map1和map2，size记录数据数目，一个map存放key-size，另一个放size-key，插入时两边一起插，删除时每次删除后把最后一个位置填到删除位置，以后随机选择的时候还是在连续的区域选择
问题三：布隆过滤器-黑名单问题
布隆过滤器有失误率，失误类型是即使不在黑名单中也可能判断在黑名单中（不会把黑名单中的判断成不是的），布隆过滤器即bit类型的map：生成一个m长度的bit类型的数组，要判断的东西计算哈希函数对m取模，然后在数组中相应位置置1，总共经过k个哈希函数处理，并在每个位置置1（可能重复），判断黑名单时对k个哈希函数计算，如果数组中每个位置都置1则是黑名单（相同的输入计算的输出肯定是一样的），但凡有一个不是1则不在黑名单。数组空间越大则失误率越小，即不在黑名单中的判断错误情况。
失误率公式
其中n为样本量，p为预期失误率
哈希函数个数
失误率
问题四：认识一致性哈希
服务器设计中，使数据迁移代价很低，同时负载均衡：把哈希函数的返回值想象成环，计算哈希函数后不取模，然后顺时针找到里计算结果最近的位置（用二分的方法找刚刚大于计算结果的位置），这样增加机器的迁移代价比较小
一致性哈希
虚拟节点技术：从真实的物理机器生成大量虚拟节点，然后分布在环上（例如m1生成m11，m12，m13...），这样三个机器基本上占据环的比重基本相同。虚拟节点技术可以解决：①负载不均衡；②负载均衡后扩容又使负载不均衡。
网友评论