问题形容：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的长度。与布隆过滤器不同的是，字典树可能保障任何时候的查问后果都是正确的，但须要耗费更多的空间去存储整个字典树。

如果你有更好的计划，也能够在评论区补充~