哪里做网站百度收录块,手机网站小程序,商派商城网站建设方案,九江网站设计公司两周之前——爬虫的原理就不细说了#xff0c;无非是通过种子URL来顺藤摸瓜#xff0c;爬取出网站关联的所有的子网页#xff0c;存入自己的网页库当中。但是#xff0c;这其中涉及到一个小小的问题......URL去重方案第一版#xff1a;HashSet创建一个HashSet集合#xf… 两周之前——爬虫的原理就不细说了无非是通过种子URL来顺藤摸瓜爬取出网站关联的所有的子网页存入自己的网页库当中。但是这其中涉及到一个小小的问题......URL去重方案第一版HashSet创建一个HashSet集合把每一个URL字符串作为HashSet的key插入到集合当中利用HashSet的Key唯一性来对URL做去重。这个方案看似没毛病但是经过几轮压测之后......每一个URL按照20字节来算一亿个URL就是20亿字节也就是大约占了1.8G以上的空间。这么大的HashSet集合显然是不可取的。于是小灰又思考了一番......URL去重方案第二版BitmapBitmap是一种节省空间的数据结构不太了解的朋友可以看看往期的相关文章漫画Bitmap算法 整合版具体怎么做呢获取每一个URL的HashCode根据HashCode的值来插入到Bitmap的对应位置。如果要插入位置的值已经是1说明该URL已重复。使用Bitmap以后每一个Url只占了1个Bit一亿个Url占约12MB。假设整个Bitmap的空隙比较多额外空间占90%总空间也不过是120MB相比HashSet来说大大节省了内存空间。这个方案貌似好了很多可是......String的Hashcode方法虽然尽可能做到均匀分布但仍然免不了会有冲突的情况。HashCode的冲突意味着什么呢意味着两个原本并不相同的Url被误判为重复Url。———————————————听起来有点绕我们来详细描述一下1.把第一个URL按照三种Hash算法分别生成三个不同的Hash值。2.把第二个URL也按照三种Hash算法分别生成三个不同的Hash值。3.依次比较每一个Hash结果只有当全部结果都相等时才判定两个URL相同。具体怎样映射呢流程如下1.创建一个空的Bitmap集合。2.把第一个URL按照三种Hash算法分别生成三个不同的Hash值。3.分别判断517 9 在Bitmap的对应位置是否为1只要不同时为1就认为该Url没有重复于是把5179的对应位置设置为1。4.把第二个URL按照三种Hash算法分别生成三个不同的Hash值。5.分别判断1012 9 在Bitmap的对应位置是否为1只要不同时为1就认为该Url没有重复于是把1012 9 的对应位置设置为1。6.把第三个URL按照三种Hash算法分别生成三个不同的Hash值。7.分别判断416 11 在Bitmap的对应位置是否为1只要不同时为1就认为该Url没有重复于是把416 11 的对应位置设置为1。8.把第四个URL按照三种Hash算法分别生成三个不同的Hash值。9.分别判断517 9 在Bitmap的对应位置是否为1。判断的结果是 517 9 在Bitmap对应位置的值都是1所以判定该Url是一个重复的Url。1.URL按照三个Hash算法得到三个结果。2.分别判断1012 17 在Bitmap的对应位置是否为1。判断的结果是 1012 17 在Bitmap对应位置的值都是1所以判定该Url是一个重复的Url。—————END—————算法图解如何找出栈中的最小值链表反转的两种实现方法后一种击败了100%的用户JDK 竟然是这样实现栈的关注下方二维码订阅更多精彩内容
