一无符号32位整数范围 0 ~4294967295 一共约42.9亿个可能数字刚好覆盖题目40亿。BitMap规则1个bit总数除以8字节除以1024kb再除以1024mb得出512兆运用位图只需要512mb内存即可存入压缩多倍二一个字节是八个比特位1 Byte 8 bit位图类似hash但是比hash利用率高原本40个字节现在只需要3个字节就能存这个数组1. 普通HashMap存数组 {1,3,7,4,12,16,19,13,22,18}HashMap 是存键值对key数字value标记存在。- 一个Integer对象本身开销很大对象头4字节int哪怕用基础类型的 HashMapInteger,Boolean- 还要哈希表的数组容量、链表/红黑树指针会有大量空间浪费还有哈希冲突 这里10个数字要几十甚至上百字节。普通int数组每个int4字节10个就是 10 ×4 40字节就是你刚才说的。2. BitMap位图不存数字本身bit的位置下标 数字bit的值只用0/1标记有没有。例子里最大数字是22只需要23个bit向上对齐到字节只要3字节24bit。空间直接压缩十几倍。✅ 但是BitMap不是万能的有硬性限制考试常考点BitMap适合数字范围不大、是整数- 如果数字很大比如数字是 1000000 那你得开辟100万bit的空间直接爆内存这时位图就废了得换回hash。- 如果数字是负数、字符串位图直接不能用。3. 和Hash的核心差异一句话- Hash存数据本身计算hash值找到桶能存很大的数但有额外空间开销、哈希冲突。- BitMap下标就是数据只用1bit标记存在与否极致省内存但依赖数字的范围不能太大三位图底层 byte[] 字节数组底层就是字节数组 byte[]每个 byte 1字节 8bit可以标记8个数字。拿图里例子数字 12公式1. 数组下标 index 数字 / 8 整数除法​2. byte内的bit位置 bitPos 数字 % 8 取模1啥意思 叫做 左移运算符1 n 把数字 1 的二进制整体向左移动 n 位右边空出来的位置补01 的二进制1个字节来看 00000001举例1. 1 0 左移0位 → 00000001 十进制1​2. 1 1 左移1位 → 00000010 十进制2​3. 1 2 左移2位 → 00000100 十进制4​4. 1 4 左移4位 → 00010000 十进制16规律1 n 等价于 2^n- 13 2^3 8​- 15 2^5 32在位图里是干嘛的1 bitIndex 专门用来制造掩码生成一个二进制数只有第 bitIndex 位是1剩下全部是0比如 bitIndex2 12 → 00000100只有第2位是1其他都是0。然后配合- | 按位或把这一位设置成1set添加数字​- 按位与检查这一位是不是1get查询​- ~(1n) 取反之后 把这一位清成0remove删除int arrayIndex val / 8 ;四//扩容if(arrayIndex elem.length-1) {elem Arrays.copyOf(elem,arrayIndex1);}变量含义val 你要存的数字位图的第val位​- arrayIndex 这个位落在byte数组的第几个元素 val / 8 每1个byte存8bit​- elem 底层byte数组 elem.length 当前一共有多少个字节elem.length -1 数组最大合法下标数组下标从0开始五问题为什么普通内存放不下16G原始数组1、先算原始数据占用题目40亿个无符号整数一个int占4字节40亿 × 4 160亿字节 ≈{16GB}现在普通电脑/服务器内存情况- 个人电脑常见内存8G、16G、32G​- 就算机器物理内存是16G操作系统本身就要占一部分内存JVM虚拟机也要占用内存。 你没法把完整16GB的数据全部一次性加载进内存。比如你电脑物理内存一共16G系统开机就吃掉3~5G留给Java程序的堆内存可能就只有8G左右。直接加载16G的int数组直接OOM内存溢出。2、对比Bitmap方案用位图BitMap只需要 512MB很小轻轻松松放进内存。原理1bit标记一个数字是否存在不再存储数字本身。10亿个字节为什么是1g核心换算小技巧10亿个字节大概是0.9G可看做是1G10亿个比特位大概是119兆看做128兆