位图

应用场景

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

解决方案

1. 记录已经爬取过的URL，爬取新网页前查看是否爬取过

2. 已爬取过则忽略

3. 未爬取过则先爬取后记录

注意点：

1. 查询和添加操作要高效

2. 上亿的网页，消耗内存非常高，存储效率要高

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

• 散列表

• 红黑树

• 跳表

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

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

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

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

性能优化

执行效率

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

• 一方面，链表中的结点在内存中不是连续存储的，不能一下子加载到 CPU 缓存中，没法很好地利用到 CPU 高速缓存，所以数据访问性能方面会打折扣。

• 另一方面，链表中的每个数据都是 URL，而 URL 不是简单的数字，是平均长度为 64 字节的字符串，要让待判重的 URL，跟链表中的每个 URL，做字符串匹配。这样一个字符串匹配操作，比起单纯的数字比对，要慢很多。

内存消耗

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

问题

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

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

解决方案

使用位图来解决。

1. 申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组

2. 将这 1 千万个整数作为数组下标，将对应的数组值设置成 true，如整数 5 对应下标为 5 的数组值设置为 true（array[5]=true）

3. 查询某个整数 K 是否存在，只要将对应的数组值 array[K] 取出来判断是否为true

4. 如果等于 true，说明存在整数 K

5. 如果不等于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. 创建一个 1 亿个二进制大小的位图

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

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

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

1. 使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，分别记作 X1​，X2​，X3​，…，XK​

2. 把这 K 个数字作为位图中的下标，将对应的 BitMap[X1​]，BitMap[X2​]，BitMap[X3​]，…，BitMap[XK​]都设置成 true，用 K 个二进制位，来表示一个数字的存在

3. 查询某个数字是否存在的时候，用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1​，Y2​，Y3​，…，YK​

4. 看这 K 个哈希值，对应位图中的数值是否都为 true

   1. 如果都是 true，则说明这个数字存在

   2. 如果其中任意一个不为 true，说明这个数字不存在

布隆过滤器

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

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

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

布隆过滤器

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

1. 如果某个数字经过布隆过滤器判断不存在，那这个数字真的不存在，不会误判

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

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

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

1. 往布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来越高。所以，对于无法事先知道要判重的数据个数的情况，需要支持自动扩容的功能

2. 当布隆过滤器中，数据个数与位图大小的比例超过某个阈值，就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中

3. 如果要判断某个数据是否在布隆过滤器中已经存在，就需要查看多个位图，相应的执行效率就降低了一些

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

应用

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

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

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

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

存储优化

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

1. 用布隆过滤器来记录已经爬取过的网页链接

2. 假设需要判重的网页有 10 亿，那可以用一个 10 倍大小的位图（100 亿个二进制位，约 1.2GB）来存储

3. 用散列表判重，需要至少 100GB 的空间

4. 相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多

执行优化

1. 布隆过滤器用多个哈希函数对同一个网页链接进行处理

2. CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的

3. 在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的

4. 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))

常考考点

只出现一次的数

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

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

思路

使用异或运算：

1. 两个相同的数异或后为0

2. 一个数与0异或是它自身

示例代码

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

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

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

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

思路

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

1. 统计整个数组中，每一位中1出现的次数

2. 每一位都对3取余数，这个余数就是唯一的那个元素在该位上是否为1（只可能是0或1）

3. 知道了每一位是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。

1. 将所有元素依次异或，等到的结果是a^b

2. 将a^b拆分为a和b，就是结果

   因为异或的结果是，两个为都相同就是0，两个为不同就是1，a^b这个结果中的1表示是a和b不同的位置。

3. 找到a和b中第一个不同的位置之后，将这个值与每一个元素进行与运算（将元素区分为该位与a相同和该位与b相同），这两组中分别包含了重复的元素以及a或b

4. 因为相同的元素和自身异或后为0，将a^b的结果与这两组元素分别异或，就能得到a和b分别是多少

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

小结一下用到的位运算：

1. 异或（该位相同为0，该位不同为1）

2. 相同元素异或为0

3. 获取元素最后一个1的位置

4. 取出元素中某一位的值

5. 通过异或交换两个数

示例代码

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. 通过右移运算不断取出每一位，累计1的个数

2. 通过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的个数，用数组将结果保存起来（注意，当前结果是前面结果的和）

2. 动态规划：当前这个数中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
}