摘要：答案使用，申请一个长度为类型的，每个位置只表示或，该数组占用空间约。遍历亿个数，当前数为，落在区间，对应。
过滤100亿黑名单 题目
假设有100亿个URL的黑名单，每个URL最多占用64B，设计一个过滤系统，判断某条URL是否在黑名单里。
要求不高于万分之一的判断失误率；额外内存不超过30GB
答案100亿个64B的URL需要640GB的内存，显然直接存哈希表不合理。考虑布隆过滤器，假设有一个长度为m的bit类型数组，如图所示：
输入阶段：
有k个哈希函数，函数的输出域S大于或等于m，假设哈希函数彼此独立，对于同一个输入(以字符串表示的URL)，经过k个哈希函数的计算结果也是相互独立。对计算的每一个结果Mod m，将bit array上对应的位置置1，如下：
一个输入对象会将bitmap某些位置涂黑，处理完所有输入对象，会将bitmap相当多位置涂黑，至此，布隆过滤器生成完毕，代表之前所有输入对象的集合。
20亿个数中出现最多的数 问题包含20亿个全是32位整数的大文件，在其中找出出现次数最多的数。
要求内存限制：2GB
答案将20亿个数用hash函数分成16个文件。然后统计每个小文件中，哪个数字出现次数最多。最后再比较每个小文件的次数最多的数。（本题分成16个也是根据题目来的。考虑最极端情况。20亿个数都不同）32位的整数要占4b,key占4b，value占4b。共8b。内存只有2G。所以大概每个小文件存2亿条。就需要10个小文件。但是hash函数必须2的n次方。所以2的4次方。16个
40亿个数找没出现的数 问题有一个包含40亿个无符号整数的文件，最多使用1GB内存，找到所有没出现的数
分析最差情况，40亿个数都不同，哈希表保存出现过的数，需要内存4B*40亿，大约16GB内存。
答案使用bitmap，申请一个长度为4294967295bit类型的bitArray，每个位置只表示0或1，该数组占用空间约500MB。遍历这20亿个数，例如遇到7000，就将bitArray[7000]置1。遍历完成后，再依次遍历bitArray，哪个位置没有置1，哪个数就不在40亿个数中。
40亿个数找第一个没出现的数 。内存只有10M 答案具体的，第一次遍历，申请长度64的整形数组countArr[0...63]，统计每个区间计数增加。例如，当前数是34225522090，34225522090/67108864=51，countArr[51]++。遍历完之后，必定有一个countArr[i]小于67108864，表示i区间内至少有一个数没出现过。此时countArr[]使用的内存是64*4B。
假设在37区间有一个数没出现，申请一个长度为67108864的bitmap，内存大约8MB，记为bitArr[0~67108863]。再一次遍历40亿个数，只关心37区间的数，记为num。将bitAry[num-6710886437]的值置位1。遍历完之后，bitArr必然有没有置1的位置，记为i，则6710886437+i就是没出现过的数。
找出100亿个重复URL以及搜索词汇topK问题 问题有一个包含100亿URL的大文件，每个URL占64B，找出重复URL；补充，找出top100搜索词汇
常规答案大文件通过哈希函数分配到不同机器
哈希函数将大文件拆分成小文件。
对于每一个小文件，利用哈希表遍历，找出重复的URL，或者分给机器或拆分文件完之后，进行排序，看是否有重复的URL。
补充问题的思路也是通过哈希函数分流，对于每个小文件，简历词频哈希表，建一个大小为100的小根堆，选出每个小文件的top100.每个小文件的top100进行外排序或者接着使用小根堆，就能得到100亿数据的top100.
出现两次的数以及中位数问题 问题有40亿个无符号32位整数，最多可以使用1GB内存，找出所有出现了两次的数；补充问题，最多使用10MB内存，找到40亿个数的中位数
答案第一个问题可以用bitmap做，申请长度为2?232bit的bitArr，2个bit表示一个数出现的词频。遍历40亿个数，假设出现num，将bitArr[2num]和bitArr[2num+1]设置为01，第二次出现，设置为10，第三次，设置为11。以后再遇到11的，就不做处理。遍历完成后，再遍历一次，若发现bitArr[2num]和bitArr[2num+1]是10，则num是出现了两次的数。
第二个问题，分区间讨论。长度为2MB的unsigned int数组占用8MB，将区间数目定位232/2M，取整为2148个区间，第0区间0~2M-1，第i区间2Mi~2M（i+1）-1
申请一个长度为2148的unsigned int整数数组arr[0..2147],arr[i]表示i区间有多少个数，arr占用内存小于10MB。遍历40亿个数，当前数num为num，落在区间(num/2M)，对应arr[num/2M]++。累加统计每个区间的累计数目，就能找到40亿个数的中位数。例如0~K-1区间数目个数为19.998亿，加上第K个区间就超过了20亿，说要中位数一定在K区间中，并且一定是第K区间的第0.002亿个数。
接着申请长度2M的unsigned int数组countArr[0..2M-1]，占用8MB。遍历40亿个数，只关心第K区间的数numi，countArr[numi-K*2M]++。统计完之后在第K区间找地0.002亿个数字即可。
一致性哈希分布式数据库集群缓存，例如memcached，将数据的id通过哈希函数转换为key，假设有N个机器，计算key%N，得到及其所属编号，增删改查都在这台机器上。一致性哈希能在机器扩容（N发生变化），使得不用重新计算一遍key%N
三台机器处于哈希环，id通过哈希映射为key，在哈希环中顺时针找距离最近的机器。
机器较少的时候可能会出现负载不均衡，如图所示：
答案引入虚拟节点，增加结点数
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/69607.html
摘要：实际中更多是作为其他数据结构的子结构，如哈希桶图的邻接表等等。实际中使用的链表数据结构，都是带头双向循环链表。 文章目录 一.算法的时间复杂度和空间复杂度1.算法...
摘要：综合上述缺点，小明痛定思痛，提出了经营方式二。当客户下单，小明按送达地点标注好，依次放在一个地方。因此，有强一致性要求的数据，不能放缓存。迅速判断出，请求所携带的是否合法有效。 showImg(https://segmentfault.com/img/bVbvHHL?w=1341&h=448); 绝大部分写业务的程序员，在实际开发中使用 Redis 的时候，只会 Set Value 和...
摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享 目录： 印象中的头条 面试背景 准备面试 ...
摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享目录：印象中的头条面试背景准备面试头条一面（Java+项目）头条...
摘要：本章会说明什么是内存泄漏，为什么发生，以及如何防止它们。但是，未使用的对象并不是全部未被引用，其中一些被引用这是内存泄漏的来源。注意集合类，如等，因为它们是发现内存泄漏的常见地方。如果一个类管理自己的内存，程序应该对内存泄漏保持警惕。 内存管理是Java最重要的优势之一，你只需创建对象，Java垃圾收集器会自动负责分配和释放内存。但是，情况并不那么简单，因为在Java应用程序中经常发生...
阅读 2744·2023-04-26 00:23
阅读 3229·2021-09-13 10:28
阅读 1988·2021-08-31 14:18
阅读 2625·2019-08-30 15:54
阅读 1756·2019-08-30 15:43
阅读 1135·2019-08-29 16:56
阅读 2656·2019-08-29 14:16
阅读 1922·2019-08-28 17:51
