地址监控

一个HD钱包管理的是一组自动计算的地址。以比特币为例，在确定了根扩展私钥m后，得到一组地址为m/44'/0'/0'/0/x，其中x=0~231。

HD钱包需要在链上监控每个TX的输入和输出，看看上述管理的一组地址是否存在与输入和输出中。如果作为输入，则钱包余额减少，如果作为输出，则钱包余额增加。

现在问题来了：如何根据TX的输入和输出地址快速判断这些地址中是否存在HD钱包管理的地址？

首先，可用的地址高达231个，这个数太大了，用户不可能用完，因此，HD钱包只会预生成前1000个地址（即索引号为0～999）并保存在本地数据库中，如果不够了，再继续扩展1000个，这样，HD钱包管理的地址数量不会太大。

其次，要在上千个地址集合中快速判断某个地址是否存在，查询数据库是一个非常低效的方式。以哈希表存储在内存中虽然效率很高，但管理的集合数量太多，占用的内存会非常大。

要做到高效的查询和低空间占用率，可以使用布隆过滤器（Bloom Filter），它是由Burton Howard Bloom在1970年提出的，其原理是将每个元素通过若干个哈希函数映射成一个位数组的若干个点，将其置1。检索的时候，先计算给定元素对应位是否全1，如果是全1，则给定元素很可能存在，否则，元素必定不存在。

因此，Bloom Filter有个重要特点，就是判断元素时，如果不存在，那么肯定不存在，如果存在，实际上是以一定概率存在（例如，99%），还需要再次从数据库查询以确定元素真的存在。

Bloom Filter的缺点就是它无法100%准确判断存在，此外，添加新的元素到Bloom Filter很容易，但删除元素就非常困难。构造Bloom Filter时，要先预估元素个数并给定存在概率，才能计算所需的内存空间。

Bloom Filter广泛用于垃圾邮件地址判断，CDN服务等。Bloom Filter也非常适合HD钱包监控链上每个交易的地址。