极度节约内存的算法 --位图

快来打我* 2023-06-23 03:00 195阅读 0赞

位图：  
网页爬虫，获取页面中的url，进一步爬取内容。但是需要避免重复爬取，所以需要查询是否已经爬取并保存到查询记录中。  
如果有10亿个url，怎么处理？  
hash -耗内存-> 位图 -位太多-> 布隆  --> 多hash

散列表  
10亿Url 一个url 50字节，共500亿字节。  
50G内存：分片，分到10个机器，每个机器5G，可以接受。  
分片 + 散列表。

如果用链表处理冲突，那么：  
1） 链表对CPu缓存不友好  
2） 链表url和判重的url需要逐个比较，大小50字节的字符串比较，耗时

节约内存的方案-布隆过滤器，基于位图  
问题：1千万个整数，整数范围1-1亿，如何快速查找该整数是否在1千万个整数之中呢？  
解决：申请1亿，数据类型位boolean的数组；将该1千万个整数作为下标，对应的数组值设置为true。如存在整数5，则array\[5\]=true;  
当查询k是否在1千万整数之中时，去除array\[k\],如果值为true，则存在，否则不存在

位图：  
boolean是1字节，本质上一个二进制位（bit）就可以了，如何用编程语言表示二进制呢？  
假设用char来处理，一个char是2字节，那么可以用来表示16个布尔值，如果想设置第n(1-16)位为1，只需要  
char |= 1>>n  
public class BitMap\{  
    char\[\] bytes;//2字节  
    int nBits;

public BitMap(int nBits)\{  
        this.nBits = nBits;  
        bytes = new char\[nBits/16 + 1\]  
    \}

public void set(n)\{  
        if(n > nBits) return;  
        int bitIndex = n%16;  
        int byteIndex = n/16;  
        char\[byteIndex\] |= (1<<bitIndex);  
    \}

public boolean get(n)\{  
        if(n > nBits) return;  
        int bitIndex = n%16;  
        int byteIndex = n/16;  
        return char\[byteIndex\] & (1<<bitIndex) !=0;  
    \}  
\}

如果整数范围不是1-1亿，而是1-10亿，那数组就会需要扩大10倍，会多浪费很多空间。  
布隆过滤器用于解决刚刚的问题。  
还是刚刚问题，但是数据范围是1-10亿，那布隆过滤器的做法是：  
仍然使用1亿个二进制大小的位图，那此时会存在如下场景，数字1/和数字1亿+1岂不是放到相同的位置了？  
这里布隆过滤器的做法是：  
放入某值n：使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，我们分别记作 X1，X2，X3，…，XK。我们把这 K 个数字作为位图中的下标，将对应的 BitMap\[X1\]，BitMap\[X2\]，BitMap\[X3\]，…，BitMap\[XK\] 都设置成 true，也就是说，我们用K个二进制位，来表示一个数字的存在。  
查询值n是否存在：我们用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，YK。我们看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明，这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。  
但是会存在误判的场景，例如a、b、c三个值，  
其中a的hash结果为h1，h2，h3，b的hash结果为h2,h3,h4;c的hash结果为h1，h2,h4;  
那么仅放入a、b，不放入c，此时那c取判断，会得到错误的结果:c已放入。  
布隆的误判仅仅有一个方面，未放入判定为放入了，如果其结果是未放入，那该结果一定是准确的。

布隆过滤器适用场景：适用于判定结果不要求完全准确的大规模判重场景。

1亿个整数，范围1-10亿，如何快速排序？  
使用用大小为10亿的boolean数组，遍历存在置为true，  
如果数据上面1亿个数据有重复的怎么办？  
出现两次及以上的：  
可以单独维护一个散列表存储数值，以及出现的次数。放入之前判断现在是否存在，已存在则维护该散列表。