问题描述：10亿个key中，怎么判断某个key是否存在？key的类型是不超过30个字符的字符串。
要求：
1. 内存空间不能占用太大
2. QPS在500w
看到这个问题，肯定有很多人第一反应想到Map，因为Map天然支持key-value的数据结构，并且能够快速的查找某个key。但是，如果你选择使用Hashmap，那肯定会占用很大的内存，这不符合要求。那肯定有人说使用布隆过滤器，也就是使用BloomFilter。那我们一起来看一下，使用布隆过滤器会有不会有什么问题？
一、布隆过滤器
布隆过滤器是一种概率型数据结构，可以用来检验一个元素是否属于一个集合。
它通过构建多个哈希函数，将每个关键字映射到多个位数组的位置上，若所有相应的位都为1，则说明该元素可能被包含在该集合中，如果有一个或多个对应的位为0，则肯定不在集合中。因此，布隆过滤器具有空间效率高和查询时间快等特点。
在Redis中，可以使用BitMap类型来实现布隆过滤器；而在Java语言中，可以使用Guava中的BloomFilter来实现。
示例代码：
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterDemo {
public static void main(String[] args) {
// 创建布隆过滤器，预计插入1000000000个元素
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(
Funnels.stringFunnel(), 1000000000L, 0.01);
// 插入10000个元素
for (int i = 1; i <= 10000; i++) {
bloomFilter.put("key_" + i);
}
// 判断key_9999是否存在
if (bloomFilter.mightContain("key_9999")) {
System.out.println("key_9999 存在");
} else {
System.out.println("key_9999 不存在");
}
// 判断key_10000是否存在
if (bloomFilter.mightContain("key_10000")) {
System.out.println("key_10000 存在");
} else {
System.out.println("key_10000 不存在");
}
}
}
输出：
key_9999 存在
key_10000 不存在
这段代码只演示了小数据量的存在和不存在判断，**但是布隆过滤器是存在误判率的。它的误判率会在构造函数进行设置，上面代码构造函数中的0.01就是允许的误判率。**
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(
Funnels.stringFunnel(), 1000000000L, 0.01);
误判率受到两个因素的影响：位数组长度和哈希函数个数。
位数组越长，误判率越低；哈希函数个数越多，误判率也越低。
为什么会出现误判？
由于哈希函数的数量和位数组的大小都是有限的，当布隆过滤器中的元素数量增加时，就会出现哈希冲突。
具体来说，当两个不同的元素被哈希函数映射到位数组中的同一个位置时，就会发生哈希冲突。这种情况可能会导致误判率的增加，因为一个元素被误认为在集合中时，实际上它可能是被另一个元素所占据的位置所误判。
怎么减少hash冲突？能不能避免？
为了减小哈希冲突的概率，布隆过滤器会使用多个不同的哈希函数，并通过哈希函数的参数设置和位数组的大小来优化其性能。同时，在实际使用过程中，也可以对布隆过滤器进行动态调整，以使误判率保持在可接受的范围内。**所以说误判率只能降低，但不能完全避免。**
如果你的业务允许并接收误判，那可以使用布隆过滤器。但是如果要做到精确的判断，那布隆过滤器并不是最优的选择。下面我来介绍一下我觉得可以精确判断的方案。
二、字典树（精确）
2.1 字典树的定义
字典树（Trie树） 是一种树形数据结构，用于存储字符串集合并支持高效的查询、插入和删除操作。字典树的核心思想是利用字符串的公共前缀来压缩空间并减少查询时间的开销，最大限度地减少无谓的字符串比较。它可以被认为是一种哈希树的变种或扩展，通常用于实现词频统计、字符串匹配等任务。
在字典树中，每个节点代表一个字符串（即从根节点到该节点路径上的所有字符组成的字符串），根节点代表空字符串。每个节点都有若干子节点，每个子节点对应一个字符，从而形成了一棵树。从根节点到叶子节点的路径组成的字符串即为对应的单词。为了方便存储和查询，字典树通常采用数组或哈希表等数据结构来存储子节点。
2.2 问题解决过程
将key按照字符一个个地插入到字典树中，如果在插入过程中发现某个节点没有子节点，则表示该节点对应的字符串就是一个存在的key。因此，在判断一个key是否在这个集合中时，只需把要查找的key按照同样的方式从根节点开始插入，如果能在树中找到一条路径，使得路径上每个节点都有一个与key对应的字符，则说明该key存在于集合中；否则说明该key不存在。
代码实现：
public class Trie {
private TrieNode root;
private class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
// 字典树的每个节点都包含了26个子节点，分别对应着26个小写字母
children = new TrieNode[26];
}
}
public Trie() {
// 初始化字典树根节点为空节点
root = new TrieNode();
}
public void insert(String key) {
TrieNode node = root;
for (char c : key.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
// 最后一个节点的isEndOfWord属性设置为True，标识该节点是某个key的结尾
node.isEndOfWord = true;
}
public boolean search(String key) {
TrieNode node = root;
for (char c : key.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
return false;
}
node = node.children[idx];
}
return node != null && node.isEndOfWord;
}
// 以下是使用示例
public static void main(String[] args) {
String[] keys = {"apple", "banana", "cat", "dog", "elephant", "fish", "goose", "horse"}; // 构造8个key
Trie trie = new Trie();
// 将每个key插入字典树中
for (String key : keys) {
trie.insert(key);
}
// 检查字典树中是否存在某个key
System.out.println(trie.search("dog")); // 输出true
System.out.println(trie.search("car")); // 输出false
}
}
字典树的查询效率很高，时间复杂度为O(L)，其中L表示key的长度。与布隆过滤器不同的是，字典树能够保证任何时候的查询结果都是正确的，但需要消耗更多的空间去存储整个字典树。
如果你有更好的方案，也可以在评论区补充~
