• 产生背景
  • 解决海量数据去重
    实现这样一个功能：统计 APP或网页 的一个页面，每天有多少用户点击进入的次数。同一个用户的反复点击进入记为 1 次
    解决
    1、HashMap，但数据达到一定量级时，HashMap会占用大量内存
    2、Bitmap
    3、B+树
    4、HyperLogLog（在一定条件允许下，如果允许统计在巨量数据面前的误差率在可接受的范围内）
  • 伯努利试验
    数学概率论中的一部分内容，它的典故来源于抛硬币。
• 概述
  简称为HLL，它是 LogLog 算法的升级版，作用是能够提供不精确的去重计数
  • 特点
    • 代码实现较难
    • 能够使用极少的内存来统计巨量的数据
      Redis 中实现的 HyperLogLog，只需要12K内存就能统计2^64个数据。——比Bitmap存的还多
    • 计数存在一定的误差，误差率整体较低。标准误差为 0.81% 。
    • 误差可以被设置辅助计算因子进行降低