go数据结构和算法BitMap原理及实现示例

目录
  • 1. BitMap介绍
    • 如何判断数字在bit数组的位置
    • 设置数据到bit数组
    • 从bit数组中清除数据
    • 数字是否在bit数组中
  • 2. Go语言位运算
    • 左移
    • 右移
    • 使用&^和位移运算来给某一位置0
  • 3. BitMap的Go语言实现
    • 定义
    • 创建BitMap结构
    • 将数据添加到BitMap
    • 从BitMap中删除数据
    • 判断BitMap中是否存在指定的数据

1. BitMap介绍

BitMap可以理解为通过一个bit数组来存储特定数据的一种数据结构。BitMap常用于对大量整形数据做去重和查询。
在这类查找中,我们可以通过map数据结构进行查找。但如果数据量比较大map数据结构将会大量占用内存。
BitMap用一个比特位来映射某个元素的状态,所以这种数据结构是非常节省存储空间的。

BitMap用途

  • BitMap用于数据去重
    BitMap可用于数据的快速查找,判重。
  • BitMap用于快速排序
    BitMap由于其本身的有序性和唯一性,可以实现快速排序:将其加入bitmap中,然后再遍历获取出来,从而得到排序的结果。

如何判断数字在bit数组的位置

在后面的代码中,我们使用[]byte来存储bit数据,由于一个byte有8个二进制位。因此:

  • 数字/8=数字在字节数组中的位置。
  • 数字%8=数字在当前字节中的位置。
    例如:数字10,
  • 10/8=1,即数字10对应的字节数组的位置为:1
  • 10%8=2,即数字10对应的当前字节的位置为:2

设置数据到bit数组

  • num/8得到数字在字节数组中的位置 => row
  • num%8得到数字在当前字节中的位置 => col
  • 将1左移col位,然后和以前的数据做|运算,这样就可以将col位置的bit替换成1了。

从bit数组中清除数据

  • num/8得到数字在字节数组中的位置 => row
  • num%8得到数字在当前字节中的位置 => col
  • 将1左移col位,然后对取反,再与当前值做&,这样就可以将col位置的bit替换成0了。

数字是否在bit数组中

  • num/8得到数字在字节数组中的位置 => row
  • num%8得到数字在当前字节中的位置 => col
  • 将1左移col位,然后和以前的数据做&运算,若该字节的值!=0,则说明该位置是1,则数据在bit数组中,否则数据不在bit数组中。

2. Go语言位运算

在Go语言中支持以下几种操作位的方式:

  • & 按位与:两者全为1结果为1,否则结果为0
  • | 按位或:两者有一个为1结果为1,否则结果为0
  • ^ 按位异或:两者不同结果为1,否则结果为0
  • &^ 按位与非:是"与"和"非"操作符的简写形式
  • << 按位左移:
  • >> 按位右移:

左移

将二进制向左移动,右边空出的位用0填补,高位左移溢出则舍弃该高位。
由于每次移位数值会翻倍,所以通常用代替乘2操作。当然这是建立在移位没有溢出的情况。
例如:1<<3 相当于1×8=8,3<<4 相当于3×16=48

右移

将整数二进制向右移动,左边空出的位用0或者1填补。正数用0填补,负数用1填补。
负数在内存中的二进制最高位为符号位——使用1表示,所以为了保证移位之后符号位的正确性,所以需要在高位补1。
相对于左移来说,右移通常用来代替除2操作。
例如:24>>3 相当于24÷8=3

使用&^和位移运算来给某一位置0

这个操作符通常用于清空对应的标志位,例如 a = 0011 1010,如果想清空第二位,则可以这样操作:
a &^ 0000 0010 = 0011 1000

3. BitMap的Go语言实现

接下来我们给出BitMap的Go语言实现,目前代码已经上传到github中,下载地址

定义

首先给出BitMap结构的定义:

type BitMap struct {
    bits []byte
    vmax uint
}

创建BitMap结构

func NewBitMap(max_val ...uint) *BitMap {
    var max uint = 8192
    if len(max_val) > 0 && max_val[0] > 0 {
        max = max_val[0]
    }
    bm := &BitMap{}
    bm.vmax = max
    sz := (max + 7) / 8
    bm.bits = make([]byte, sz, sz)
    return bm
}

将数据添加到BitMap

func (bm *BitMap)Set(num uint) {
    if num > bm.vmax {
        bm.vmax += 1024
        if bm.vmax < num {
            bm.vmax = num
        }
        dd := int(num+7)/8 - len(bm.bits)
        if dd > 0 {
            tmp_arr := make([]byte, dd, dd)
            bm.bits = append(bm.bits, tmp_arr...)
        }
    }
    //将1左移num%8后,然后和以前的数据做|,这样就替换成1了
    bm.bits[num/8] |= 1 << (num%8)
}

从BitMap中删除数据

func (bm *BitMap)UnSet(num uint) {
    if num > bm.vmax {
        return
    }
    //&^:将1左移num%8后,然后进行与非运算,将运算符左边数据相异的位保留,相同位清零
    bm.bits[num/8] &^= 1 << (num%8)
}

判断BitMap中是否存在指定的数据

func (bm *BitMap)Check(num uint) bool {
    if num > bm.vmax {
        return false
    }
    //&:与运算符,两个都是1,结果为1
    return bm.bits[num/8] & (1 << (num%8)) != 0
}

以上就是go数据结构和算法BitMap原理及实现示例的详细内容,更多关于go数据结构算法BitMap的资料请关注我们其它相关文章!

(0)

相关推荐

  • Golang实现常见排序算法的示例代码

    目录 前言 五种基础排序算法对比 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 前言 现在的面试真的是越来越卷了,算法已经成为了面试过程中必不可少的一个环节,你如果想进稍微好一点的公司,「算法是必不可少的一个环节」.那么如何学习算法呢?很多同学的第一反应肯定是去letcode上刷题,首先我并不反对刷题的方式,但是对于一个没有专门学习过算法的同学来说,刷题大部分是没什么思路的,花一个多小时暴力破解一道题意义也不大,事后看看别人比较好的解法大概率也记不住,所以我觉得「专门针对算法进行一些简

  • golang数据结构之golang稀疏数组sparsearray详解

    目录 一.稀疏数组 1. 先看一个实际的需求 2. 基本介绍 3. 应用实例 一.稀疏数组 1. 先看一个实际的需求 编写的五子棋程序中,有存盘退出和续上盘的功能 分析按照原始的方式来的二维数组的问题 因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据 2. 基本介绍 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组. 稀疏数组的处理方法是: 1)记录数组一共有几行几列,有多少个不同的值 2)思想:把具有不同值的元素的行列及值记录在一个小规模的数组中,

  • golang高并发系统限流策略漏桶和令牌桶算法源码剖析

    目录 前言 漏桶算法 样例 源码实现 令牌桶算法 样例 源码剖析 Limit类型 Limiter结构体 Reservation结构体 Limiter消费token limiter归还Token 总结 前言 今天与大家聊一聊高并发系统中的限流技术,限流又称为流量控制,是指限制到达系统的并发请求数,当达到限制条件则可以拒绝请求,可以起到保护下游服务,防止服务过载等作用.常用的限流策略有漏桶算法.令牌桶算法.滑动窗口:下文主要与大家一起分析一下漏桶算法和令牌桶算法,滑动窗口就不在这里这介绍了.好啦,废

  • Go实现分布式唯一ID的生成之雪花算法

    目录 背景: 特性: 雪花算法: 分布式唯一ID的生成 背景: 在分布式架构下,唯一序列号生成是我们在设计一个尤其是数据库使用分库分表的时候会常见的一个问题 特性: 全局唯一,这是基本要求,不能出现重复数字类型,趋势递增,后面的ID必须比前面的大长度短,能够提高查询效率,这也是从MySQL数据库规范出发的,尤其是ID作为主键时**信息安全,**如果ID连续生成,势必会泄露业务信息,所以需要无规则不规则高可用低延时,ID生成快,能够扛住高并发,延时足够低不至于成为业务瓶颈. 雪花算法: ​ sno

  • 使用go实现常见的数据结构

    1 golang常见数据结构实现 1.1 链表 举单链表的例子,双向链表同理只是多了pre指针. 定义单链表结构: type LinkNode struct { Data int64 NextNode *LinkNode } 构造链表及打印链表: func main() { node := new(LinkNode) node.Data = 1 node1 := new(LinkNode) node1.Data = 2 node.NextNode = node1 // node1 链接到 nod

  • Go语言的数据结构转JSON

    目录 结构体转为 JSON 格式 接口转为 JSON 格式 Marshal() 函数的原型 总结 在日常工作中,除了需要从 JSON 转化为 Go 的数据结构.但往往相反的情况是:我们需要将数据以 JSON 字符串的形式发送到 Web 服务器.今天我们将学会如何从一个结构化数据编码为 JSON . Json(Javascript Object Nanotation)是一种数据交换格式,常用于前后端数据传输.任意一端将数据转换成json 字符串,另一端再将该字符串解析成相应的数据结构,如strin

  • go数据结构和算法BitMap原理及实现示例

    目录 1. BitMap介绍 如何判断数字在bit数组的位置 设置数据到bit数组 从bit数组中清除数据 数字是否在bit数组中 2. Go语言位运算 左移 右移 使用&^和位移运算来给某一位置0 3. BitMap的Go语言实现 定义 创建BitMap结构 将数据添加到BitMap 从BitMap中删除数据 判断BitMap中是否存在指定的数据 1. BitMap介绍 BitMap可以理解为通过一个bit数组来存储特定数据的一种数据结构.BitMap常用于对大量整形数据做去重和查询.在这类查

  • MySQL索引背后的数据结构及算法原理详解

    摘要 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题.特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等.为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论. 文章主要内容分为三个部分. 第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础. 第二部分结合MySQL数据库中My

  • JavaScript数据结构与算法之队列原理与用法实例详解

    本文实例讲述了JavaScript数据结构与算法之队列原理与用法.分享给大家供大家参考,具体如下: 队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素.队列用于存储按顺序排列的数据,先进先出,这点和栈不一样(后入先出).在栈中,最后入栈的元素反而被优先处理.我们现在可以把队列想象对我们去餐馆吃饭的情景,很多人排队吃饭,排在最前面的人先打饭.新来的人只能在后面排队.直到轮到他们为止. 一:对队列的操作 队列有2种主要的操作,向队尾中插入新元素enqueue()方法和删除队列中的队首的元

  • java 数据结构基本算法希尔排序

    C语言数据结构基本算法希尔排序 前言: 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序, 然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.当增量减到1时,进行直接插入排序后,排序完成. 实现代码: public class ShellSort { /** * 原理:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的 * 下标相差d.对每组

  • Python实现的数据结构与算法之快速排序详解

    本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • JavaScript中数据结构与算法(一):栈

    序 数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记录下来吧 git代码下载:https://github.com/JsAaron/data_structure.git 栈结构 特殊的列表,栈内的元素只能通过列表的一端访问,栈顶 后入先出(LIFO,last-in-first-out)的数据结构 javascript提供可操作的方法, 入栈 push,

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • 数据结构与算法 排序(冒泡,选择,插入)

    数据结构与算法 排序(冒泡,选择,插入) 1.冒泡排序 1.1算法 冒泡排序(buddle-sort)算法的运作如下:(从后往前) 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 1.2 实现 // // main.c // BubbleSort // // Created

  • Python实现希尔排序算法的原理与用法实例分析

    本文实例讲述了Python实现希尔排序算法的原理与用法.分享给大家供大家参考,具体如下: 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 希尔排序的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高

随机推荐