当前位置: 首页 > news >正文

【2025最新redis数据结构之Hypeloglog介绍】关于Hypeloglog

HyperLogLog (HLL) 算法深度解析

一、HLL 基本概念

HyperLogLog 是一种用于基数统计(distinct counting)的概率算法,能够在极小内存占用下(通常只需几KB)估算巨大数据集的基数(不重复元素数量),标准误差约为 0.81%。

核心特点

  • 极低内存消耗:统计 10^9 个不重复元素仅需约 1.5KB 内存

  • 固定大小结构:内存占用与基数大小无关

  • 可合并性:多个 HLL 结构可以合并计算总基数

二、算法实现原理

1. 基本思想

HLL 基于以下观察:在一个随机均匀分布的比特流中,连续出现 "0" 的最大数量 k 与数据集中不重复元素的数量 N 存在关系:N ≈ 2^k

2. 核心组件

  1. 哈希函数

    • 将输入元素映射为足够长的比特串(通常 64 位)

    • 要求:均匀分布、确定性

  2. 分桶(Register)

    • 使用前 m 个比特确定桶索引(m 通常取 12-16)

    • 剩余比特用于计算连续前导零的数量

  3. 调和平均数

    • 用于合并各桶的估算值,减少误差

3. 算法步骤

  1. 初始化

    m = 2^b # b 通常取 4-16 registers = [0] * m

  2. 添加元素

    def add(element):hash = sha1(element).hexdigest()  # 生成哈希值index = int(hash[:b], 16) % m    # 前b位作为桶索引value = hash[b:]                 # 剩余部分计算前导零leading_zeros = count_leading_zeros(value) + 1registers[index] = max(registers[index], leading_zeros)
  3. 估算基数

    def estimate():harmonic_mean = sum(2 ** -r for r in registers) ** -1return alpha * m * m * harmonic_mean  # alpha 为修正因子

三、Redis 中的实现(为什么redis中只占用了12kb的大小)

Redis 实现的 HyperLogLog 使用 16384 (2^14) 个桶,每个桶占 6 bits,总内存占用:

12 KB = 16384 * 6 / 8 / 1024

内存布局

+---------+---------+-----+---------+
| 11000000 | 00011100 | ... | 00101100 |  # 每个桶6位
+---------+---------+-----+---------+

关键命令

PFADD key element [element ...]  # 添加元素
PFCOUNT key [key ...]           # 获取基数估算
PFMERGE destkey sourcekey [sourcekey ...] # 合并多个HLL

四、数学原理深度解析

1. 概率基础

对于均匀分布的哈希值,连续出现 k 个前导零的概率:

P = 1 / 2^(k+1)

2. 估算公式

原始 LogLog 估算:

E = α * m * 2^(1/m * Σρ)

改进的 HyperLogLog 估算:

E = α * m * m / (Σ2^(-ρ))

其中:

  • m = 桶数量

  • ρ = 各桶的最大前导零数

  • α = 修正因子(m=16:0.673, m=32:0.697, m=64:0.709, m≥128:0.7213/(1+1.079/m))

3. 误差修正

对小范围基数进行线性修正:

  • 当 E < 2.5m:使用线性计数

  • 当检测到空桶:调整估算公式

五、性能优化技术

  1. 稀疏表示

    • 对小基数使用显式存储

    • 当基数较小时直接存储元素而非寄存器值

  2. 偏差校正

    • 对小范围基数使用预先计算的校正表

    • 消除系统偏差

  3. 寄存器压缩

    • 使用变长编码压缩寄存器数组

    • 在合并时解压缩处理

六、应用场景

  1. 网站UV统计

    # 统计日UV
    PFADD daily:uv:20230501 user1 user2 user3
    PFCOUNT daily:uv:20230501
  2. 跨日统计

    PFMERGE weekly:uv daily:uv:20230501 daily:uv:20230502 ... daily:uv:20230507
  3. A/B测试

    # 统计不同方案的独立用户数
    PFADD variant:A user1 user3 user5
    PFADD variant:B user2 user3 user6

七、与其他基数统计方案对比

算法内存占用误差率是否精确合并能力
HashSetO(N)0%
Linear CountingO(N)可变
LogLogO(log(logN))1.3/√m
HyperLogLogO(log(logN))0.81/√m
HyperLogLog++O(log(logN))0.81/√m

八、实现注意事项

  1. 哈希函数选择

    • 需要良好的分布特性

    • Redis 使用 64 位 MurmurHash2

  2. 寄存器位数

    • 通常 5-6 位足够(最大前导零 32-64)

    • 更多位数对精度提升有限

  3. 边界情况处理

    • 空数据集返回 0

    • 小数据集使用精确计数

HyperLogLog 通过巧妙的概率统计方法和分桶技术,在极小内存占用下实现了大规模数据集的基数估算,是大数据时代不可或缺的基数统计工具。Redis 的实现进一步优化了内存使用和计算效率,使其成为实际应用中的首选方案。

相关文章:

【2025最新redis数据结构之Hypeloglog介绍】关于Hypeloglog

HyperLogLog (HLL) 算法深度解析 一、HLL 基本概念 HyperLogLog 是一种用于基数统计&#xff08;distinct counting&#xff09;的概率算法&#xff0c;能够在极小内存占用下&#xff08;通常只需几KB&#xff09;估算巨大数据集的基数&#xff08;不重复元素数量&#xff09…...

软考复习——知识点软件开发

开发模型 瀑布模型 各个活动规定为线性顺序连接的若干阶段的模型。是一种理想的现象开发模型&#xff0c;缺乏灵活性&#xff0c;无法理解软件需求不明确或不准确的问题。适用于需求明确的项目。 演化模型 从初始的原型逐步演化成最终软件产品&#xff0c;特别适用于对软件…...

关于AI:记忆、身份和锁死

作者&#xff1a;John Battelle 当生成式AI迎来投资热潮、产品发布和炒作高峰时&#xff0c;我们大多数人在奔向“下一个大事件”的过程中&#xff0c;忽略了一个深层次的缺陷。我们现在主流的AI产品和服务&#xff08;比如OpenAI、Google和Microsoft的产品&#xff09;都是通过…...

2024新版仿蓝奏云网盘源码,已修复已知BUG,样式风格美化,可正常运营生产

说起网盘源码&#xff0c;网络上出现的也很多&#xff0c;不过可真正正能够用于运营的少之又少。今天将的蓝奏云网盘源码&#xff0c;其实网络上也有&#xff0c;不过是残缺版&#xff0c;bug很多。我今天分享的仿蓝奏云模板是经过长时间测试修复后的源码&#xff0c;源码实测可…...

OJ - 设计循环队列

622. 设计循环队列 - 力扣&#xff08;LeetCode&#xff09; 循环队列是一种线性数据结构&#xff0c;其操作表现基于 FIFO&#xff08;先进先出&#xff09;原则&#xff0c;并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可…...

实战指南:封装Faster-Whisper为FastAPI接口并实现高并发处理-附整合包

实战指南&#xff1a;封装Faster-Whisper为FastAPI接口并实现高并发处理-附整合包 「faster-whisper」 链接&#xff1a;https://pan.quark.cn/s/d4ddffb1b196 标题下面提供一个完整的示例&#xff0c;说明如何使用 FastAPI 封装 faster-whisper 接口&#xff0c;对外提供 RES…...

011数论——算法备赛

素数筛 给定n, 求2~n内的所有素数 埃氏筛 利用素数的定义&#xff0c; 输出素数2&#xff0c;然后筛掉2的倍数&#xff0c;得 {2,3,5,7,9,11,13&#xff0c;…}输出素数3&#xff0c;然后筛掉3的倍数&#xff0c;得 {2,3,5,7,11,13&#xff0c;…} 继续上述步骤&#xff0…...

C语言之机房机位预约系统

&#x1f31f; 嗨&#xff0c;我是LucianaiB&#xff01; &#x1f30d; 总有人间一两风&#xff0c;填我十万八千梦。 &#x1f680; 路漫漫其修远兮&#xff0c;吾将上下而求索。 C语言之机房机位预约系统 目录 博客&#xff1a;机房机位预约系统设计与实现 系统功能概述…...

中间件--ClickHouse-14--案例-3-其他案例思路概述

1、广告投放效果分析 案例背景&#xff1a; 一家广告平台需要分析广告的点击、曝光、转化等数据&#xff0c;以优化广告投放策略并提升 ROI&#xff08;投资回报率&#xff09;。 解决方案&#xff1a; 数据接入&#xff1a;将广告投放相关的数据&#xff08;如曝光、点击、…...

saas是什么?它做什么用的。及和Paas和laas有什么区别

Saas是什么&#xff1f;它做什么用的。及和Paas和laas有什么区别 提示&#xff1a;帮帮志会陆续更新非常多的IT技术知识&#xff0c;希望分享的内容对您有用。本章分享的是行业内容。前后每一小节的内容是存在的有&#xff1a;学习and理解的关联性&#xff0c;希望对您有用~ 文…...

Qt基础005(文件操作后续)

文章目录 QFileDialogQFileDialog打开开发案例QFileDialog保存开发案例实现文件打开功能开发流程打开功能优化 QComboBoxQListExtraSelection 简介 QFileDialog QFileDialog打开开发案例 #include <QApplication> #include <QFileDialog> #include <QStringLi…...

松灵Cobot Magic双臂具身遥操机器人(基于ROS的定位建图与协同导航技术)

摘要 本文以CobotMagic可移动协作机器人为研究对象&#xff0c;从硬件架构设计、软件系统架构、多传感器融合定位建图系统、智能导航系统协同机制四个维度&#xff0c;深入解析机器人系统工作原理。重点研究多传感器融合定位建图系统实现原理&#xff0c;结合实测数据验证系统…...

AI——神经网络以及TensorFlow使用

文章目录 一、TensorFlow安装二、张量、变量及其操作1、张量Tensor2、变量 三、tf.keras介绍1、使用tf.keras构建我们的模型2、激活函数1、sigmoid/logistics函数2、tanh函数3、RELU函数4、LeakReLu5、SoftMax6、如何选择激活函数 3、参数初始化1、bias偏置初始化2、weight权重…...

实现对象之间的序列化和反序列化

1.什么是序列化&#xff1f; 在项目的开发中&#xff0c;为了让前端更好的分析后端返回的结果&#xff0c;我们一般会将返回的信息进行序列化&#xff0c;序列化就是将返回对象的状态信息转换为一种标准化的格式&#xff0c;方便在网络中传输也方便打印日志时号观察&#xff0…...

QML中日期处理类

在 QML 中处理日期和时间主要使用 JavaScript 的 Date 对象以及 Qt 提供的一些相关功能。以下是常用的日期处理方式&#xff1a; 1. JavaScript Date 对象 QML 可以直接使用 JavaScript 的 Date 对象&#xff1a; qml // 创建当前日期时间 var currentDate new Date()// 创…...

基于docker-java封装的工具类

基于docker-java封装的工具类 背景环境工具类 背景 写OJ系统时需要用docker作为代码沙箱使用&#xff0c;顺手封装了一个工具类&#xff0c;给自己做个笔记&#xff0c;如果可以的话也希望帮助到其他人。 环境 docker 26.1.4docker-java 3.4.2docker-java-transport-httpcli…...

windows docker desktop 无法访问容器端口映射

为什么使用docker desktop访问映射的端口失败&#xff0c;而其端口对应的服务是正常的&#xff1f; 常见问题&#xff0c;容器的防火墙没有关闭&#xff01;&#xff01;&#xff01; 以centos7为例&#xff0c;默认情况下防火墙处于开启状态&#xff1a; 这下访问就OK了...

ReentrantReadWriteLock读写锁

一、锁的分类 这里不会对Java中大部分的分类都聊清楚&#xff0c;主要把 **互斥&#xff0c;共享** 这种分类聊清楚。 Java中的互斥锁&#xff0c;synchronized&#xff0c;ReentrantLock这种都是互斥锁。一个线程持有锁操作时&#xff0c;其他线程都需要等待前面的线程释放锁…...

Vue.js 入门教程

Vue.js 入门教程 Vue.js 是一款非常流行的前端 JavaScript 框架&#xff0c;适用于构建用户界面。它的设计思想是尽可能简单、灵活&#xff0c;易于与其他库或现有项目整合。本文将从最基础的概念开始&#xff0c;逐步引导你学习 Vue.js。 一、Vue.js 基础概念 1.1 什么是 V…...

解决Docker 配置 daemon.json文件后无法生效

vim /etc/docker/daemon.json 在daemon中配置一下dns {"registry-mirrors": ["https://docker.m.daocloud.io","https://hub-mirror.c.163.com","https://dockerproxy.com","https://docker.mirrors.ustc.edu.cn","ht…...

wpf stylet框架 关于View与viewmodel自动关联绑定的问题

1.1 命名规则 Aview 对应 AVIewModel, 文件夹 views 和 viewmodels 1.2 需要注册服务 //RootViewModel是主窗口 public class Bootstrapper : Bootstrapper<RootViewModel>{/// <summary>/// 配置IoC容器。为数据共享创建服务/// </summary…...

车载测试用例开发-如何平衡用例覆盖度和测试效率的方法论

1 摘要 在进行车载测试用例编写时&#xff0c;会遇到多个条件导致用例排列组合爆炸的情况&#xff0c;但是为了产品测试质量&#xff0c;我们又不得不保证用例设计的需求覆盖度&#xff0c;这样又会使得测试周期非常长。我们如何平衡效率和测试质量&#xff1f;本文进行了一些…...

leetcode(01)森林中的兔子

今天开始记录刷题的过程&#xff0c;每天记录自己刷题的题目和自己的解法&#xff0c;欢迎朋友们给出更多更好的解法。 森林中的兔子 森林中有未知数量的兔子&#xff0c;提问其中若干只兔子“还有多少只兔子与你&#xff08;被提问的兔子&#xff09;颜色相同”。将答案收集到…...

人工智能-机器学习其他技术(决策树,异常检测,主成分分析)

决策树 一种对实例进行分类的树形结构&#xff0c;通过多层判断区分目标所属类别 本质&#xff1a;通过多层判断&#xff0c;从训练数据集中归纳出一组分类规则 优点&#xff1a; 计算量校&#xff0c;运算速度快 易于理解 缺点&#xff1a; 忽略属性间的相关性 样本分布不均时…...

AIGC通信架构深度优化指南

AIGC通信架构深度优化指南 标题&#xff1a;《百亿参数大模型如何高效通信&#xff1f;揭秘AIGC系统的协议层设计艺术》 副标题&#xff1a;从分布式训练到多模态推理&#xff0c;构建高可靠AI通信系统 1. AIGC典型通信场景 1.1 分布式模型训练参数同步 sequenceDiagram训练…...

精益数据分析(7/126):打破创业幻想,拥抱数据驱动

精益数据分析&#xff08;7/126&#xff09;&#xff1a;打破创业幻想&#xff0c;拥抱数据驱动 在创业的道路上&#xff0c;我们都怀揣着梦想&#xff0c;但往往容易陷入自我编织的幻想中。我希望通过和大家一起学习《精益数据分析》&#xff0c;能帮助我们更清醒地认识创业过…...

Android Gradle多渠道打包

目录 1.多渠道打包是什么2.为什么需要多渠道打包3.多渠道配置VariantproductFlavorsbuildTypes 3.构建变体组合关于组合 4.渠道过滤5.渠道资源资源文件资源合并规则代码文件SourceSets 6. 渠道依赖项7.渠道统计meta-dataBuildConfig 8.管理渠道 1.多渠道打包是什么 多聚道打包…...

Day58 | 179. 最大数、316. 去除重复字母、334. 递增的三元子序列

179. 最大数 题目链接&#xff1a;179. 最大数 - 力扣&#xff08;LeetCode&#xff09; 题目难度&#xff1a;中等 代码&#xff1a; class Solution {public String largestNumber(int[] nums) {String[] strsnew String[nums.length];for(int i0;i<nums.length;i)str…...

LabVIEW发电机励磁系统远程诊断

变流器在风电系统中承担电能转换与控制的关键角色。它将发电机输出的低频、可变交流&#xff0c;通过整流、逆变等环节转为频率、电压稳定的交流&#xff0c;以满足电网接入要求&#xff1b;同时&#xff0c;根据实时风速调整发电机转速&#xff0c;实现最大功率追踪。 ​ 在某…...

性能比拼: Go vs Bun

本内容是对知名性能评测博主 Anton Putra Go (Golang) vs. Bun: Performance (Latency - Throughput - Saturation - Availability) 内容的翻译与整理, 有适当删减, 相关指标和结论以原作为准 我对 Bun 在之前的基准测试中的出色表现感到惊讶&#xff0c;因此我决定将它与 Go …...

Kubernetes相关的名词解释Dashboard界面(6)

什么是Kubernetes Dashboard&#xff1f; Kubernetes Dashboard 是一个基于 Web 的用户界面&#xff0c;用于管理 Kubernetes 集群。它是 Kubernetes 官方提供的可视化工具&#xff0c;允许用户通过直观的图形界面而不是命令行来部署、管理和监控集群中的应用程序。 Dashboard…...

Linux网络编程 TCP---并发服务器:多进程架构与端口复用技术实战指南

知识点1【并发服务器—多进程版】 并发服务器&#xff1a;服务器可以同时服务多个客户端 首先复习一下服务器的创建过程&#xff08;如下图&#xff09; 1、监听套接字&#xff08;套接字→绑定→监听&#xff08;连接队列&#xff09;&#xff09; 2、利用accept从连接队列…...

(done) 吴恩达版提示词工程 1. 引言

url: https://www.bilibili.com/video/BV1Z14y1Z7LJ/?spm_id_from333.337.search-card.all.click&vd_source7a1a0bc74158c6993c7355c5490fc600 LLM 有两种&#xff1a; 1.基础 LLM&#xff0c;通过文本训练数据预测后面的内容。 这种 LLM 当你给它提问&#xff1a;What is…...

uniapp微信小程序实现sse

微信小程序实现sse 注&#xff1a;因为微信小程序不支持sse请求&#xff0c;因为后台给的是分包的流&#xff0c;所以我们就使用接受流的方式&#xff0c;一直接受&#xff0c;然后把接受的数据拿取使用。这里还是使用uniapp的原生请求。 上代码 //注意&#xff1a;一定要下…...

【TeamFlow】3 Rust 与 WebAssembly (Wasm) 深度应用指南

WebAssembly 是一种低级的类汇编语言&#xff0c;能在现代浏览器中高效执行。Rust 因其无 GC、内存安全和卓越性能&#xff0c;成为编译到 Wasm 的理想语言。 一、为什么选择 Rust Wasm 性能优势&#xff1a;Rust 生成的 Wasm 代码执行效率接近原生 内存安全&#xff1a;避免…...

C 语言的未来:在变革中坚守与前行

C 语言&#xff0c;作为编程语言领域的一位 “老将”&#xff0c;自诞生以来就一直扮演着至关重要的角色。历经数十年的发展&#xff0c;它的影响力依然广泛而深远。在科技飞速发展的今天&#xff0c;新的编程语言如雨后春笋般不断涌现&#xff0c;C 语言的未来发展走向成为了众…...

SQL注入之information_schema表

1 information_schema表介绍&#xff1a; information_schema表是一个MySQL的系统数据库&#xff0c;他里面包含了所有数据库的表名 SQL注入中最常见利用的系统数据库&#xff0c;经常利用系统数据库配合union联合查询来获取数据库相关信息&#xff0c;因为系统数据库中所有信…...

android framework开发的技能要求

作为Android Framework开发工程师,需要具备深入的系统底层理解能力和对Android架构的全面认知。以下是核心技能要求,分为技术能力和软实力两大方向: 一、核心技术能力 Android系统架构深度掌握 Binder机制:理解Binder驱动、ServiceManager、AIDL跨进程通信原理,能分析Bind…...

AWS EC2完全指南:如何快速搭建高性能云服务器?

一、什么是AWS EC2&#xff1f;云时代的虚拟服务器革命 AWS Elastic Compute Cloud&#xff08;EC2&#xff09;作为全球领先的云服务器解决方案&#xff0c;正在重新定义虚拟服务器的可能性。与传统VPS相比&#xff0c;EC2提供&#xff1a; 秒级弹性扩展&#xff1a;CPU/RAM按…...

go环境安装mac

下载go安装包&#xff1a;https://golang.google.cn/dl/ 找到对应自己环境的版本下载。 注意有二进制的包&#xff0c;也有图形界面安装的包。图形界面直接傻瓜式点就行了。 二进制的按照下面操作&#xff1a; 1、下载二进制包。 2、将下载的二进制包解压至 /usr/local目录…...

Python实现对大批量Word文档进行批量自动化排版(15)

前言 本文是该专栏的第15篇,后面会持续分享Python办公自动化干货知识,记得关注。 在本专栏上一篇文章《Python实现对目标Word文档进行自动化排版【4万字精讲】(14)》中,笔者已经详细介绍“基于Python,实现对目标docx格式的word文档进行自动化排版”的实战教学(文章附带…...

嵌入式面试题解析:二维数组,内容与总线,存储格式

在嵌入式系统领域&#xff0c;扎实掌握基础概念是应对面试的关键。本文通过典型面试题&#xff0c;详细解析核心知识&#xff0c;梳理易错点&#xff0c;并补充常见面试题&#xff0c;助力新手快速入门。 一、二维数组元素地址计算 题目 若二维数组 arr[0..M-1][0..N-1] 的首…...

【iOS】alloc init new底层原理

目录 前言 alloc alloc核心操作 cls->instanceSize(extraBytes) calloc obj->initInstanceIsa init 类方法&#xff1a; 实例方法&#xff1a; new 前言 笔者最近在进行对OC语言源码的学习&#xff0c;学习源码的过程中经常会出现一些从来没有遇见过的函数&…...

解决vscode找不到Python自定义模块,报错No module named ‘xxx‘

1、 首先在.vscode下的launch.json中添加"env": {“PYTHONPATH”: “${workspaceRoot}”} {"version": "0.2.0","configurations": [{省略其他配置"env": {"PYTHONPATH": "${workspaceRoot}"}}] }2、 …...

【某比特币网址请求头部sign签名】RSA加密逆向分析

目标&#xff1a;aHR0cDovL21lZ2FiaXQudmlwL21hcmtldA 直接搜索sign不方便定位&#xff0c;可以换个思路搜asi_uuid或者user_info 为什么搜这个&#xff0c;因为都是请求头里面的参数&#xff0c;基本上会在一起 实际上就是Object(h.a)((new Date).getTime()) 直接在这里打断点…...

【Docker项目实战】使用Docker部署Jupyter Notebook服务

【Docker项目实战】使用Docker部署Jupyter Notebook服务 一、 Jupyter Notebook介绍1.1 Jupyter Notebook 简介1.2 主要特点1.3 主要使用场景二、本次实践规划2.1 本地环境规划2.2 本次实践介绍三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compos…...

Oracle高级语法篇 - 用户与角色关系

在Oracle数据库中&#xff0c;用户和角色是权限管理的核心概念。用户是数据库的使用者&#xff0c;而角色则是权限的集合。通过合理地分配角色给用户&#xff0c;可以简化权限管理&#xff0c;提高数据库的安全性和易用性。本文将详细讲解Oracle中用户和角色之间的关系&#xf…...

“小坝” 策略:始发站 buffer 控制与优化

端到端&#xff0c;这两个端是两个应用程序中的位置&#xff0c;第一个端指数据被产生处&#xff0c;第二个端指数据被消费处。更一般的&#xff0c;把数据发生的应用程序所在的主机视为数据始发站也是合理的。 网络中遍布 buffer&#xff0c;buffer 却是一把双刃剑的存在&…...

【esp32 点亮led】-解决不能闪烁问题

问题现象&#xff1a;将esp例程中的led例程下载到开发板中&#xff0c;led不能闪烁&#xff0c;串口查看&#xff0c;可以看到对应的led ON/led off 信息。 解决办法&#xff1a; 使用idf.py menuconfig 命令配置相应的引脚为GPIO模式&#xff0c;如下图所示&#xff0c;保存…...

自然语言处理(9)—— 共现词矩阵及Python实现

共现词矩阵 1. 概述2. 构建步骤3. 代码实现&#xff08;Python&#xff09;结语 共现词矩阵&#xff08;Co-occurrence Matrix&#xff09;是自然语言处理&#xff08;NLP&#xff09;中用于捕捉词语间语义关系的重要工具。共现矩阵通过统计词语在特定上下文窗口内的共现频率&a…...