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

数据结构: 位图

位图

概念

用一个bit为来标识数据在不在

功能

  • 节省空间
  • 快速查找一个数在不在一个集合中
  • 排序 + 去重
  • 求两个集合的交集,并集
  • 操作系统中的磁盘标记

简单实现

1.设计思想:一个bit位标识一个数据, 使用char(8bit位)集合来模拟

2.预备工作:a.计算这个数在第几个char b.是这个char的第几个bit位

                第i个char: num/8   第j个bit位: num%8

3.操作:放数据, 删数据, 判断数据在不在

  • set   :将对应的bit位置为1 ~~> 标识数据存在        _bit[i]  |=    (1<<j)   
  • reset:将对应的bit位置为0 ~~>标识数据不存在     _bit[i]  &=   ~(1<<j) 
  • test  :查看该bit位是不是位1~~>查看数据在不在   _bit[i]  &=  (1<<j)

set的实现:让对应bit位置1,其它位不变. 让该位 | 上1  ,  其它位 | 上0 

rest的实现:让对应bit位置1,其它位不变. 让该位 & 上0, 其它位 & 上1 

test的实现:让对应位&上1

4.代码

namespace code
{template<size_t N>class bitset{public:bitset(){_bits.resize(N/8+1,0);}//将指定的位置为1void set(size_t x){int i = x / 8;int j = x % 8;_bits[i] |= (1 << j);}//将指定的位置为0void reset(size_t x){int i = x / 8;int j = x % 8;_bits[i] &= ~(1 << j);}//查看数字在不在bool test(size_t x){int i = x / 8;int j = x % 8;return _bits[i] & (1 << j);}private:vector<char> _bits;};
}

布隆过滤器

概念

用多个bit位标识数据在不在(可以映射非整型数据)

功能

布隆过滤器常用于缓存控制、拼写检查、恶意网址过滤等场景,能够快速且高效地过滤掉大部分不必要的元素

简单实现

1.复用位图

2.提供多个仿函数,将非整型数据转换为整型, 并映射到不同的位置

3.置为1:根据计算出的位置将其置为1  在不在:映射的多个位置都为1表示在

4.代码

	struct BKDRHash{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};struct APHash{size_t operator()(const string& s){size_t hash = 0;for (long i = 0; i < s.size(); i++){size_t ch = s[i];if ((i & 1) == 0){hash ^= ((hash << 7) ^ ch ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));}}return hash;}};struct DJBHash{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}};// N最多会插入key数据的个数template<size_t N,class K = string,class Hash1 = BKDRHash,class Hash2 = APHash,class Hash3 = DJBHash>class BloomFilter{public://根据hash函数计算出的位置,将其置为1void set(const K& key){size_t len = N * _X;size_t hash1 = Hash1()(key) % len;_bs.set(hash1);size_t hash2 = Hash2()(key) % len;_bs.set(hash2);size_t hash3 = Hash3()(key) % len;_bs.set(hash3);}//所有映射的位置都为1才表示在// 在      不准确的,存在误判// 不在    准确的bool test(const K& key){size_t len = N * _X;size_t hash1 = Hash1()(key) % len;if (!_bs.test(hash1)){return false;}size_t hash2 = Hash2()(key) % len;if (!_bs.test(hash2)){return false;}size_t hash3 = Hash3()(key) % len;if (!_bs.test(hash3)){return false;}return true;}private:static const size_t _X = 6;bitset<N* _X> _bs;};

相关文章:

数据结构: 位图

位图 概念 用一个bit为来标识数据在不在 功能 节省空间快速查找一个数在不在一个集合中排序 去重求两个集合的交集,并集操作系统中的磁盘标记 简单实现 1.设计思想:一个bit位标识一个数据, 使用char(8bit位)集合来模拟 2.预备工作:a.计算这个数在第几个char b.是这个ch…...

Nginx 反向代理负载均衡

Nginx 反向代理负载均衡 普通的负载均衡软件&#xff0c;如 LVS&#xff0c;其实现的功能只是对请求数据包的转发、传递&#xff0c;从负载均衡下的节点服务器来看&#xff0c;接收到的请求还是来自访问负载均衡器的客户端的真实用户&#xff1b;而反向代理就不一样了&#xf…...

SAP FIORI 初步了解

1、对网上存在的部分资料进行收集 一套适合 SAP UI5 开发人员循序渐进的学习教程 SAP Fiori 的学习路线指南 如何根据角色批量激活SAP Fiori服务 关于S/4和Fiori&#xff0c;你必须知道的10件事 SAP Fiori开发教程 SAP FIORI教程 面向ABAP开发人员&#xff0c;SAPUI5 Fiori开发…...

chrome浏览器记录不住网站登录状态,退出后再打开就需要重新登陆的解决办法

chrome浏览器记录不住网站登录状态&#xff0c;退出后再打开就需要重新登陆&#xff0c;比较繁琐。 解决办法&#xff1a; 1、chrome浏览器右上角三个竖的点&#xff0c;然后进入“设置”&#xff08;Settings&#xff09;&#xff0c;选择“隐私与安全”&#xff08;Privacy…...

Linux lpd命令教程:打印服务管理技巧全解析(附实例教程和注意事项)

Linux lpd命令介绍 lpd是Linux操作系统中的一个命令&#xff0c;全称为line printer daemon&#xff0c;其主要职责是管理和控制打印任务。lpd可以接收打印任务请求并将这些请求放入打印任务队列中。当打印机空闲时&#xff0c;lpd会自动将任务队列中的打印请求发送给打印机以…...

利用STM32和可控硅控制220V加热电路

利用STM32和可控硅控制220V加热电路 Chapter1 利用STM32和可控硅控制220V加热电路一、错误原理图二、正确原理图 Chapter2 可控硅驱动芯片MOC3081/3061Chapter3 一个MOC3061的可控硅触发电路的分析Chapter4 可控硅的两种触发方式&#xff1a;移相触发和过零触发1、过零触发2、移…...

在高并发场景下,缓存“雪崩”了怎么办

1. 缓存雪崩的常见原因 缓存“雪崩”是指&#xff0c;因为部分缓存节点不可用&#xff0c;而导致整个缓存系统&#xff08;甚至是整个服务系统&#xff09;不可用。缓存“雪崩”主要分为以下两种情况&#xff1a; 因缓存不支持 rehash 而导致的缓存“雪崩”缓存支持 rehash 时…...

本地git服务器的使用

Windows上使用&#xff1a; 首先要在windows开发机上生成密钥&#xff1a; 1.安装git&#xff0c;首先去git官网下载git&#xff0c;https://git-scm.com/downloads&#xff0c;下载.exe格式并安装。 2.从程序目录启动“Git Bash” 3.键入命令&#xff1a;ssh-keygen -t rsa -…...

Mybatis Java API - SqlSessionFactoryBuilder

在MyBatis中&#xff0c;用于与数据库进行交互的主要Java接口是SqlSession。通过这个接口&#xff0c;您可以执行命令、获取映射器并管理事务。稍后我们将更详细地讨论SqlSession本身&#xff0c;但首先我们必须学习如何获取SqlSession的实例。SqlSession是由SqlSessionFactory…...

【动态规划】 LCR 099. 最小路径和

LCR 099. 最小路径和 解题思路 采用动态规划的思路每次搜索都是向上或者向左进行搜索dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1) 返回的值。同时(i,j)到(i - 1,j - 1)有两种方法&#xff0c;所以一定存在重叠子问题设置备忘录Memo存储dp过程中所有…...

【51单片机系列】DS18B20温度传感器扩展实验之设计一个智能温控系统

本文是关于DS18B20温度传感器的一个扩展实验。 文章目录 一、相关元件介绍二、实验分析三、proteus原理图设计四、软件设计 本扩展实验实现的功能&#xff1a;利用DS18B20设计一个智能温度控制系统&#xff0c;具有温度上下限值设定。当温度高于上限值时&#xff0c;电机开启&a…...

2023年年度总结,一个小白的CSDN涨粉历程

前言 滚滚长江东逝水&#xff0c;一去不复返。 转眼间已到2024年节点&#xff0c;时间如滚滚长江水向东奔流不息&#xff0c;在长江消失之前&#xff0c;都不会停歇&#xff0c;也不会回头。人亦如此&#xff0c;不管是生活还是学习&#xff0c;都是不断往前走的过程&#xff…...

2023-12-17 LeetCode每日一题(使用最小花费爬楼梯)

2023-12-17每日一题 一、题目编号 746. 使用最小花费爬楼梯二、题目链接 点击跳转到题目位置 三、题目描述 给你一个整数数组 cost &#xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用&#xff0c;即可选择向上爬一个或者两个台阶。 你…...

《Webpack5 升级》- Vue2.x 组件库 Webpack3 升 5

前言 基于 Vue2.x 的项目和组件库开发于 2019 年 &#xff0c;那时对 Webpack 版本没有概念&#xff0c;项目和组件库的版本混乱…有的使用 v3&#xff0c;有的使用 v4… 对于现今 2023 年&#xff08;或 2024 年&#xff09;的整个生态环境是不够用的&#xff0c;无法使用较新…...

【7K⭐】Pot:一款开源免费支持跨平台划词翻译和OCR的软件

【7K⭐】Pot&#xff1a;一款开源免费支持跨平台划词翻译和OCR的软件 如果你经常需要阅读英文文档或者图片&#xff0c;你可能会遇到以下问题&#xff1a; 浏览器自带的翻译功能翻译效果不佳&#xff0c;无法对照原文&#xff0c;而且不能翻译图片中的文字翻译插件虽然支持多…...

navicat premium历史版本下载及更新navicat premium15 永久(使用)有效期

1、navicat premium介绍 Navicat Premium 是一套可创建多个连接的数据库开发工具&#xff0c;让你从单一应用程序中同时连接 MySQL、Redis、MariaDB、MongoDB、SQL Server、Oracle、PostgreSQL 和 SQLite 。它与 GaussDB 、OceanBase 数据库及 Amazon RDS、Amazon Aurora、Amaz…...

JAVA进化史: JDK8特性及说明

JDK 8&#xff08;Java Development Kit 8&#xff09;是Java平台的一个重大版本&#xff0c;于2014年3月发布。该版本引入了许多令人期待的新特性&#xff0c;其中一些改变了Java语言的面貌&#xff0c;提供了更丰富、灵活和现代的编程体验。以下是JDK 8的一些主要特性&#x…...

vue3基础知识一,安装及使用

一、安装vue3 需要安装node&#xff0c;然后在项目所在目录命令行执行以下代码。 npm create vuelatest 回车后需要配置以下内容。 二、安装所需的依赖包并运行 cd到项目目录&#xff0c;执行以下代码安装依赖包 npm i 运行项目 npm run dev 打开浏览器查看结果 ok&#…...

3D动态路障生成

3D动态路障生成 介绍设计实现1.路面创建2.空物体的创建3.Create.cs脚本创建 总结 介绍 上一篇文章介绍了Mathf.Lerp的底层实现原理&#xff0c;这里介绍一下跑酷类游戏的动态路障生成是如何实现的。 动态路障其实比较好生成&#xff0c;但是难点在哪里&#xff0c;如果都是平面…...

Node.js--》node环境配置及nvm和nvm-desktop安装教程

博主最近换了台新电脑&#xff0c;环境得从零开始配置&#xff0c;所以以下是博主从一台纯净机中配置环境&#xff0c;绝对的小白教程&#xff0c;大家第一次安装完全可以参考我的过程&#xff0c;闲话少说&#xff0c;直接开始&#xff01;&#xff01;&#xff01; 接下来介绍…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...