乐趣区

关于java:字节面试10亿个key中怎么判断某个key是否存在

jiezi

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

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

退出移动版