哈希处理海量数据
接下来我们将以问题的形式来介绍如何用hash处理海量数据。
1.问题1 (位图)
给定100亿个整数,设计算法找到只出现一次的。
1.1问题分析
100亿个整数,一个整数占用4byte,那么就需要约40G左右的空间来存储。显然常见的map等数据结构无法在运行内存中进行处理。我们会想到之前学的位图,其是用一个bite位来标记数字的两种状态(0表示不存在,1表示存在),但此题中的每个整数可以看成三种状态(00表示不存在,01表示出现一次,10表示出现两次)。
1.2问题解答
方案一:
在位图的基础上,我们利用其原理,对位图的进行改造。我们不再用一个bite位映射一个整数,而是用两个bite位映射一个整数。
方案二:
既然每个数字要两个bite位存储,那么我们可以用两个位图来存储每个数字的信息,bm1存储第一个bite位,bm2存储第二个bite位
2.问题2(位图)
两个文件,各有100亿个整数,我们只有1G的内存,如何找到这两个文件的交集
2.1问题分析
海量数据处理,显然普通的数据结构无法解决,我们考虑用位图来解决问题。一个能代表整形的位图有0.5G的大小
2.2问题解答
方案1:
我们可以利用一个位图来存储文件1的信息,再读取文件2的整数依次在位图中test即可解决问题。
方案2:
我们可以利用位图1来存储文件1的信息,位图2来存储文件2的信息。再将两个位图的bite位按位与,得到的新位图即为交集部分。
3.问题3(布隆过滤器and哈希分割)
两个文件,分别有100亿个query,我们有1G的内存,如何找到两个文件的交集?分别给出精确算法和近似算法
3.1问题分析
一个query我们可以将其看为字符串,大概有30个字节大小,那么100亿个query就是300-600G的大小,显然常规的数据结构无法解决。我们考虑用bloom_filter来解决近视算法。
3.2问题解决
方案1:近似算法
我们用一个布隆过滤器来存储文件1的信息,再将文件2的信息依次在布隆过滤器中test,如果每个hash都test成功,那么就可能是交集(也有可能误判,将不是交集的判断为交集)。
方案2:准确算法
显然准确算法不能使用bloom_filter,但是这么多数据无法一一放进内存中,我们思考可否将文件切分为小的文件,再放入内存中呢?
上述的算法就是先将A文件均分为小文件,将B文件也均分为小文件,让在内存中用set进行处理。例如A0,先将A0存储到set中,再B0,B1,B2 ...B999中的数据依次在set中查找;接着A1-B0,B1,B2...B999。显然效率实在是太低了。
那如果我们不均分呢?用hash切割呢?
如图,我们在前期切割的时候,不采用均分切割,采用hash切割:依次取出文件中的字符串,利用字符哈希函数,得到hash值%文件个数,得到的结果就是这个数据一个要进的小文件编号。这样就保证了相同的字符串会进入相同的文件中,这样我们只需要将A0与B0在内存中用set处理,A1与B1....
4.问题4(哈希分割)
给一个超过100G的文件,里面存储着ip地址,设计算法找到出现次数最多的ip地址,或者出现次数为top k的地址?
4.1问题分析
处理数据是string,精确查找要求不能使用bloom过滤器,那么我们思考采用划分小文件的方法。
4.2问题解决
我们可以创建1000个小文件,依次编号A0-A999.采用Hash分割,将相同的ip分到同一个文件中。在内存中我们利用map,统计A0文件中的各个ip出现的次数,再利用multimap<int,string>统计出现最多的字符串,在创建一个pair<string,int> max,存储这个字符串。再依次A1-A999,每次更新最多字符串即可。
如果是要topk的字符串,那么我们可以建一个小堆进行数据处理。
5.问题5(一致性哈希)
微信号-朋友圈问题
我们可以近似的将微信号和朋友圈看为kv模型。那么这些数据如何存储呢?
如果10亿用户,每个用户分100M的空间,那么我们需要10万T的空间,假设我们有10万台主机,每台机器能存储1T的信息。
分析:当用户claus发朋友圈时,那么我们应该插入哪台机器呢?显然我们可以采用哈希的思路找到微信号和服务器的映射关系,将朋友圈信息插入到对应服务器中。
那么当我们 扩容服务器时,将10w台服务器扩大为15w台服务器时,数据如何迁移呢?难道要将所有数据重新映射码?显然上面的模型存在缺陷。我们引入一致性hash的概念。
一致性hash时,上图中的应该是x%2^32,这样x会落在0-2^32-1的范围内,我们不再将x与服务器一一对应,而是范围对应,例如将0-10000的值映射到服务器1号,10001的值映射到服务器2号....。
当我们需要扩容时,只需要选择一段高负载范围区,将其分一份范围出来,将数据迁移到新服务器上,修改范围映射范围即可。
相关文章:
哈希处理海量数据
接下来我们将以问题的形式来介绍如何用hash处理海量数据。 1.问题1 (位图) 给定100亿个整数,设计算法找到只出现一次的。 1.1问题分析 100亿个整数,一个整数占用4byte,那么就需要约40G左右的空间来存储。显然常见的…...
Go语言基础教程1
Go语言基础教程 目录 变量声明与使用基本数据类型常量切片操作字符串处理指针格式化输出参数 一、变量声明 1.1 基本变量声明 // 标准声明 var variableName variableType// 示例 var age int var name string1.2 变量声明与初始化 // 显式类型声明 var age int 30// 类…...
【每日一道面试题】for与foreach的区别(2024/12/6)
目录 foreach的特点遍历时删除时 foreach 和 for循环遍历数组的差别关于 foreach 和 for 循环的效率问题 首先我们要对foreach有个基本的了解,才能对它们进行区别 foreach的特点 遍历时 用foreach循环去遍历一个数组, 用foreach循环去遍历一个集合&…...
解密时序数据库的未来:TDengine Open Day技术沙龙精彩回顾
在数字化时代,开源已成为推动技术创新和知识共享的核心力量,尤其在数据领域,开源技术的涌现不仅促进了行业的快速发展,也让更多的开发者和技术爱好者得以参与其中。随着物联网、工业互联网等技术的广泛应用,时序数据库…...
React第十一节 组件之间通讯之发布订阅模式(自定义发布订阅器)
组件之间通讯常用方案 1、通过props 2、通过context 3、通过发布订阅模式 4、通过Redux 后面会有专栏介绍 什么情况下使用发布订阅模式 a、当我们想要兄弟组件之间通讯,而共同的父组件中又用不到这些数据时候; b、当多个毫无相关的组件之间想要进行数据…...
Vue 2与Vue 3项目中的屏幕缩放适配:使用vue2-scale-box和vue3-scale-box
🌟 前言 欢迎来到我的技术小宇宙!🌌 这里不仅是我记录技术点滴的后花园,也是我分享学习心得和项目经验的乐园。📚 无论你是技术小白还是资深大牛,这里总有一些内容能触动你的好奇心。🔍 &#x…...
Brain.js(九):LSTMTimeStep 实战教程 - 未来短期内的股市指数预测 - 实操要谨慎
系列的前一文RNNTimeStep 实战教程 - 股票价格预测 讲述了如何使用RNN时间序列预测实时的股价, 在这一节中,我们将深入学习如何利用 JavaScript 在浏览器环境下使用 LSTMTimeStep 进行股市指数的短期预测。通过本次实战教程,你将了解到如何用…...
云计算考试题
1、与SaaS不同的,这种“云”计算形式把开发环境或者运行平台也作为一种服务给用户提供。(B) A、软件即服务 B、基于平台服务 C、基于WEB服务 D、基于管理服务 2、云计算是对(D)技术的发展与运用 A、并行计算 B、网格计算 C、分布式计算 D、三个选项都是 3、Amazon.com公司…...
【设计模式】装饰器模式 在java中的应用
文章目录 1. 引言装饰器模式的定义与设计目的装饰器模式与其他设计模式的比较 2. 装饰器模式的结构组件接口(Component)具体组件(ConcreteComponent)装饰角色(Decorator)具体装饰类(ConcreteDec…...
【kafka】生产者的同步发送和异步发送
Kafka 的生产者端提供了同步发送和异步发送两种方式,适合不同的使用场景和性能需求。 以下是两种发送模式的详细讲解: 同步发送 概念 同步发送是指生产者在发送一条消息后,会阻塞当前线程,等待 Kafka 返回发送结果(…...
8. Debian系统中显示屏免密码自动登录
本文介绍如何在Debian系统上,启动后,自动免密登录,不卡在登录界面。 1. 修改lightDM配置文件 嵌入式Debian系统采用lightDM显示管理器,所以,一般需要修改它的配置文件/etc/lightdm/lightdm.conf,找到[Seat…...
SpringBoot 开源停车场管理收费系统
一、下载项目文件 下载源码项目文件口令: 【前端小程序地址】(3.0):伏脂火器白泽知洞座/~6f8d356LNL~:/【后台管理地址】(3.0):伏脂火器仇恨篆洞座/~0f4a356Ks2~:/【岗亭端地址】(3.0):动作火器智汇堂多好/~dd69356K6r~:/复制口令…...
QT的ui界面显示不全问题(适应高分辨率屏幕)
//自动适应高分辨率 QCoreApplication::setAttribute(Qt::AA_EnableHighDpiScaling);一、问题 电脑分辨率高,默认情况下,打开QT的ui界面,显示不全按钮内容 二、解决方案 如果自己的电脑分辨率较高,可以尝试以下方案:自…...
双向链表的模拟实现 —— LinkedList
MyLinkedList类 public class MyLinkedList {// 定义节点类static class Node {int val;Node prev;Node next;public Node() {}public Node(int val) {this.val val;}}// 定义头节点private Node head;// 定义尾结点private Node tail;// 头插public void headInsert(int val…...
速盾:高防cdn预热指定url就只刷新这个吗?
高防CDN预热是指在网站上线或更新之前,将网站内容缓存到CDN节点服务器上,以提高用户访问网站的速度和稳定性。通常,预热可以通过指定URL来进行,而不是刷新整个网站。 预热指定URL的好处是可以选择性地进行缓存刷新,而…...
JDK21新特性
目录 虚拟线程(JEP 444): 顺序集合(JEP 431): 字符串模板(JEP 430): 模式匹配的增强(JEP 440、441以及443): 结构化并发和作用域值…...
json学习
JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,易于人阅读和编写,也易于机器解析和生成。它通常用于在服务器和客户端之间交换数据,特别是在 Web 应用中。 JSON 格式基于 JavaScript 对象表示法&#…...
005-mysql常用的名称
语言分类 DDL :数据定义语言 1、线上DDL语句在对表操作,是要锁元数据表的,此时所有的修改类的命令无法正常运行。 2、对大表在高峰期进行DDL操作,可以使用工具:pt-online-schema-change gh-ost 工具(8.0以…...
PostgreSQL和MySQL区别
PostgreSQL 和 MySQL 有以下一些主要区别: 一、功能特性 1. 数据类型支持 - PostgreSQL:支持丰富的数据类型,包括数组、JSON、JSONB、hstore(键值对存储)、范围类型等。例如,可以直接在数据库中存储和查…...
Android笔记(三十四):onCreate执行Handler.post在onResume后才能执行?
背景 偶然发现一个点,就是在onCreate执行Handler.post在onResume后才执行,以下是测试代码 多次运行的结果一致,为什么execute runnable不是在onCreate和onResume之间执行的呢,带着疑问撸了一遍Activity启动流程 关键源码分析 …...
动手学深度学习d2l包M4芯片 gpu加速
conda创建环境 CONDA_SUBDIRosx-arm64 conda create -n ml python3.9 -c conda-forge conda env config vars set CONDA_SUBDIRosx-arm64 conda activate mlpip安装包 pip install --pre torch torchvision torchaudio --extra-index-url https://download.pytorch.org/whl/n…...
游戏引擎学习第35天
开场介绍 今天的任务是继续改进一个虚拟的瓦片地图系统,使其适合处理更大的世界。我们希望这个系统能管理大范围的游戏世界,其中包含按需存储的小区域。昨天,我们介绍了“内存区域”的概念,用于管理持久性存储。我们计划今天继续…...
Python 3 和 MongoDB 的集成使用
Python 3 和 MongoDB 的集成使用 MongoDB 是一个流行的 NoSQL 数据库,以其灵活的数据模型和强大的查询功能而闻名。Python 3 作为一种广泛使用的编程语言,与 MongoDB 的集成变得日益重要。本文将介绍如何在 Python 3 环境中集成和使用 MongoDBÿ…...
MperReduce学习笔记下
自定义InputFormat合并小文件 案例需求 无论hdfs还是mapreduce,对于小文件都有损效率,实践中,又难免面临处理大量小文件的场景,此时,就需要有相应解决方案。 案例分析 小文件的优化无非以下几种方式: …...
react + antd desgin 使用form功能时upload,radio,checkbox不能回显的问题
最近使用react开发 遇到form回显的问题 ,处理upload回显的问题,提示 react-refresh:160 Warning: [antd: Upload] value is not a valid prop, do you mean fileList? 查看文档后,在form.item 组件下有一个特殊属性 valuePropName 子节点的值…...
【NLP修炼系列之Bert】Bert多分类多标签文本分类实战(附源码下载)
引言 今天我们就要用Bert做项目实战,实现文本多分类任务和我在实际公司业务中的多标签文本分类任务。通过本篇文章,可以让想实际入手Bert的NLP学习者迅速上手Bert实战项目。 1 项目介绍 本文是Bert文本多分类和多标签文本分类实战,其中多分…...
OpenSSL 自建CA 以及颁发证书(网站部署https双向认证)
前言 1、前面写过一篇 阿里云免费ssl证书申请与部署,大家可以去看下 2、建议大家看完本篇博客,可以再去了解 openssel 命令 openssl系列,写的很详细 一、openssl 安装说明 1、这部分就不再说了,我使用centos7.9,是自…...
YOLOv11改进,YOLOv11添加U-Netv2分割网络中SDI信息融合模块,助力小目标检测
摘要 理论介绍 SDI模块的架构: 平滑卷积(SmoothConv):用于平滑特征图,帮助减少噪声并使得特征更加稳定。Hadamard积:用于在特征图中进行逐元素相乘(点乘),以加强语义信息和细节信息的融合。通道注意力(ChannelAttention):利用通道注意力机制来自动关注重要的特征通…...
flex布局 flex-end为什么overflow无法滚动及解决方法
flex-end为什么overflow无法滚动及解决方法 在使用Flexbox布局时,我们经常使用justify-content和align-items属性来定位子元素。其中,align-items属性用于控制子元素在交叉轴上的位置,例如顶部对齐、底部对齐或居中对齐等。当我们将align-it…...
从ground_truth mask中获取图像的轮廓图
引言 在图像取证领域,主要分为检测和定位两个方面。检测就是判断一张图片是否为伪造图,定位与传统意义上的语义分割任务相近,就是定位伪造像素的区域。如果单纯使用语义分割网络训练,只能获得次优解,而像多任务学习那样…...
Java项目实战II基于微信小程序的旅游社交平台(开发文档+数据库+源码)
目录 一、前言 二、技术介绍 三、系统实现 四、核心代码 五、源码获取 全栈码农以及毕业设计实战开发,CSDN平台Java领域新星创作者,专注于大学生项目实战开发、讲解和毕业答疑辅导。 一、前言 随着移动互联网的迅猛发展,旅游已经成为人…...
开源即时通讯与闭源即时通讯该怎么选择,其优势是什么?
在选择即时通讯软件时,应根据企业的经营领域来选择适合自身需求的开源或闭源方案。不同领域对开源和闭源即时通讯的理念存在差异,因此总结两个点简要分析这两种选择,有助于做出更明智的决策。 一、开源与闭源的根本区别在于软件的源代码是否…...
【计算机网络】实验15:VLAN间通信的实现方法“单臂路由”
实验15 VLAN间通信的实现方法“单臂路由” 一、实验目的 加深对VLAN间通信的实现方法“单臂路由”的理解。 二、实验环境 Cisco Packet Tracer模拟器 三、实验过程 1.构建网络拓扑,并配置好主机的IP地址、子网掩码、默认网关,如图1,2所…...
数据库学习记录04
DDL【数据定义语言】 MySQL命名规则 数据库名不得超过30个字符,变量名限制为29个必须只能包含A-Z,a-z,0-9,_共63个字符不能在对象名的字符间留空格必须不能和用户定义的其他对象重名必须保证你的字段没有和保留字、数据库系统或常用方法冲突保持字段名和类型的一致…...
PDF文件打开之后不能打印,怎么解决?
正常的PDF文件是可以打印的,如果PDF文件打开之后发现文件不能打印,我们需要先查看一下自己的打印机是否能够正常运行,如果打印机是正常的,我们再查看一下,文件中的打印功能按钮是否是灰色的状态。 如果PDF中的大多数功…...
A* 算法 是什么?
A*(A-star)算法是一种启发式搜索算法,用于在图或网格中找到从起点到目标的最短路径。它被广泛用于路径规划问题,例如导航、游戏开发中的角色移动,以及机器人路径规划。 1. A 算法的基本概念* A* 算法结合了两种经典搜…...
ORM框架详解:为什么不直接写SQL?
想象一下,你正在开发一个小型的在线书店应用。你需要存储书籍信息、用户数据和订单记录。作为一个初学者,你可能会想:“我已经学会了SQL,为什么还要使用ORM框架呢?直接写SQL语句不是更简单、更直接吗?” 如…...
厘米级高精度RTK手持终端北斗卫星定位手持pda
RTK是一种测量技术叫“载波相位差分技术”,是实时处理两个测量站载波相位观测量的差分方法,将基准站采集的载波相位发给用户接收机,进行求差解算坐标,以此得到高精度坐标。随着技术的不断革新,GPS接收机也由原来只能用…...
Kafka-Connect源码分析
一、上下文 《Kafka-Connect自带示例》中我们尝试了零配置启动producer和consumer去生产和消费数据,那么它内部是如何实现的呢?下面我们从源码来揭开它神秘的面纱。 二、入口类有哪些? 从启动脚本(connect-standalone.sh&#…...
【STM32 Modbus编程】-作为主设备读取保持/输入寄存器
作为主设备读取保持/输入寄存器 文章目录 作为主设备读取保持/输入寄存器1、硬件准备与连接1.1 RS485模块介绍1.2 硬件配置与接线1.3 软件准备2、读保持寄存器2.1 主设备发送请求2.2 从设备响应请求2.3 主机接收数据3、读输入寄存器4、结果4.1 保持寄存器4.2 输入寄存器在前面的…...
Kubesphere上搭建redis集群
Kubesphere上搭建redis集群 版本:redis:6.2.3 1)挂载配置 redis.conf: cluster-enabled yes cluster-config-file nodes.conf cluster-node-timeout 5000 cluster-require-full-coverage no cluster-migration-barrier 1 appendonly yes …...
learn-(Uni-app)跨平台应用的框架
使用 Vue.js 开发所有前端应用的框架,开发者编写一份代码,可发布到iOS、Android、Web(包括微信小程序、百度小程序、支付宝小程序、字节跳动小程序、H5、App等)等多个平台。 跨平台:Uni-app 支持编译到iOS、Android、W…...
target_compile_definitions
这个接口给目标定义的宏,不能像C中定义的宏一样,尝试利用宏进行替换: cmake_minimum_required(VERSION 3.8) project(compile_definitions_pro)add_executable(main_exec src/main.cpp)set(SYSTEM_NAME "") if(CMAKE_SYSTEM_NAME S…...
浏览器同源策略、跨域、跨域请求,服务器处理没、跨域解决方案
目录 什么是同源策略什么是跨域发生跨域时,服务器有没有接到请求并处理响应:(两种情况) 如何解决跨域 什么是同源策略 概念: 同源策略是浏览器的一种安全机制,用于防止恶意网站对用户的敏感数据进行未经授…...
深入理解网络安全等级保护:保障信息安全的关键策略与实践
随着信息技术的飞速发展,网络安全问题日益凸显。为了应对这一挑战,网络安全等级保护制度应运而生,旨在确保不同等级的信息和信息系统的安全。本文将探讨网络安全等级保护的基本概念、重要性及其实践方法。 一、信息安全等级保护的基本概念 1…...
MySQL
InnoDB 引擎底层存储和缓存原理 到目前为止,MySQL 对于我们来说还是一个黑盒,我们只负责使用客户端发 送请求并等待服务器返回结果,表中的数据到底存到了哪里?以什么格式存放的? MySQL 是以什么方式来访问的这些数据&…...
新书速览|循序渐进Node.js企业级开发实践
《循序渐进Node.js企业级开发实践》 1 本书内容 《循序渐进Node.js企业级开发实践》结合作者多年一线开发实践,系统地介绍了Node.js技术栈及其在企业级开发中的应用。全书共分5部分,第1部分基础知识(第1~3章)…...
2024三掌柜赠书活动第三十五期:Redis 应用实例
目录 前言 Redis操作都会,却不知道怎么用? 关于《Redis 应用实例》 编辑推荐 内容简介 作者简介 图书目录 《Redis 应用实例》全书速览 拓展:Redis使用场景 实例1:缓存应用 场景描述 实现方法 具体代码示例 实例2&a…...
Android 第三方框架:RxJava:源码分析:观察者模式
文章目录 观察者模式RxJava中的观察者模式总结 观察者模式 RxJava中的观察者模式 以Observable、ObservableOnSubscribe、Observer为例 Observable是被观察者 负责发射事件或数据 Observer是观察器 负责对从被观察者中获取的数…...
开源模型应用落地-安全合规篇-用户输入价值观判断(四)
一、前言 在深度合规功能中,对用户输入内容的价值观判断具有重要意义。这一功能不仅仅是对信息合法性和合规性的简单审核,更是对信息背后隐含的伦理道德和社会责任的深刻洞察。通过对价值观的判断,系统能够识别可能引发不当影响或冲突的内容,从而为用户提供更安全、更和谐的…...