位图

应用场景

同一个网页链接被包含在多个页面中时，会导致爬虫在爬取的过程中，重复爬取相同的网页，如何避免这些重复的爬取呢？

解决方案

记录已经爬取过的URL，爬取新网页前查看是否爬取过
已爬取过则忽略
未爬取过则先爬取后记录

注意点：

查询和添加操作要高效
上亿的网页，消耗内存非常高，存储效率要高

满足上述需求的数据结构有：

散列表
红黑树
跳表

在支持快速查询和插入的同时需要关注内存的消耗。

假设有10亿网页，一条URL平均长度64byte，全部存储起来需要大约60GB的内存。散列表需要保证较低的装填因子，采用链表法则还需要保存指针，实际使用的存储空间可能需要超过100GB。大型搜索引擎会使用分治的思想将这100GB的数据保存在多台服务器上。

分治+散列表的思路可以实现，那么在添加、查询和内存消耗上是否还有优化空间？

注意：时间复杂度只是表示执行时间随数据规模的变化趋势，并不能度量在特定的数据规模下，代码执行时间的多少。在数据量很大的情况下，常数、系数和低阶的优化都能带来非常可观的收益。

性能优化

执行效率

分治+散列表思路中耗时的点在于：通过哈希函数定位到某个链表之后，还要依次比对每个链表中的 URL。

一方面，链表中的结点在内存中不是连续存储的，不能一下子加载到 CPU 缓存中，没法很好地利用到 CPU 高速缓存，所以数据访问性能方面会打折扣。
另一方面，链表中的每个数据都是 URL，而 URL 不是简单的数字，是平均长度为 64 字节的字符串，要让待判重的 URL，跟链表中的每个 URL，做字符串匹配。这样一个字符串匹配操作，比起单纯的数字比对，要慢很多。

内存消耗

在内存消耗方面的优化，可以将散列表更换为布隆过滤器。布隆过滤器基于位图，且对位图进行了改进。

问题

如何在数据范围是1~10亿之间的1千万个整数中快速查找某个整数是否存在。

散列表可以解决，位图也可以解决。

解决方案

使用位图来解决。

申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组
将这 1 千万个整数作为数组下标，将对应的数组值设置成 true，如整数 5 对应下标为 5 的数组值设置为 true（array[5]=true）
查询某个整数 K 是否存在，只要将对应的数组值 array[K] 取出来判断是否为true
如果等于 true，说明存在整数 K
如果不等于true，说明不存在整数 K

注意：很多编程语言中提供的布尔类型，大小是 1 byte，并不能节省太多内存空间。实际上，表示 true 和 false 两个值，只需要用一个二进制位（bit）就可以。

如何通过编程语言，来表示一个二进制位（bit）可以使用位运算。

借助编程语言中提供的数据类型，比如 int、long、char 等类型，通过位运算，用其中的某个位表示某个数字。如下示例：

// byte占1个字节，8bit
type BitMap struct {
    bytes []byte
    nbits int
}

func NewBitMap(bits int) *BitMap {
    return &BitMap{
        bytes: make([]byte, bits/8+1),
        nbits: bits,
    }
}

func (b *BitMap) set(k int) {
    if k > b.nbits {
        return
    }
    byteIndex := k / 8
    bitIndex := k % 8
    b.bytes[byteIndex] |= 1 << bitIndex
}

func (b *BitMap) get(k int) bool {
    if k > b.nbits {
        return false
    }
    byteIndex := k / 8
    bitIndex := k % 8
    return (b.bytes[byteIndex] & (1 << bitIndex)) != 0
}

位图通过数组下标来定位数据，所以访问效率非常高
每个数字用一个二进制位（bit）表示，在数字范围不大的情况下，需要的内存空间非常节省

数据范围是1~10亿之间的1千万数据：

散列表存储：每个数据占32位（4个字节），总共有1千万个数据需要大约40MB
位图存储：每个数据占1位，数据最大范围1亿需要大约12.5MB

如果数据的范围更大，是1~10亿，数据量还是1千万，那么位图存储的空间是125MB，这就远大于散列表需要的存储空间。

这是就需要布隆过滤器来解决数据范围非常大这个问题了。

布隆过滤器

数据范围是1~10亿之间的1千万数据，使用布隆过滤器的处理策略是：

创建一个 1 亿个二进制大小的位图
通过哈希函数（如f(x)=x%n，n表示位图大小，即对数字跟位图的大小进行取模求余），对数字进行处理，让它落在这 1 到 1 亿范围内

注意：哈希会存在冲突，如一亿零一和 1 两个数字最终都存储在1这个位置。为了降低这种冲突概率，可以设计一个复杂点、随机点的哈希函数。

布隆过滤器的处理方法是：一个哈希函数可能会存在冲突，用多个哈希函数一块儿定位一个数据，来降低冲突的概率。

使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，分别记作 X1，X2，X3，…，XK
把这 K 个数字作为位图中的下标，将对应的 BitMap[X1]，BitMap[X2]，BitMap[X3]，…，BitMap[XK]都设置成 true，用 K 个二进制位，来表示一个数字的存在
查询某个数字是否存在的时候，用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，YK
看这 K 个哈希值，对应位图中的数值是否都为 true
1. 如果都是 true，则说明这个数字存在
2. 如果其中任意一个不为 true，说明这个数字不存在

对于两个不同的数字来说，经过一个哈希函数处理，可能会产生相同的哈希值。但是经过 K 个哈希函数处理之后，K 个哈希值都相同的概率就非常低了。

尽管采用 K 个哈希函数之后，两个数字哈希冲突的概率降低了，但是，这种处理方式又带来了新的问题，那就是容易误判。

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

布隆过滤器只会对存在有误判：

如果某个数字经过布隆过滤器判断不存在，那这个数字真的不存在，不会误判
如果某个数字经过布隆过滤器判断存在，这时有可能误判，可能数字并不存在

只要调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，就可以将这种误判的概率降到非常低。

布隆过滤器的误判率，主要跟哈希函数的个数、位图的大小有关。

往布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来越高。所以，对于无法事先知道要判重的数据个数的情况，需要支持自动扩容的功能
当布隆过滤器中，数据个数与位图大小的比例超过某个阈值，就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中
如果要判断某个数据是否在布隆过滤器中已经存在，就需要查看多个位图，相应的执行效率就降低了一些

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

应用

尽管布隆过滤器会存在误判，但是，这并不影响它发挥大作用。很多场景对误判有一定的容忍度。

比如要解决的爬虫判重这个问题，即便一个没有被爬取过的网页，被误判为已经被爬取，对于搜索引擎来说，也并不是什么大事情，是可以容忍的，毕竟网页太多了，搜索引擎也不可能 100% 都爬取到。

布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。

比如，统计一个大型网站的每天的 UV（Unique Visitor，独立访客）数，就可以使用布隆过滤器，对重复访问的用户进行去重。

存储优化

使用布隆过滤器解决爬虫去重问题：

用布隆过滤器来记录已经爬取过的网页链接
假设需要判重的网页有 10 亿，那可以用一个 10 倍大小的位图（100 亿个二进制位，约 1.2GB）来存储
用散列表判重，需要至少 100GB 的空间
相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多

执行优化

布隆过滤器用多个哈希函数对同一个网页链接进行处理
CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的
在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的
CPU 计算要比内存访问更快速，所以，理论上布隆过滤器的判重方式，更加快速

工业实现

Java 中的 BitSet 类是一个位图
Redis 提供了 BitMap 位图类
Google 的 Guava 工具包提供了 BloomFilter 布隆过滤器的实现

常见二进制操作

位操作符

// & 与运算
// 两个位都是 1 时，结果才为 1，否则为 0，如
1 0 0 1 1 &
1 1 0 0 1
-----------
1 0 0 0 1

// | 或运算
// 两个位都是 0 时，结果才为 0，否则为 1，如  
1 0 0 1 1 |
1 1 0 0 1

1 1 0 1 1

// ^ 异或运算
// 两个位相同则为 0，不同则为 1，如  
1 0 0 1 1 ^  
1 1 0 0 1
-----------
0 1 0 1 0

// ~ 取反运算(在go取反使用^)
// 0 则变为 1，1 则变为 0，如
~ 1 0 0 1 1
-----------
  0 1 1 0 0 

// &^ 位清空运算
// 根据后者为1的位置，将前者对应位置变为0，如
0 1 1 1 1 1 &^
0 0 0 1 0 1
-----------
0 1 1 0 1 0

// << 左移运算 (乘以2^n)
// 向左进行移位操作，高位丢弃，低位补 0，如
a := 8
a << 3
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0100 0000

// >> 右移运算 (除以2^n)
// 向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如
a := 8
a >> 3
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001

a := -8
a >> 3
移位前：1111 1111 1111 1111 1111 1111 1111 1000
移位前：1111 1111 1111 1111 1111 1111 1111 1111

基础操作

// 两个相同的数异或后得到0，任何数与0异或得到它自身
a = a^0 = 0^a
0 = a^a

// 交换两个数，异或符合交换律
tmp := a^b
a ^= tmp   // 相当于 a = a^b^b
b ^= tmp   // 相当于 b = a^b^a

// 移除最低位的1
a = n&(n-1)

// 获取最后一位
a = n&1

// 获取最低位的1
a = n&(n-1)^n
a = n&(~n+1)
a = n&-n

// 判断奇偶性
// 只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数
if (a & 1)==0 {
    //偶数
}

// 交换符号
// 交换符号将正数变成负数，负数变成正数
func reversal(a int) {
    return ~a + 1
}

// 统计二进制中1的个数
count := 0  
for a != 0 {
    if a&1 == 1 {
        count++
    }
    a = a >> 1
}
// 或者
for a!=0{
    a=a&(a-1)
    count++
}

复杂操作

// 将x最右边的n位清零
x&(~0<<n)

// 获取x的第n位值（0或者1）
(x>>n)&1

// 获取x的第n位的幂值
x&(1<<(n-1))

// 仅将第n位置为1
x|(1<<n)

// 仅将第n位置为0
x&(~(1<<n))
x&^(1<<n)

// 将x最高位至第n位（含）清零
// [有问题]
x&(~(1<<n))

// 将第n位至第0位（含）清零
x&(~((1<<(n+1))-1))

常考考点

只出现一次的数

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：算法应该具有线性时间复杂度，且不使用额外空间来实现。

思路

使用异或运算：

两个相同的数异或后为0
一个数与0异或是它自身

示例代码

func singleNumber(nums []int) int {
    res := 0
    for _,num := range nums {
        res ^= num
    }
    return res
}

只出现一次的数【变形1】

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：算法应该具有线性时间复杂度，且不使用额外空间来实现。

思路

因为重复的元素出现了三次，不重复的元素只要一个出现一次。

统计整个数组中，每一位中1出现的次数
每一位都对3取余数，这个余数就是唯一的那个元素在该位上是否为1（只可能是0或1）
知道了每一位是1还是0后，还原所在的位值，组合在一起就是这个结果

注意：判断数组中数据的位数时，int类型在32和64位操作系统中长度不同，现在一般都是64位操作系统了。

示例代码

func singleNumber(nums []int) int {
    // 外层循环控制本次查看的是哪一位
    // 从最右边第0位开始
    res, n := 0, len(nums)
    for i := 0; i < 64; i++ {
        sum := 0
        // 内层循环控制数组中的第几个数
        for j := 0; j < n; j++ {
            // 通过右移将将该位放到最后
            // 通过与运算取出这一位
            sum += (nums[j] >> i) & 1
        }
        // 对3取余数得到唯一的那个数的这一位的值
        // 通过左移运算恢复这个值应该在的位置
        res += sum % 3 << i
    }
    return res
}

只出现一次的数【变形2】

给定一个整数数组，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

说明：算法应该具有线性时间复杂度，且不使用额外空间来实现。

思路

两个相同的数异或后为0，一个数与0异或还是它自身。因为重复的元素都出现两次，异或后就变成了0。

将所有元素依次异或，等到的结果是a^b
将a^b拆分为a和b，就是结果
因为异或的结果是，两个为都相同就是0，两个为不同就是1，a^b这个结果中的1表示是a和b不同的位置。
找到a和b中第一个不同的位置之后，将这个值与每一个元素进行与运算（将元素区分为该位与a相同和该位与b相同），这两组中分别包含了重复的元素以及a或b
因为相同的元素和自身异或后为0，将a^b的结果与这两组元素分别异或，就能得到a和b分别是多少

因为在异或的过程中重复的元素已经被0化了，就变成diff := a^b,a ^= diff,b ^= diff，只不过这里的a和b值相互交换了一下。

小结一下用到的位运算：

异或（该位相同为0，该位不同为1）
相同元素异或为0
获取元素最后一个1的位置
取出元素中某一位的值
通过异或交换两个数

示例代码

func singleNumber(nums []int) []int {
    diff, n := 0, len(nums)
    for i := 0; i < n; i++ {
        // diff=a^b
        diff ^= nums[i]
    }
    res := []int{diff, diff}

    // 获取diff中最后一个1的位置
    diff = (diff & (diff - 1)) ^ diff
    for i := 0; i < n; i++ {
      // 相当于取出diff最后一个1对应的那一位的值
        if diff&nums[i] == 0 {
            res[0] ^= nums[i]
        } else {
            res[1] ^= nums[i]
        }
    }
    return res
}

求位为1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

思路

两种方法：

通过右移运算不断取出每一位，累计1的个数
通过n&(n-1)不断移除最后一个1，累计1的个数

示例代码

// 方法1
func hammingWeight(num uint32) int {
    res:=0
    for num!=0{
       if num&1==1{
         res++
       }
         num >>= 1
    }
    return res
}

// 方法2
func hammingWeight(num uint32) int {
    res:=0
    for num!=0{
        num=num&(num-1)
        res++
    }
    return res
}

比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

思路

也就是计算从0到num之间，这些数的累计1的个数。

两种方法：

上一题已经求出一个数中累计1的个数，用数组将结果保存起来（注意，当前结果是前面结果的和）
动态规划：当前这个数中1的个数比上一个缺1的元素多1

示例代码

// 方法1
func countBits(num int) []int {
    res := make([]int, num+1)
    for i := 1; i <= num; i++ {
        res[i] = hammingWeight(i)
    }
    return res
}

func hammingWeight(num int) int {
    res:=0
    for num!=0{
        num=num&(num-1)
        res++
    }
    return res
}

// 方法2
func countBits(num int) []int {
   dp := make([]int, num+1)
   // 不用初始化 base case，因为dp[0]==0
    for i := 1; i <= num; i++ {
        dp[i] = dp[i&(i-1)] + 1
    }
    return dp
}

颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

思路

把最右边的一位取出，左移对应的位数，加到结果中。

示例代码

func reverseBits(num uint32) uint32 {
    var (
        res uint32
        pow int = 31
    )
    for num != 0 {
        // 把最后一位取出来，左移之后累加到结果中
        res += (num & 1) << pow
        num >>= 1
        pow--
    }
    return res
}

数字范围按位与

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

思路

因为是按位与，从m到n的这些数字中，只要有一个数的某一位是0，那么这一位就是0，最终结果就是这一段范围内全是1的那一位，对应的数字。

示例代码

func rangeBitwiseAnd(m int, n int) int {
    count := int
    for m != n {
        m >>= 1
        n >>= 1
        count++
    }
    return m << count
}

最后更新于4年前

这有帮助吗？