从位图结构开始学内存的计算

今天发现从认识位图Bitmap结构可以很好梳理底层的计算机内存结构基础。那就先来认识内存的计算单位内存可以比喻成一张巨大的Excel 表格表格里可以划分不同的Sheet页方便区分不同功能类\区域类似 堆区栈区启动区命令区变量区自由申请区......开发者设计的程序使用内存的时候需要进到指定的区需要设计好在区内使用的边界大小这样才能保证程序和系统正常运行划分边界就需要认识存储单位。现代的操作系统、高级语言把这些申请步骤都封装好了程序运行的时候底层自动帮你做了所以感知不到知道就行。存储单位分为Bit、Byte、KB、MB、GB、......除了Bit到Byte是8进率其它的存储单位间都以 1024 作为进率;Bit (位) (b)计算机存储信息的最小单位也是计算机最基础的单位可以存储的值为 0 或 1。Byte (字节) (B)基本存储单位1 Byte 8 bits。KB (千字节) (Kilobyte)1 KB 1024 Bytes。MB (兆字节) (Megabyte)1 MB 1024 KB。GB (吉字节) (Gigabyte)1 GB 1024 MB。.......32位 和 64位计算机的区别我们说的 32 位和 64 位计算机指的是 CPU 每一次可以处理多少位的数据好基础的内存存储单位复习就到这里。位图的定义一种数据结构使用一串二进制位 (0/1) 来表示大量数据的存在状态以极节省内存来快速判断数据是否在集合中。简而言之它可以是图像像素点阵也可以是记录状态位序列的高效数据集合核心概念基本单位是位bit位图的核心是利用计算机最小的存储单位——位bit每个位只能是0或1。映射关系一个位代表一个特定的数据项。例如位图的第N个位bit可以表示整数N是否存在于集合中。状态表示通常用 1 表示“存在”或“真”0表示“不存在”或“假”。主要特点极度节省空间1个位只占1bit (1/8字节)相比于存储整个数字或字符串能大幅减少内存占用。高效操作支持快速的位运算AND, OR, XOR等可以实现集合的快速查找、交集、并集、差集等操作。适用场景海量用户签到状态、黑白名单、数据去重、数据库索引、布隆过滤器等。与图像位图的区别数据结构位图一种逻辑概念关注如何高效存储和操作数据状态。图像位图点阵图一种图像表示方式每个像素点由一个或多个位表示颜色和亮度用于显示图像。位图使用案例上图只用了 32位4字节 就表示了一个用户一个月的全部登录记录。记录方式为如果登录了系统那么对应天数的那个bit就设置为1否则为0。一个月恰好是连续的31天实践-40亿个QQ号在2G内存去重问题一台 2G 内存电脑要求处理 40 亿个无序10位的QQ号如何快速去重我们先看看存储进内存需要多少内存空间一个10位的QQ号1234567890需要34位来存储那么40亿个就是34 * 40亿 136000000000Bits;136000000000 / (8 * 1024*1024*1024) ≈ 16 (GB);16G数据是装不进2G内存的。所以想进内存在开始计算的方案都行不通。考虑其他办法吧。方案二以QQ号9076072220为例我们可以按照以下步骤将其放入位图中:确定位置找到对应的位图位置。对于QQ号9076072220我们将其作为索引9076072220设置位将该位置设置为1表示该QQ号存在。通过这种方式将所有QQ号放入位图后所有值为1的位置表示存在不为1的位置表示不存在。对于相同的QQ号只需设置一次1因此可以有效地完成去重。然后计算需要多少内存空间10位QQ最大是9999999999 - 1000000000 8999999999 个;因为0-999999999 是非10位QQ号不在本次计算内所以去掉。所以8999999999 * 1bit(标记) 8999999999 bits;40亿 * 1 bit(标记) 40亿 bits 40亿 bits 8999999999 bits 12999999999 bits;12999999999 / (8 * 1024 * 1024 * 2024 ) ≈ 0.7 GB哇只需要不到1G的空间就可以搞定相比而言很省空间了。时间复杂度O(nj)n 为范围(上图的32位)j为记录数上图的34位都是常数所以O(1)非常快。