算法进阶--第一章--哈希函数
-- 哈希函数与哈希表
-- 位图与布隆过滤器详解
-- 一致性哈希结构
1.经典哈希函数
1)input 无穷大 hashcode f(string)
2)output S域·
3)输入一样输出一样
4)当输入不一样,输出可能一样 哈希碰撞
5) 离散 均匀输出 打乱输入规律 模m 0~m-1
哈希表
效率变差,哈希表的扩容 在线离线 O(1)
哈希函数分流 大数据一半都是
2.
设计RandomPool结构
【题目】设计一种结构,在该结构中有如下三个功能:insert(key):将某个key加入到该结构,做到不重复加入。
delete(key):将原本在结构中的某个key移除。getRandom():等概率随机返回结构中的任何一个key。
【要求】Insert、delete和getRandom方法的时间复杂度都是O(1)
add,random
删除,用最后一条填取删掉的地方,size -1
3.
认识布隆过滤器
解决一个问题:
原理:每个URL经过几个哈希函数后对应位置上描黑 ,所有黑名单每个URL描黑后整个布隆过滤器的一个位类型的数组相应位置被描黑,检查URL:计算k个哈希函数对应的位置,所有的位置都是黑的则认为是名单上的。否则不在
第一个公式:比特数组开多大由样本量和预期失误率来决定。 /8 都是字节
哈希函数个数计算取整,第三个公式预期失误率。
4.
认识一致性哈希
经典服务器抗压结构:负载均衡
问题:扩容
引入一致性哈希:降低迁移数据代价,又负载均衡
问题:机器数量少时,不一定均分,负载会有问题,即使均匀,加一个机器就不均匀了。
一个技术:虚拟节点技术
小概率:哈希碰撞
5.
岛问题
一个矩阵中只有0和1两种值,每个位置都可以和自己的上、下、左、右四个位置相连,如果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?
举例:
0 0 1 0 1 0
1 1 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
这个矩阵中有三个岛。
边界信息如何合并:
6.
认识并查集结构
1)两个元素是否是一个集合
2) 合并两个元素所在集合
优化:查找后打平