实习记录--(海量数据如何判重?)--每天都要保持学习状态和专注的状态啊!!!---你的未来值得你去奋斗
海量数据如何判重?
判断一个值是否存在?解决方法:
1.使用哈希表:
可以将数据进行哈希操作,将数据存储在相应的桶中。
查询时,根据哈希值定位到对应的桶,然后在桶内进行查找。这种方法的时间复杂度为 O(1),但需要额外的存储空间来存储哈希表。如果桶中存在数据,则说明此值已存在,否则说明未存在。
2.使用布隆过滤器:
布隆过滤器是一种概率型数据结构,用于判断一个元素是否在集合中。它利用多个哈希函数映射数据到一个位数组,并将对应位置置为 1。
查询时,只需要对待查询的数据进行哈希,并判断对应的位是否都为 1。如果都为 1,则该数据可能存在;如果有一个位不为 1,则该数据一定不存在。布隆过滤器的查询时间复杂度为 O(k),其中 k 为哈希函数的个数。
相同点和不同点
相同点:
它们都存在误判的情况。
例如,使用哈希表时,不同元素的哈希值可能相同,所以这样就产生误判了;
而布隆过滤器的特征是,当布隆过滤器说,某个数据存在时,这个数据可能不存在;当布隆过滤器说,某个数据不存在时,那么这个数据一定不存在
不同点:
存储机制:
哈希表使用一个数组来存储键值对,通过哈希函数将键映射到数组的索引位置,然后将值存储在对应的位置上。
布隆过滤器则使用一个位数组(或位向量),通过多个哈希函数将元素映射到位数组的多个位上。
查询操作:
哈希表在进行查询时,通过计算哈希值来定位键值对的存储位置,然后直接获取对应的值。查询时间复杂度通常为 O(1)。
布隆过滤器在进行查询时,也通过多个哈希函数计算多个位,然后判断对应的位是否都为 1 来确定元素是否存在。查询时间复杂度为 O(k),其中 k 为哈希函数的个数。
内存占用:
哈希表需要根据数据规模来动态调整数组的大小,以保证存储效率。
布隆过滤器在预先设置位数组的大小后,不会随数据规模的增加而增长。因此布隆过滤器更适用于海量数据。
结论:
哈希表和布隆过滤器都能实现判重,但它们都会存在误判的情况,但布隆过滤器存储占用的空间更小,更适合海量数据的判重。
布隆过滤器实现原理:
布隆过滤器的实现:主要依靠的是它数据结构中的一个位数组,每次存储键值的时候,不是直接把数据存储在数据结构中,因为这样太占空间了,它是利用几个不同的无偏哈希函数,把此元素的 hash 值均匀的存储在位数组中,也就是说,每次添加时会通过几个无偏哈希函数算出它的位置,把这些位置设置成 1 就完成了添加操作。
当进行元素判断时,查询此元素的几个哈希位置上的值是否为 1,如果全部为 1,则表示此值存在,如果有一个值为 0,则表示不存在。因为此位置是通过 hash 计算得来的,所以即使这个位置是 1,并不能确定是那个元素把它标识为 1 的,因此布隆过滤器查询此值存在时,此值不一定存在,但查询此值不存在时,此值一定不存在。
并且当位数组存储值比较稀疏的时候,查询的准确率越高,而当位数组存储的值越来越多时,误差也会增大。
位数组和 key 之间的关系,如下图
如何实现布隆过滤器?
1.通过程序实现(内存级别方案):使用 Google Guava 库实现布隆过滤器。
2.通过中间件实现(支持数据持久化):使用 Redis 4.0 之后提供的布隆过滤插件来实现,它的好处是支持持久化,数据不会丢失。
一、什么是Guava
1)Guava库是一个适合很多Java项目的通用工具库
2)Guava工具库中包含了:集合Collection、并发Concurrency、原语Primitive、反射Reflection、比较Comparison、I/O操作、哈希Hash、网络Networking、字符串String、数学函数Math、缓存Caching、内存中的发布/订阅……以及各种级别的数据类型
3)需要JDK 6以上版本
使用 Google Guava 库实现布隆过滤器总共分为以下两步:
- 引入 Guava 依赖
- 使用 Guava API 操作布隆过滤器
① 引入 Guava 依赖
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId>
</dependency>
② 使用 Guava API
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;public class BloomFilterExample {public static void main(String[] args) {// 创建一个布隆过滤器,设置期望插入的数据量为10000,期望的误判率为0.01BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.unencodedCharsFunnel(), 10000, 0.01);// 向布隆过滤器中插入数据bloomFilter.put("data1");bloomFilter.put("data2");bloomFilter.put("data3");// 查询元素是否存在于布隆过滤器中System.out.println(bloomFilter.mightContain("data1")); // trueSystem.out.println(bloomFilter.mightContain("data4")); // false}
}
在上述示例中,我们通过 BloomFilter.create() 方法创建一个布隆过滤器,指定了元素序列化方式、期望插入的数据量和期望的误判率。然后,我们可以使用 put() 方法向布隆过滤器中插入数据,使用 mightContain() 方法来判断元素是否存在于布隆过滤器中。
相关文章:

实习记录--(海量数据如何判重?)--每天都要保持学习状态和专注的状态啊!!!---你的未来值得你去奋斗
海量数据如何判重? 判断一个值是否存在?解决方法: 1.使用哈希表: 可以将数据进行哈希操作,将数据存储在相应的桶中。 查询时,根据哈希值定位到对应的桶,然后在桶内进行查找。这种方法的时间复…...

【MATLAB源码-第67期】基于麻雀搜索算法(SSA)的无人机三维地图路径规划,输出最短路径和适应度曲线。
操作环境: MATLAB 2022a 1、算法描述 麻雀搜索算法(Sparrow Search Algorithm, SSA)是一种新颖的元启发式优化算法,它受到麻雀社会行为的启发。这种算法通过模拟麻雀的食物搜索行为和逃避天敌的策略来解决优化问题。SSA通过模…...

Promise的并发控制 - 从普通并发池到动态并发池
一、场景 给你一个有200个URL的数组,通过这些URL来发送请求,要求并发请求数不能超过五个。 这是一道很常考的面试题,接下来让我们来学习一下Promise并发控制 二、普通并发池的实现 主要思路就是,判断当前队列是否满,…...

Java类加载机制(类加载器,双亲委派模型,热部署示例)
Java类加载机制 类加载器类加载器的执行流程类加载器的种类加载器之间的关系ClassLoader 的主要方法Class.forName()与ClassLoader.loadClass()区别 双亲委派模型双亲委派 类加载流程优缺点 热部署简单示例 类加载器 类加载器的执行流程 类加载器的种类 AppClassLoader 应用类…...

【C语言初学者周冲刺计划】3.2将一个数组中的值逆序重新存放
目录 1解题思路: 2代码 3运行代码如图: 4总结: 1解题思路: 首先学会如何利用循环输入位数和输入数值,然后再利用循环逆序即可 2代码 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int main() { int…...

【C++心愿便利店】No.11---C++之string语法指南
文章目录 前言一、 为什么学习string类二、标准库中的string类 前言 👧个人主页:小沈YO. 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:C 心愿便利店 🔑本章内容:str…...

OpenCV检测圆(Python版本)
文章目录 示例代码示例结果调参 示例代码 import cv2 import numpy as np# 加载图像 image_path DistanceComparison/test_image/1.png image cv2.imread(image_path, cv2.IMREAD_COLOR)# 将图像转换为灰度 gray cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)# 使用高斯模糊消除…...

轻量封装WebGPU渲染系统示例<15>- DrawInstance批量绘制(源码)
当前示例源码github地址: https://github.com/vilyLei/voxwebgpu/blob/main/src/voxgpu/sample/DrawInstanceTest.ts 此示例渲染系统实现的特性: 1. 用户态与系统态隔离。 细节请见:引擎系统设计思路 - 用户态与系统态隔离-CSDN博客 2. 高频调用与低频调用隔离。…...
E: 仓库 “http://cn.archive.ubuntu.com/ubuntu kinetic Release” 没有 Release 文件。
sudo apt-get update时报以下错误: E: 仓库 “http://cn.archive.ubuntu.com/ubuntu kinetic Release” 没有 Release 文件。 N: 无法安全地用该源进行更新,所以默认禁用该源。 N: 参见 apt-secure(8) 手册以了解仓库创建和用户配置方面的细节。 E: 仓库…...

【VR开发】【Unity】【VRTK】3-VR项目设置
任何VR避不开的步骤 如何设置VR项目,无论是PC VR还是安卓VR,我在不同的系列教程中都说过了,不过作为任何一个VR开发教程都难以避免的一环,本篇作为VRTK的开发教程还是对VR项目设置交代一下。 准备好你的硬件 头盔必须是6DoF的,推荐Oculus Quest系列,Rift系列,HTC和Pi…...
git log 用法
git log --format"%s" -n 1在 Git 中,您可以使用 git log 命令来查看提交历史,其中包含每个提交的详细信息,包括提交消息。如果您只想提取提交信息而不是完整的 git log 输出,可以使用 git log 命令的 --format 选项来指…...
Linux学习---有关监控系统zabbix的感悟
监控系统 监控系统就像咱们日常生活中小区监控(Monitor),用于及时发现问题(PROBLEM),根据相应的规则可以触发警告(Media),在后台显示屏(Dashboard)上以某种方面显示出来,高级的报警系统也许还能实现电话通知等功能,目的是为及时发…...

apollo云实验:定速巡航场景仿真调试
定速巡航场景仿真调试 概述启动仿真环境仿真系统修改默认巡航速度 实验目的福利活动 主页传送门:📀 传送 概述 自动驾驶汽车在实现落地应用前,需要经历大量的道路测试来验证算法的可行性和系统的稳定性,但道路测试存在成本高昂、…...

基于RK3568的新能源储能能量管理系统ems
新能源储能能量管理系统(EMS)是一种基于现代化技术的系统,旨在管理并优化新能源储能设备的能量使用。 该系统通过监测、调度和控制新能源储能设备来确保能源的高效利用和可持续发展。 本文将从不同的角度介绍新能源储能能量管理系统的原理、…...

dockerfile避坑笔记(VMWare下使用Ubuntu在Ubuntu20.04基础镜像下docker打包多个go项目)
一、docker简介 docker是一种方便跨平台迁移应用的程序,通过docker可以实现在同一类操作系统中,如Ubuntu和RedHat两个linux操作系统中,实现程序的跨平台部署。比如我在Ubuntu中打包了一个go项目的docker镜像(镜像为二进制文件&am…...

Qt 使用QtXlsx操作Excel表
1.环境搭建 QtXlsx是一个用于读写Microsoft Excel文件(.xlsx)的Qt库。它提供了一组简单易用的API,可以方便地处理电子表格数据。 Github下载:GitHub - dbzhang800/QtXlsxWriter: .xlsx file reader and writer for Qt5 官方文档…...

canal+es+kibana+springboot
1、环境准备 服务器:Centos7 Jdk版本:1.8 Mysql版本:5.7.44 Canal版本:1.17 Es版本:7.12.1 kibana版本:7.12.1 软件包下载地址:链接:https://pan.baidu.com/s/1jRpCJP0-hr9aI…...
【力扣】面试经典150题——双指针
文章目录 125. 验证回文串392. 判断子序列167. 两数之和 II - 输入有序数组11. 盛最多水的容器15. 三数之和 125. 验证回文串 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字…...

6-8 最宽层次结点数 分数 10
文章目录 1.题目描述2.本题ac答案2.1法一: 代码复用2.2法二: 顺序队列实现层序遍历 3.C层序遍历求最大宽度3.1层序遍历代码3.2求最大宽度 1.题目描述 2.本题ac答案 2.1法一: 代码复用 //二叉树第i层结点个数 int LevelNodeCount(BiTree T, int i) {if (T NULL || i < 1)re…...

Linux学习第28天:Platform设备驱动开发(二): 专注与分散
Linux版本号4.1.15 芯片I.MX6ULL 大叔学Linux 品人间百味 思文短情长 三、硬件原理图分析 四、驱动开发 1、platform设备与驱动程序开发 53 /* 54 * 设备资源信息,也就是 LED0 所使用的所有寄存器 55 */ 56 static str…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...

JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...

STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...