45 | 位图：如何实现网页爬虫中的URL去重功能？

精选留言(57)

• 

  DreamYe

  bloom filter: False is always false. True is maybe true.

  2019-01-09

  

   87
• 

  五岳寻仙

  课后思考题1
  
  传统的做法：1亿个整数，存储需要400M空间，排序时间复杂度最优 N×log(N)
  
  使用位图算法：数字范围是1到10亿，用位图存储125M就够了，然后将1亿个数字依次添加到位图中，然后再将位图按下标从小到大输出值为1的下标，排序就完成了，时间复杂度为 N

  2019-01-09

   6

   45
• 

  www.xnsms.com小鸟接码

  位图代码的实现一开始没看懂，请教了下身边一位大神同事才搞懂，原来char类型存储数字的时候，只占1个字节，也就是8位。所以计算的时候都是除8或者模8。希望我的回答可以帮助其他跟我一样基础薄弱的同学，共同进步

  2019-01-09

   1

   27
• 

  越过山丘

  第一题，数字重复了，有什么好方法处理吗

  作者回复: 对于重复的 可以再维护一个小的散列表 记录出现次数超过1次的数据以及对应的个数

  2019-01-10

   2

   17
• 

  ban

  这个char代码最好还是用图解比较好理解，纯代码看不懂。
  我这里有另外一个位的图解计算过程，再去看代码，你就会秒懂
  https://mp.weixin.qq.com/s/xxauNrJY9HlVNvLrL5j2hg

  2019-01-11

  

   15
• 

  传说中的成大大

  1亿个整数 如果完全读入内存大约是0.4G的样子 可以直接快排排序
  通过位图方式开辟一个十亿大小的位图缩小到0.125g的样子,虽然数字只有一亿个,但是我们却要检查1到10亿之间的数字是否存在再输出即可达到排序

  2019-01-09

  

   6
• 

  司霖

  将数字 A 的第 k 位设置为1：A = A | (1 << (k - 1))
  将数字 A 的第 k 位设置为0：A = A & ~(1 << (k - 1))
  检测数字 A 的第 k 位：A & (1 << (k - 1)) != 0
  用于理解bitmap中代码

  2019-03-12

  

   4
• 

  猫头鹰爱拿铁

  思考题1的java实现。
  import java.util.Random;
  
  public class BitMap {
  private int[] bits;
  private int[] input;
  
  public BitMap(int n, int[] input) {
  bits = new int[n];
  this.input = input;
  }
  
  public void setBit(int n) {
  int offset = n / 32;
  int value = n % 32;
  bits[offset] |= (1 << value);
  }
  
  public boolean getBit(int n) {
  int offset = n / 32;
  int value = n % 32;
  return (bits[offset] & (1 << value)) != 0;
  }
  
  /**
  * 排序
  *
  * @param n
  * 是数组的存储整数范围
  * @param input
  * 输入的未排序数组
  * @return 有序的数组范围
  */
  public int sort(int n, int[] input) {
  int j = 0;
  for (int i = 1; i <= 10 * n; i++) {
  if (getBit(i)) {
  input[j++] = i;
  }
  }
  return j;
  }
  
  public static void main(String[] args) {
  int n = 1000000000;
  int[] input = new int[n];
  Random r = new Random();
  for (int i = 0; i < n; i++) {
  input[i] = r.nextInt(10 * n - 1) + 1;
  }
  BitMap bitMap = new BitMap(10 * n, input);
  for (int i = 0; i < n; i++) {
  bitMap.setBit(input[i]);
  }
  int size = bitMap.sort(n, input);
  for (int i = 0; i < size; i++)
  System.out.print(input[i] + ",");
  }
  }
  

  2019-01-09

  

   4
• 

  Kudo

  直观上感觉位图有点像学排序时桶的概念，所以使用位图也可以实现类似于桶排序的效率。

  2019-01-09

  

   4
• 

  Sharry

  这个位图很精妙，因为编程语言没有提供bit类型，所以使用byte进行位运算的方式，巧妙的利用每一位，以达到减少内存开辟的消耗的问题

  2019-01-09

  

   4
• 

  Flash

  争哥，我想到了通过hash算法将String转换为int类型数据，然后再将int数据位运算存储到位图上，可是这个hash算法，也可能会出现散列冲突啊，不同的String有可能是同一个int，然后反应到位图上就是相同的bit位了。

  2019-03-29

  

   3
• 

  Costar

  有个问题怎么解决的？Bloom filter删除数据时，不能把bit位置0

  作者回复: 一般不用来删除，如果非要支持删除，可以再弄个数据结构记录删除的数据。

  2019-07-02

  

   2
• 

  李斌

  我们在信息流推荐系统中用 bloom filter 过滤推荐历史，在工程上使用 RedisLibs 的 ReBloom

  2019-06-05

  

   2
• 

  公号-代码荣耀

  在线上环境，我们采用redis的set进行去重，效果还是不错的

  2019-01-12

   1

   2
• 

  煦暖

  争哥，位图的代码理解了好久还没懂(；′⌒`)，能加几行注释吗？？

  作者回复: 好的 我去补充下

  2019-01-11

  

   2
• 

  阮雅

  王争哥，您好。你画这个图，用的啥软件画的啊？ 比普通的黑白图更容易理解。望求解！感激不尽！

  作者回复: ipad paper

  2019-01-09

  

   2
• 

  www.xnsms.com小鸟接码

  思考题1:用10亿个位的位图存储这1亿个数，然后直接按脚标从0到10亿顺序遍历整个位图，如果位为1，则打印脚标，打印出来的就是排好序的1亿个数字
  
  思考题2:用位图的话。一个机器应该就够了

  2019-01-09

  

   2
• 

  marvinle

  老师，按照你的讲解我写了一个简单的布隆过滤器， 使用了3个简单的哈希函数，判错率在0.9左右
  不知道是否是属于偏高了，这是代码，可以的话帮忙看看是否正确https://github.com/MarvinLe/tools/tree/master/BloomFilter

  作者回复: 判错旅太高了 哈希函数不够随机均匀？位图不够大？

  2019-01-09

  

   2
• 

  雍鹏亮

  思考题1和桶排序一样吧，把对应的的桐位置1，然后依次读取

  2019-01-22

  

   1
• 

  NeverMore

  对布隆过滤器的理解更深了。

  2019-01-11

  

   1