海量数据去重的哈希与布尔过滤器

目录

散列表

hash与平衡二叉树比较:

散列表组成:

hash函数

作用:

怎么选择hash:

选择标准:

常用hash:

hash的操作:

hash冲突

产生原因

如何描述冲突程度:

解决冲突:

在合理范围内:used < size:

不在合理范围内(used > size or used < 0.1size()):

stl中散列表的实现

哪些stl使用了散列表?

stl(unordered_*)散列表实现

布隆过滤器:

 背景:

构成:

怎么操作的

要点:

应用分析:

由n和p确定m和k:

变量关系:

确定哈希函数

分布式一致的哈希:

解决的问题:分布式缓存中扩容的问题

怎么解决的

目的

避免缓存失效:

保证数据均衡:


hash的应用:

什么时候使用哈希呢?

一般情况下是判断某字符串在大量的数据中是否存在,比如

散列表

hash与平衡二叉树比较:

二叉树通过比较,结构有序,提升搜索效率

key与节点存储位置的映射古关系(无序),通过空间去换取时间

散列表组成:

hash函数(将key映射到某一个地址)

数组

hash(key) % size = index

散列表(Hash Table)是一种基于键值对的数据结构,它通过哈希函数将键('key')映射到数组中的特定索引位置,实现快速存储和查找。具体组成和原理如下:

 1. 哈希函数(Hash Function)

   - 作用:将输入的键(如字符串、整数等)转换成一个整数地址,称为哈希值。哈希值决定了这个键在数组中的存储位置。
   - 映射过程:哈希函数会对键进行某种算法处理,使得不同的键尽可能产生不同的哈希值。例如,把一个字符串键映射到一个整数值。
   
 2. 数组

   - 作用:哈希表的核心存储空间。数组的每一个元素称为“桶”(Bucket),每个桶可以存储一个或多个值。
   - 大小(size):数组的长度是有限的,因此选择合适的大小(即 'size')有助于减少哈希冲突(当不同的键映射到相同的索引)。
   - 存储方式:哈希表利用数组的索引位置来存储键值对,这样可以在 O(1) 时间内完成查找。

 3. 哈希函数映射过程

   - 通过 'hash(key) % size = index' 计算出键值对应该存放在数组中的位置。具体步骤为:
     - 首先,将 'key' 通过哈希函数转化为一个哈希值(整数)'hash(key)'。
     - 然后,用 'hash(key) % size' 对哈希值进行取模操作,以确保结果在数组范围内('[0, size-1]')。
     - 最后,得到一个数组索引 'index',将键值对存储到这个位置。
   
   例如:
   '''cpp
   int hashIndex = hash(key) % size;
   '''

 示例

假设我们有一个哈希表大小为 '10' 的数组,用来存储字符串键:

1. 选择一个哈希函数 'hash(key)',将字符串转化为整数。
2. 对数组大小 'size = 10' 进行取模:'hash(key) % 10',以确定键存储的索引。
3. 若 'key = "apple"',经过哈希函数得到整数 'hash("apple") = 38',则 '38 % 10 = 8',所以将 '"apple"' 存储在数组第 '8' 个位置上。

这样,哈希表实现了通过键快速定位值的功能。

hash函数

作用:

映射关系

怎么选择hash:
选择标准:

        计算速度快

        强随机分布性

常用hash:

        murmurhash2,cityhash,siphash

        

hash的操作:

插入和删除

本质上都是先靠搜索找到位置,然后进行相关操作

hash冲突
产生原因

哈希冲突产生的原因是不同的键经过哈希函数映射后得到了相同的数组索引,从而导致多个键试图存储到相同的位置。

如何描述冲突程度:

使用负载因子:

解决冲突:
在合理范围内:used < size:

1.链表法

2.开放寻址法:

不在合理范围内(used > size or used < 0.1size()):

当used > size():扩容 (一般情况下是翻倍扩容)

当used < 0.1 size():缩容

之后要rehash(因为size改变了)

stl中散列表的实现
哪些stl使用了散列表?

stl(unordered_*)散列表实现

为了实现迭代器,将后面具体节点串成一个单链表

布隆过滤器:

 背景:

内存有限,只想确定某个key存不存在,不想知道具体内容

       

构成:

位图 和 n个hash函数

怎么操作的

(hash(key) & bit_size = index):

查询和插入的操作是一样的

布隆过滤器只能确定某个key是否不存在,但是是否一定存在不能证明。

不支持删除操作的原因:

       在位图中每次槽位只有两种状态(0 or 1),一个槽位被设置位1状态,但不确定它被设置了多少次,也不知道被多少个key哈希映射而来以及是被具体哪个hash函数映射而来。
 

要点:

确定一个key一定不存在,可控假阳率确定存在

不能删除

根据n和p算出m和k

应用分析:

由n和p确定m和k:

https://hur.st/bloomfilter

变量关系:

为什么是哈希函数中,经常对31进行操作

当k为31,假阳率(冲突概率)最低

确定哈希函数

只用2GB内存在20亿个整数中找到出现次数最多的数

k 整数(4个字节)               

v 出现次数                       

用散列表来解决,同时用4个字节来(unit32)来存储数据,因为4个字节可表示21亿多个数字>20亿

现在一组kv要8字节,20亿组要16GB内存

所以对20亿个整数拆分成若干等份

把20亿个整数丶大文件拆分到多个文件中

目的是把相同的整数放在一个文件中

使用哈希函数,哈希函数会生成64位的整数,一方面可以对文件数取余,另一方面可以应用到散列表中

在各个文件中找出出现次数最多的值再比较就可以确定答案

分布式一致的哈希:

解决的问题:
分布式缓存中扩容的问题

(分布式缓存:缓存存储怎么优雅的扩容)

怎么解决的

固定算法

哈希偏移

增加虚拟节点:

解决了哈希偏移和是哈希迁移数据量变少

目的
避免缓存失效:

固定算法

数据迁移

保证数据均衡:

虚拟节点

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/14498.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

快速掌握——python类 封装[私有属性方法]、继承【python进阶】(内附代码)

1.类的定义 与 实例化对象 在python中使用class关键字创建一个类。 举例子 class Stu(object):id 1001name 张三def __init__(self):passdef fun1(self):pass# 实例化对象 s1 Stu() s2 Stu() print(s1.name) print(s2.name) 第一个方法 __init__是一种特殊的方法&#x…

PO 证书链

提到服务器间证书交换会不会头大,这两天遇到一个B2B接口的通讯证书问题,借机涨姿势,分享之 通常服务器之间通讯证书使用有两种方式: 如果不是生产机,可以简单的使用自签名证书,自签名证书就是下面这两个信息相同,都是自己,工具这里就不介绍了,多的是。双方互换证书,你…

HarmonyOS App 购物助手工具的开发与设计

文章目录 摘要引言功能需求分析技术方案与设计架构设计技术选型 代码示例Demo数据抓取模块数据存储模块历史价格查询和数据可视化模块完整界面布局和调用示例代码详解 QA环节总结参考资料 摘要 随着促销活动的增多&#xff0c;用户面临真假折扣的困惑&#xff0c;特别是在一些…

MPTCP协议

介绍 多路径TCP或 MPTCP协议是标准的扩展传输控制协议并在中进行了描述 RFC 8684号文件它允许设备同时使用多个接口通过单个MPTCP连接发送和接收TCP数据包。MPTCP可以聚合多个接口的带宽&#xff0c;也可以选择延迟最低的接口。它还允许在一条路径断开时进行故障切换&#xff…

1. 初始认识 Spring Cloud

1. 初始认识 Spring Cloud 文章目录 1. 初始认识 Spring Cloud前言2. Spring Cloud 基本介绍3. 系统架构的演变过程3.1 单机架构3.2 动静分离架构&#xff1a;静态缓存 文件存储3.3 分布式架构&#xff1a;业务拆分 负载均衡3.4 微服务架构&#xff1a;使用 Spring Cloud 4. …

网络学习第四篇

引言&#xff1a; 我们在第三篇的时候出现了错误&#xff0c;我们要就行排错&#xff0c;那么我们要知道一下怎么配置静态路由实现ping通&#xff0c;这样子我们才知道下一跳到底是什么&#xff0c;为什么这样子做。 实验目的 理解和掌握静态路由的基本概念和配置方法。 实…

【rf】robotframework自动化测试环境搭建

robotframework自动化测试环境搭建 前言&#xff1a; 1、在2019年之前&#xff0c;robotframework-ride的版本一直是1.5.2.1&#xff0c;是2016年1月份的版本&#xff0c;只能安装在python2.7的环境上&#xff0c;导致如果想同时使用robotframework做测试且又需要python3环境…

opencv入门学习总结

opencv学习总结 不多bb&#xff0c;直接上代码&#xff01;&#xff01;&#xff01; 案例一&#xff1a; import cv2 # 返回当前安装的 OpenCV 库的版本信息 并且是字符串格式 print(cv2.getVersionString()) """ 作用&#xff1a;它可以读取不同格式的图像文…

《DiffusionDet: Diffusion Model for Object Detection》ICCV2023

摘要 本文提出了一种新的框架DiffusionDet&#xff0c;它将目标检测任务表述为从带噪声的边界框到目标边界框的去噪扩散过程&#xff08;如图一所示&#xff09;。在训练阶段&#xff0c;目标边界框逐渐扩散到随机分布&#xff0c;模型学习逆转这一加噪过程。在推理阶段&#…

加深深度学习矩阵计算理解--用人类直觉 走进线性代数(非应试)

文章目录 前言一、向量二、线性组合、空间与基三、矩阵和线性变换四、矩阵乘法与线性变化复合1、矩阵乘法代表线性变换的复合2、实例说明 五、三维空间的线性变换1、基本性质2、直觉理解3、矩阵表示 六、行列式一、行列式的定义2、行列式在空间中的抽象理解 七、逆矩阵 列空间秩…

AIGC学习笔记(5)——AI大模型开发工程师

文章目录 AI大模型开发工程师004 垂直领域的智能在线搜索平台1 智能在线搜索平台需求分析大模型不够“聪明”增强大模型的方式需求分析2 智能在线搜索平台方案设计方案设计技术选型大模型版本GLM-4大模型注册使用Google Cloud平台注册创建可编程的搜索引擎3 智能在线搜索平台代…

【C++滑动窗口】1234. 替换子串得到平衡字符串|1877

本文涉及的基础知识点 C算法&#xff1a;滑动窗口及双指针总结 LeetCode1234. 替换子串得到平衡字符串 有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符&#xff0c;且长度为 n 的字符串。 假如在该字符串中&#xff0c;这四个字符都恰好出现 n/4 次&#xff0c;那么它就…

源码分享-Springboot+Vue大学生社团活动平台附源码,sql文件,配套论文

源码获取: 复制链接到浏览器打开即可领取 夸克网盘领取链接&#xff1a;https://pan.quark.cn/s/187d2ca0e3ec 百度网盘领取链接&#xff1a;https://pan.baidu.com/s/1apbO6k1cEqFXV-USf0I2IA?pwdccaj 提取码: ccaj 1.1课题背景及意义 随着现代网络技术发展&#xff0…

南山前海13元一份的猪脚饭

​今天没有带饭&#xff0c;中午打算去中国国有资本资本风投大厦的工地餐点吃个打工餐。 ​快到工地餐点就看到不少工友已经开始津津有味吃饭了哈。其实树下也有很多小鸟在觅食&#xff0c;可能是找一些剩饭吃的样子&#xff0c;大部分是麻雀为主。​ ​肚子有些饿&#xff0c;…

C++builder中的人工智能(29):如何在Windows项目中导入FANN库

这篇文章旨在使用由Steffen Nissen开发的FANN库实现人工神经网络。FANN库支持20多种编程语言&#xff0c;包括Delphi和C Builder。您可以在FANN的官方网站上找到完整信息和文档&#xff0c;并下载FANN的源文件。 步骤&#xff1a; 下载FANN库&#xff1a; 从Nissen的官方网站下…

Java开发人员学习ArkTs笔记(二)-函数与类

大家好&#xff0c;我是一名热爱Java开发的开发人员。目前&#xff0c;我正在学习ARKTS&#xff08;Advanced Java Knowledge and Technology Stack&#xff09;&#xff0c;并将不断输出我的学习笔记。我将在这里分享我学习ARKTS的过程和心得&#xff0c;希望能够为其他开发人…

maven环境搭建

maven基本知识 https://blog.csdn.net/qq_41187116/article/details/125955085?spm1001.2014.3001.5502 maven环境搭建 maven软件下载 不要去官网下&#xff0c;慢~ 直接相信清华大学吧&#xff1a; https://mirrors.tuna.tsinghua.edu.cn/apache/maven/maven-3/3.9.9/bin…

jmeter常用配置元件介绍总结之线程组

系列文章目录 安装jmeter jmeter常用配置元件介绍总结之线程组 1.线程组(用户)1.1线程组1.1.setUp线程组和tearDown线程组1.2.Open Model Thread Group(开放模型线程组)1.3.bzm - Arrivals Thread Group(到达线程组)1.4.jpgc - Ultimate Thread Group(终极线程组)1.5.jpgc - St…

八 Bean的生命周期

八、Bean的生命周期 8.1 什么是Bean的生命周期 Spring其实就是一个管理Bean对象的工厂。它负责对象的创建&#xff0c;对象的销毁等。 所谓的生命周期就是&#xff1a;对象从创建开始到最终销毁的整个过程。 什么时候创建Bean对象&#xff1f; 创建Bean对象的前后会调用什…

【入门篇】桃园结义【算法赛】——多语言版

题目跳转 python import os import sys# 请在此输入您的代码 print(3)C #include <stdio.h> #include <stdlib.h>int main(int argc, char *argv[]) {printf("%d",3);return 0; }C #include <iostream> using namespace std; int main() {// …