海量数据去重

HashSet

• HashSet不重复
• 可以用O(1)判断数据是否存在
• 海量数据的话可以拆分到HashMap每个桶或者多台机器上

BitSet

• 如果海量数据是整数
• 范围不大
• 构造bit数组，数据都映射到上面
• 如两个比特数组可以存0~3->00 01 10 11

字典树

• 如果海量数据是字符串数据
• 可以用很小空间开销构建字典树
• 原理就是每个结点存放一个字符，子树则是下一个字符，当前value为1的话表示root到该节点的字符串存在了
  

布隆过滤器

• 原理就是经过多个hash函数散列到bitset中，设为1
• 查找的时候也是通过多个hash函数看散列到的位置是否都为1，都为1的话则判定存在
• 由于是hash，容易出现误判
• 如果hash函数个数设置过大，容易带来更高的时间和空间开销