【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. 核心组件
-
哈希函数:
-
将输入元素映射为足够长的比特串(通常 64 位)
-
要求:均匀分布、确定性
-
-
分桶(Register):
-
使用前 m 个比特确定桶索引(m 通常取 12-16)
-
剩余比特用于计算连续前导零的数量
-
-
调和平均数:
-
用于合并各桶的估算值,减少误差
-
3. 算法步骤
-
初始化:
m = 2^b # b 通常取 4-16 registers = [0] * m
-
添加元素:
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)
-
估算基数:
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:使用线性计数
-
当检测到空桶:调整估算公式
五、性能优化技术
-
稀疏表示:
-
对小基数使用显式存储
-
当基数较小时直接存储元素而非寄存器值
-
-
偏差校正:
-
对小范围基数使用预先计算的校正表
-
消除系统偏差
-
-
寄存器压缩:
-
使用变长编码压缩寄存器数组
-
在合并时解压缩处理
-
六、应用场景
-
网站UV统计:
# 统计日UV PFADD daily:uv:20230501 user1 user2 user3 PFCOUNT daily:uv:20230501
-
跨日统计:
PFMERGE weekly:uv daily:uv:20230501 daily:uv:20230502 ... daily:uv:20230507
-
A/B测试:
# 统计不同方案的独立用户数 PFADD variant:A user1 user3 user5 PFADD variant:B user2 user3 user6
七、与其他基数统计方案对比
算法 | 内存占用 | 误差率 | 是否精确 | 合并能力 |
---|---|---|---|---|
HashSet | O(N) | 0% | 是 | 否 |
Linear Counting | O(N) | 可变 | 否 | 是 |
LogLog | O(log(logN)) | 1.3/√m | 否 | 是 |
HyperLogLog | O(log(logN)) | 0.81/√m | 否 | 是 |
HyperLogLog++ | O(log(logN)) | 0.81/√m | 否 | 是 |
八、实现注意事项
-
哈希函数选择:
-
需要良好的分布特性
-
Redis 使用 64 位 MurmurHash2
-
-
寄存器位数:
-
通常 5-6 位足够(最大前导零 32-64)
-
更多位数对精度提升有限
-
-
边界情况处理:
-
空数据集返回 0
-
小数据集使用精确计数
-
HyperLogLog 通过巧妙的概率统计方法和分桶技术,在极小内存占用下实现了大规模数据集的基数估算,是大数据时代不可或缺的基数统计工具。Redis 的实现进一步优化了内存使用和计算效率,使其成为实际应用中的首选方案。
相关文章:
【2025最新redis数据结构之Hypeloglog介绍】关于Hypeloglog
HyperLogLog (HLL) 算法深度解析 一、HLL 基本概念 HyperLogLog 是一种用于基数统计(distinct counting)的概率算法,能够在极小内存占用下(通常只需几KB)估算巨大数据集的基数(不重复元素数量)…...
软考复习——知识点软件开发
开发模型 瀑布模型 各个活动规定为线性顺序连接的若干阶段的模型。是一种理想的现象开发模型,缺乏灵活性,无法理解软件需求不明确或不准确的问题。适用于需求明确的项目。 演化模型 从初始的原型逐步演化成最终软件产品,特别适用于对软件…...
关于AI:记忆、身份和锁死
作者:John Battelle 当生成式AI迎来投资热潮、产品发布和炒作高峰时,我们大多数人在奔向“下一个大事件”的过程中,忽略了一个深层次的缺陷。我们现在主流的AI产品和服务(比如OpenAI、Google和Microsoft的产品)都是通过…...
2024新版仿蓝奏云网盘源码,已修复已知BUG,样式风格美化,可正常运营生产
说起网盘源码,网络上出现的也很多,不过可真正正能够用于运营的少之又少。今天将的蓝奏云网盘源码,其实网络上也有,不过是残缺版,bug很多。我今天分享的仿蓝奏云模板是经过长时间测试修复后的源码,源码实测可…...
OJ - 设计循环队列
622. 设计循环队列 - 力扣(LeetCode) 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则,并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可…...
实战指南:封装Faster-Whisper为FastAPI接口并实现高并发处理-附整合包
实战指南:封装Faster-Whisper为FastAPI接口并实现高并发处理-附整合包 「faster-whisper」 链接:https://pan.quark.cn/s/d4ddffb1b196 标题下面提供一个完整的示例,说明如何使用 FastAPI 封装 faster-whisper 接口,对外提供 RES…...
011数论——算法备赛
素数筛 给定n, 求2~n内的所有素数 埃氏筛 利用素数的定义, 输出素数2,然后筛掉2的倍数,得 {2,3,5,7,9,11,13,…}输出素数3,然后筛掉3的倍数,得 {2,3,5,7,11,13,…} 继续上述步骤࿰…...
C语言之机房机位预约系统
🌟 嗨,我是LucianaiB! 🌍 总有人间一两风,填我十万八千梦。 🚀 路漫漫其修远兮,吾将上下而求索。 C语言之机房机位预约系统 目录 博客:机房机位预约系统设计与实现 系统功能概述…...
中间件--ClickHouse-14--案例-3-其他案例思路概述
1、广告投放效果分析 案例背景: 一家广告平台需要分析广告的点击、曝光、转化等数据,以优化广告投放策略并提升 ROI(投资回报率)。 解决方案: 数据接入:将广告投放相关的数据(如曝光、点击、…...
saas是什么?它做什么用的。及和Paas和laas有什么区别
Saas是什么?它做什么用的。及和Paas和laas有什么区别 提示:帮帮志会陆续更新非常多的IT技术知识,希望分享的内容对您有用。本章分享的是行业内容。前后每一小节的内容是存在的有:学习and理解的关联性,希望对您有用~ 文…...
Qt基础005(文件操作后续)
文章目录 QFileDialogQFileDialog打开开发案例QFileDialog保存开发案例实现文件打开功能开发流程打开功能优化 QComboBoxQListExtraSelection 简介 QFileDialog QFileDialog打开开发案例 #include <QApplication> #include <QFileDialog> #include <QStringLi…...
松灵Cobot Magic双臂具身遥操机器人(基于ROS的定位建图与协同导航技术)
摘要 本文以CobotMagic可移动协作机器人为研究对象,从硬件架构设计、软件系统架构、多传感器融合定位建图系统、智能导航系统协同机制四个维度,深入解析机器人系统工作原理。重点研究多传感器融合定位建图系统实现原理,结合实测数据验证系统…...
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.什么是序列化? 在项目的开发中,为了让前端更好的分析后端返回的结果,我们一般会将返回的信息进行序列化,序列化就是将返回对象的状态信息转换为一种标准化的格式,方便在网络中传输也方便打印日志时号观察࿰…...
QML中日期处理类
在 QML 中处理日期和时间主要使用 JavaScript 的 Date 对象以及 Qt 提供的一些相关功能。以下是常用的日期处理方式: 1. JavaScript Date 对象 QML 可以直接使用 JavaScript 的 Date 对象: qml // 创建当前日期时间 var currentDate new Date()// 创…...
基于docker-java封装的工具类
基于docker-java封装的工具类 背景环境工具类 背景 写OJ系统时需要用docker作为代码沙箱使用,顺手封装了一个工具类,给自己做个笔记,如果可以的话也希望帮助到其他人。 环境 docker 26.1.4docker-java 3.4.2docker-java-transport-httpcli…...
windows docker desktop 无法访问容器端口映射
为什么使用docker desktop访问映射的端口失败,而其端口对应的服务是正常的? 常见问题,容器的防火墙没有关闭!!! 以centos7为例,默认情况下防火墙处于开启状态: 这下访问就OK了...
ReentrantReadWriteLock读写锁
一、锁的分类 这里不会对Java中大部分的分类都聊清楚,主要把 **互斥,共享** 这种分类聊清楚。 Java中的互斥锁,synchronized,ReentrantLock这种都是互斥锁。一个线程持有锁操作时,其他线程都需要等待前面的线程释放锁…...
Vue.js 入门教程
Vue.js 入门教程 Vue.js 是一款非常流行的前端 JavaScript 框架,适用于构建用户界面。它的设计思想是尽可能简单、灵活,易于与其他库或现有项目整合。本文将从最基础的概念开始,逐步引导你学习 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 摘要 在进行车载测试用例编写时,会遇到多个条件导致用例排列组合爆炸的情况,但是为了产品测试质量,我们又不得不保证用例设计的需求覆盖度,这样又会使得测试周期非常长。我们如何平衡效率和测试质量?本文进行了一些…...
leetcode(01)森林中的兔子
今天开始记录刷题的过程,每天记录自己刷题的题目和自己的解法,欢迎朋友们给出更多更好的解法。 森林中的兔子 森林中有未知数量的兔子,提问其中若干只兔子“还有多少只兔子与你(被提问的兔子)颜色相同”。将答案收集到…...
人工智能-机器学习其他技术(决策树,异常检测,主成分分析)
决策树 一种对实例进行分类的树形结构,通过多层判断区分目标所属类别 本质:通过多层判断,从训练数据集中归纳出一组分类规则 优点: 计算量校,运算速度快 易于理解 缺点: 忽略属性间的相关性 样本分布不均时…...
AIGC通信架构深度优化指南
AIGC通信架构深度优化指南 标题:《百亿参数大模型如何高效通信?揭秘AIGC系统的协议层设计艺术》 副标题:从分布式训练到多模态推理,构建高可靠AI通信系统 1. AIGC典型通信场景 1.1 分布式模型训练参数同步 sequenceDiagram训练…...
精益数据分析(7/126):打破创业幻想,拥抱数据驱动
精益数据分析(7/126):打破创业幻想,拥抱数据驱动 在创业的道路上,我们都怀揣着梦想,但往往容易陷入自我编织的幻想中。我希望通过和大家一起学习《精益数据分析》,能帮助我们更清醒地认识创业过…...
Android Gradle多渠道打包
目录 1.多渠道打包是什么2.为什么需要多渠道打包3.多渠道配置VariantproductFlavorsbuildTypes 3.构建变体组合关于组合 4.渠道过滤5.渠道资源资源文件资源合并规则代码文件SourceSets 6. 渠道依赖项7.渠道统计meta-dataBuildConfig 8.管理渠道 1.多渠道打包是什么 多聚道打包…...
Day58 | 179. 最大数、316. 去除重复字母、334. 递增的三元子序列
179. 最大数 题目链接:179. 最大数 - 力扣(LeetCode) 题目难度:中等 代码: class Solution {public String largestNumber(int[] nums) {String[] strsnew String[nums.length];for(int i0;i<nums.length;i)str…...
LabVIEW发电机励磁系统远程诊断
变流器在风电系统中承担电能转换与控制的关键角色。它将发电机输出的低频、可变交流,通过整流、逆变等环节转为频率、电压稳定的交流,以满足电网接入要求;同时,根据实时风速调整发电机转速,实现最大功率追踪。 在某…...
性能比拼: Go vs Bun
本内容是对知名性能评测博主 Anton Putra Go (Golang) vs. Bun: Performance (Latency - Throughput - Saturation - Availability) 内容的翻译与整理, 有适当删减, 相关指标和结论以原作为准 我对 Bun 在之前的基准测试中的出色表现感到惊讶,因此我决定将它与 Go …...
Kubernetes相关的名词解释Dashboard界面(6)
什么是Kubernetes Dashboard? Kubernetes Dashboard 是一个基于 Web 的用户界面,用于管理 Kubernetes 集群。它是 Kubernetes 官方提供的可视化工具,允许用户通过直观的图形界面而不是命令行来部署、管理和监控集群中的应用程序。 Dashboard…...
Linux网络编程 TCP---并发服务器:多进程架构与端口复用技术实战指南
知识点1【并发服务器—多进程版】 并发服务器:服务器可以同时服务多个客户端 首先复习一下服务器的创建过程(如下图) 1、监听套接字(套接字→绑定→监听(连接队列)) 2、利用accept从连接队列…...
(done) 吴恩达版提示词工程 1. 引言
url: https://www.bilibili.com/video/BV1Z14y1Z7LJ/?spm_id_from333.337.search-card.all.click&vd_source7a1a0bc74158c6993c7355c5490fc600 LLM 有两种: 1.基础 LLM,通过文本训练数据预测后面的内容。 这种 LLM 当你给它提问:What is…...
uniapp微信小程序实现sse
微信小程序实现sse 注:因为微信小程序不支持sse请求,因为后台给的是分包的流,所以我们就使用接受流的方式,一直接受,然后把接受的数据拿取使用。这里还是使用uniapp的原生请求。 上代码 //注意:一定要下…...
【TeamFlow】3 Rust 与 WebAssembly (Wasm) 深度应用指南
WebAssembly 是一种低级的类汇编语言,能在现代浏览器中高效执行。Rust 因其无 GC、内存安全和卓越性能,成为编译到 Wasm 的理想语言。 一、为什么选择 Rust Wasm 性能优势:Rust 生成的 Wasm 代码执行效率接近原生 内存安全:避免…...
C 语言的未来:在变革中坚守与前行
C 语言,作为编程语言领域的一位 “老将”,自诞生以来就一直扮演着至关重要的角色。历经数十年的发展,它的影响力依然广泛而深远。在科技飞速发展的今天,新的编程语言如雨后春笋般不断涌现,C 语言的未来发展走向成为了众…...
SQL注入之information_schema表
1 information_schema表介绍: information_schema表是一个MySQL的系统数据库,他里面包含了所有数据库的表名 SQL注入中最常见利用的系统数据库,经常利用系统数据库配合union联合查询来获取数据库相关信息,因为系统数据库中所有信…...
android framework开发的技能要求
作为Android Framework开发工程师,需要具备深入的系统底层理解能力和对Android架构的全面认知。以下是核心技能要求,分为技术能力和软实力两大方向: 一、核心技术能力 Android系统架构深度掌握 Binder机制:理解Binder驱动、ServiceManager、AIDL跨进程通信原理,能分析Bind…...
AWS EC2完全指南:如何快速搭建高性能云服务器?
一、什么是AWS EC2?云时代的虚拟服务器革命 AWS Elastic Compute Cloud(EC2)作为全球领先的云服务器解决方案,正在重新定义虚拟服务器的可能性。与传统VPS相比,EC2提供: 秒级弹性扩展:CPU/RAM按…...
go环境安装mac
下载go安装包:https://golang.google.cn/dl/ 找到对应自己环境的版本下载。 注意有二进制的包,也有图形界面安装的包。图形界面直接傻瓜式点就行了。 二进制的按照下面操作: 1、下载二进制包。 2、将下载的二进制包解压至 /usr/local目录…...
Python实现对大批量Word文档进行批量自动化排版(15)
前言 本文是该专栏的第15篇,后面会持续分享Python办公自动化干货知识,记得关注。 在本专栏上一篇文章《Python实现对目标Word文档进行自动化排版【4万字精讲】(14)》中,笔者已经详细介绍“基于Python,实现对目标docx格式的word文档进行自动化排版”的实战教学(文章附带…...
嵌入式面试题解析:二维数组,内容与总线,存储格式
在嵌入式系统领域,扎实掌握基础概念是应对面试的关键。本文通过典型面试题,详细解析核心知识,梳理易错点,并补充常见面试题,助力新手快速入门。 一、二维数组元素地址计算 题目 若二维数组 arr[0..M-1][0..N-1] 的首…...
【iOS】alloc init new底层原理
目录 前言 alloc alloc核心操作 cls->instanceSize(extraBytes) calloc obj->initInstanceIsa init 类方法: 实例方法: new 前言 笔者最近在进行对OC语言源码的学习,学习源码的过程中经常会出现一些从来没有遇见过的函数&…...
解决vscode找不到Python自定义模块,报错No module named ‘xxx‘
1、 首先在.vscode下的launch.json中添加"env": {“PYTHONPATH”: “${workspaceRoot}”} {"version": "0.2.0","configurations": [{省略其他配置"env": {"PYTHONPATH": "${workspaceRoot}"}}] }2、 …...
【某比特币网址请求头部sign签名】RSA加密逆向分析
目标:aHR0cDovL21lZ2FiaXQudmlwL21hcmtldA 直接搜索sign不方便定位,可以换个思路搜asi_uuid或者user_info 为什么搜这个,因为都是请求头里面的参数,基本上会在一起 实际上就是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数据库中,用户和角色是权限管理的核心概念。用户是数据库的使用者,而角色则是权限的集合。通过合理地分配角色给用户,可以简化权限管理,提高数据库的安全性和易用性。本文将详细讲解Oracle中用户和角色之间的关系…...
“小坝” 策略:始发站 buffer 控制与优化
端到端,这两个端是两个应用程序中的位置,第一个端指数据被产生处,第二个端指数据被消费处。更一般的,把数据发生的应用程序所在的主机视为数据始发站也是合理的。 网络中遍布 buffer,buffer 却是一把双刃剑的存在&…...
【esp32 点亮led】-解决不能闪烁问题
问题现象:将esp例程中的led例程下载到开发板中,led不能闪烁,串口查看,可以看到对应的led ON/led off 信息。 解决办法: 使用idf.py menuconfig 命令配置相应的引脚为GPIO模式,如下图所示,保存…...
自然语言处理(9)—— 共现词矩阵及Python实现
共现词矩阵 1. 概述2. 构建步骤3. 代码实现(Python)结语 共现词矩阵(Co-occurrence Matrix)是自然语言处理(NLP)中用于捕捉词语间语义关系的重要工具。共现矩阵通过统计词语在特定上下文窗口内的共现频率&a…...