常见算法扩展链接

1. 布隆过滤器
   三、布隆过滤器实战
   布隆过滤器有很多实现和优化，由 Google 开发著名的 Guava 库就提供了布隆过滤器（Bloom Filter）的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器，只需要引入以下坐标：

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>28.0-jre</version>
</dependency>

在导入 Guava 库后，我们新建一个 BloomFilterDemo 类，在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器，接着我们初始化 1 百万条数据到过滤器中，然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中：

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterDemo {
    public static void main(String[] args) {
        int total = 1000000; // 总数量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }
}

当以上代码运行后，控制台会输出以下结果：

已匹配数量 1000309
很明显以上的输出结果已经出现了误报，因为相比预期的结果多了 309 个元素，误判率为：

309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

如果要提高匹配精度的话，我们可以在创建布隆过滤器的时候设置误判率 fpp：

BloomFilter<CharSequence> bf = BloomFilter.create(
  Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);
在 BloomFilter 内部，误判率 fpp 的默认值是 0.03：

// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
  return create(funnel, expectedInsertions, 0.03D);
}
在重新设置误判率为 0.0002 之后，我们重新运行程序，这时控制台会输出以下结果：

已匹配数量 1000003
通过观察以上的结果，可知误判率 fpp 的值越小，匹配的精度越高。当减少误判率 fpp 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

参考链接：

https://zhuanlan.zhihu.com/p/94433082

2. 字符串匹配（KMP算法）

https://blog.csdn.net/dark_cy/article/details/88698736

3. 贪心算法

https://blog.csdn.net/effective_coder/article/details/8736718
https://www.cnblogs.com/xsyfl/p/6938642.html