一文读懂位图（Bitmap）：从数据结构到磁盘修复

前几天帮朋友处理一台旧笔记本想压缩C盘空间再分个区出来。图吧工具箱里的分区工具刚加载完磁盘直接弹出一行红字C盘bitmap中有标记为已使用的未用簇。朋友第一反应是问我这电脑是不是中毒了其实不是毒这个报错牵扯到的是NTFS文件系统里的$Bitmap元文件——一个藏在系统底层、平时装系统、分区、重启都见不到真容的家伙。“位图Bitmap”这个词有点意思它在计算机里其实有好几副面孔Java后端面试经常考的数据结构位图、Android开发天天要处理的图片Bitmap、Windows分区报错里的NTFS记账本$Bitmap、以及操作系统教科书里内存管理的页分配器位图。它们名字一样本质都是“用一张映射表去记录状态”但应用场景、操作姿势、坑点完全不是一回事。这篇就把这几个面孔掰开揉碎讲一遍文末还附一套针对“bitmap中有标记为已使用的未用簇”报错的完整修复流程有需要的可以直接抄作业。顺便说一句如果你搜“电位图怎么画”是为了化学里的电势图Latimer图、Frost图那和计算机的Bitmap是两个世界化学里那是表示不同氧化态之间电势关系的图别再被关键词带跑偏了。下面全部围绕计算机里的位图展开。1. 先看清本质Bitmap到底是“一串bit”还是“一张图”1.1 用“开关面板”理解位图位图最底层的本质不是图片而是一段连续的内存空间里面每个bit位只存0或1表达“是/否”“有/无”“空闲/占用”这类二值状态。它叫“图”是因为这串bit排列起来就像一张格子表每个格子记录一个编号对应的状态。你可以把它想象成一排开关面板每个开关对应一个编号按下去表示“这个编号已被占用”弹起来表示“空闲”。一个字节有8个bit能管8个开关。如果用一个boolean数组存同样的状态每个元素要占1字节位图直接把内存压缩到八分之一。数据量小的时候看不出差距一旦数据量上亿差距就是几十MB和几百GB的差别。数据库里的位图索引Bitmap Index也是这个思路给某个低基数列建索引这个列的每个取值都对应一串bitbit位记录“该行是否取这个值”。我在生产环境见过一个千万级别的订单状态表用位图索引做多条件组合统计响应时间从秒级掉到毫秒级原理就是多个位图做与、或、非运算计算机处理bit运算比扫描表快得多。1.2 位图和哈希表、布尔数组的取舍既然都是判断“某个元素是否存在”为什么不直接上HashSet我直接给一组实测感知更直观的对比以1亿个范围在0到1亿之间的整数做去重为例位图需要约100000000 / 8 12.5MB内存不管数据塞进来多满内存固定boolean[]约100MB比位图多花7倍内存但接口最简单HashSetInteger光Integer对象装箱哈希表扩容轻松上GB但能维护额外信息。方案内存占用(估算)支持计数支持字符串等复杂键实现复杂度位图12.5MB不支持不支持低boolean[]100MB不支持不支持极低HashSetInteger数GB级别可以可以低HashMapInteger,Integer数GB级别可以可以中所以结论很明确只关心“有没有”、数据范围可控、对内存敏感这三个条件同时满足位图是首选方案。但位图也不是万能的它天生不支持计数也不支持存字符串这类复杂键这时就得往哈希表或布隆过滤器方向考虑了。2. Java里的位图从BitSet到经典面试题2.1 Java原生BitSet的正确用法Java标准库早就内置了位图实现就是java.util.BitSet。它内部用一个long[]数组承载数据每个long是64位封装好了常见位运算。日常开发里多用在判定类场景比如用户签到记录、ID是否被消费过、增量同步的游标断点。[\begin{java} import java.util.BitSet;public class BitmapDemo { public static void main(String[] args) { // 假设有一批ID范围0~999999999 BitSet seen new BitSet(1_000_000_000); int[] ids {123456, 789012, 123456, 555555};for (int id : ids) { if (seen.get(id)) { System.out.println(id 是重复ID); } else { seen.set(id); } } System.out.println(123456 是否出现过: seen.get(123456)); System.out.println(当前已有记录数: seen.cardinality()); }}这里有个比较隐蔽的边界BitSet.set(int bitIndex)里的bitIndex是非负int所以理论上最多标记到2^31-1约21.5亿个位置对应内存约268MB。如果你要覆盖整个32位无符号整数域0到42.9亿原生BitSet就不够用了要么自己用long[]扩展要么拆成高位、低位两个BitSet。我见过不止一次有人拿BitSet硬扛海量ID跑到一半报NegativeArraySizeException或者IndexOutOfBoundsException查半天才发现是索引越界。 ### 2.2 面试强题40亿个整数怎么找不重复 这道题在Java后端面试里出现频率极高**40亿个无序int内存限制几百MB找出所有重复的数字**。思路就是位图。因为int的取值范围是-2147483648~2147483647一共约42.9亿个数用位图标记只需要512MB。但题目要求几百MB内存怎么办 常见解法是分桶把int范围按符号位或高16位分成若干桶每个桶里的数字范围缩小再对每个桶用位图判断逐个桶输出重复数据。桶的数量算好单桶位图控制在几十MB就能把峰值内存压下去。实际工作中虽然很少遇到这种裸数据量但位图“用空间换时间、分而治之”的思想到了海量日志系统、ID归因场景照样管用。 另一道衍生题是**位图排序**已知待排整数都在0~10000之间且不重复可以直接遍历原数组把数字对应的bit置1再从头扫一遍位图输出“值为1的下标”就完成了排序。复杂度是O(nrange)比快排更暴力但也更快前提是数据范围不能太离谱。 java public class BitmapSort { public static void sort(int[] arr, int maxVal) { BitSet bs new BitSet(maxVal 1); for (int num : arr) { bs.set(num); } int idx 0; for (int i 0; i maxVal; i) { if (bs.get(i)) { arr[idx] i; } } } }我看网上很多教程直接把这段丢出来没提醒一个关键坑位图排序只适合“不重复数据”。如果待排数据里有重复值置位只会保留一个排序后数据直接变少这属于数据丢失。2.3 负数、超大范围和稀疏场景的避坑方式用位图标记有符号整数最简单的处理是偏移映射把负数整体平移成正数。比如范围-1000~1000存num时下标记成num 1000查的时候再减回去。这个偏移量必须全局统一一旦某处忘了加查出来的数据全错。如果数据范围大得离谱比如要标记0到10^12之间的随机数位图需要约125GB内存显然不可行。这种情况退而求其次用布隆过滤器搞一个位数组每个元素通过多个哈希函数映射到多个位置全部位置是1就认为“可能存在”有一个位置是0就确定“不存在”。布隆过滤器适合允许一定误判率的场景比如爬虫URL去重、缓存穿透防护。它本质是位图加哈希的升级版代价是有误判收益是内存需求骤降。还有一个很多人踩过的性能坑位图很稀疏的时候BitSet.cardinality()内部要遍历所有非零long数据分布极其稀疏时它会很慢。我之前处理过一批ID只有几千个、但数值范围上亿的请求用BitSet做存在性判断没问题但频繁调用cardinality()统计数量性能明显不如维护一个独立的计数变量。3. 图像世界的Bitmap旋转到底转的是什么3.1 位图图像的本质是像素矩阵做Android开发或者图像处理的人一听到Bitmap脑子里浮现的往往是图片。这跟数据结构的位图完全是两回事图像里的Bitmap是一个二维像素数组每个像素存颜色信息比如常见的ARGB_8888格式一个像素占4字节——A透明、R红、G绿、B蓝各8位。以一张1080×1920的手机截图为例内存占用大约是1080 * 1920 * 4 8294400字节约7.9MB。这就是为什么很多手机App加载高清图稍不注意就会OOM一张原图动辄十几MB加上解码过程中的临时缓冲内存就绷不住了。位图图像跟矢量图的最大区别是位图放大后会马赛克因为像素点就那么多矢量图记录的是“怎么画一条线”的数学描述无限放大依然清晰。日常拍照、截图、Web图片基本都是位图Logo、图标这类对清晰度要求高的场景才优先用矢量图。3.2 Android里旋转Bitmap的三条路Android开发里旋转Bitmap是高频操作尤其处理相机照片。最省事的是用MatrixMatrix matrix new Matrix(); matrix.postRotate(90f); Bitmap rotated Bitmap.createBitmap(src, 0, 0, src.getWidth(), src.getHeight(), matrix, true);createBitmap最后一个参数filter旋转90度这种整数角度时建议传false传了true反而会引入滤波导致的轻微模糊旋转45度这类非直角角度时再考虑true。如果不想依赖Matrix或者要写跨平台图像处理代码手动像素映射也很简单。顺时针旋转90度的核心是目标图像的宽高互换每个像素的坐标做变换我习惯用“目标坐标反推源坐标”来写不容易错public static Bitmap rotate90(Bitmap src) { int srcW src.getWidth(); int srcH src.getHeight(); int dstW srcH; int dstH srcW; Bitmap dst Bitmap.createBitmap(dstW, dstH, src.getConfig()); int[] srcPixels new int[srcW * srcH]; int[] dstPixels new int[srcW * srcH]; src.getPixels(srcPixels, 0, srcW, 0, 0, srcW, srcH); for (int dy 0; dy dstH; dy) { for (int dx 0; dx dstW; dx) { // 顺时针90度目标(dx,dy) ← 源(srcH - 1 - dx, dy) int sx dy; int sy srcH - 1 - dx; dstPixels[dy * dstW dx] srcPixels[sy * srcW sx]; } } dst.setPixels(dstPixels, 0, dstW, 0, 0, dstW, dstH); return dst; }注意目标数组长度仍然是srcW * srcH但写入时用的步长是dstW也就是srcH。很多人这里写错出现图片“斜了”“花了”的诡异现象基本都是把宽高步长搞混了。3.3 旋转图片的四个经典坑第一个坑是OOM。createBitmap会重新分配一块与原图同等大小的内存如果原图引用不释放内存瞬间翻倍。处理方法通常是旋转完之后对不再使用的原图调用recycle()Android 3.0之后GC也能回收但主动释放更稳妥。第二个坑是EXIF方向。手机相机横屏拍出来的照片JPEG文件里会记录一个Orientation字段90/180/270加载成Bitmap时像素还是原始方向直接显示是“躺着的”。正确做法是用ExifInterface读取方向再通过Matrix做对应旋转int orientation new ExifInterface(path) .getAttributeInt(ExifInterface.TAG_ORIENTATION, ExifInterface.ORIENTATION_NORMAL); switch (orientation) { case ExifInterface.ORIENTATION_ROTATE_90: matrix.postRotate(90); break; case ExifInterface.ORIENTATION_ROTATE_180: matrix.postRotate(180); break; case ExifInterface.ORIENTATION_ROTATE_270: matrix.postRotate(270); break; }第三个坑是非90度旋转的透明三角区。旋转45度时原图的矩形外轮廓变成一个菱形四角没有像素填充createBitmap会补成透明色如果直接把结果写进文件或者贴到View上边缘会出现难看的透明缺口。这种场景要么扩大画布、填充背景色要么用Canvas裁剪别指望Matrix自己帮你处理。第四个坑是大图加载前先做采样。一张4000×3000的相机原图ARGB_8888解码出来要48MB旋转一次再翻倍。建议先用BitmapFactory.Options设置inSampleSize缩小采样比如inSampleSize2就把宽高各减半内存直接降到四分之一。做头像、缩略图这类场景基本都能接受。4. Windows磁盘上的$Bitmap分区报错“已使用的未用簇”怎么修4.1 $Bitmap是NTFS的“记账本”如果你在Windows上折腾过磁盘分区大概率见过“bitmap中有标记为已使用的未用簇”之类的提示尤其图吧工具箱这类工具在扫描磁盘时会直接红字警告。这个bitmap不是图片也不是内存数据它是NTFS文件系统里的一个隐藏元文件文件名叫$Bitmap。NTFS会把磁盘分成很多等长的“簇”cluster默认4KB一个簇。文件保存时占用若干连续或不连续的簇$Bitmap就用二进制位记录每个簇的状态0表示空闲1表示已占用。整个C盘几百GB的数据本质上都靠这个记账本标注“哪块地皮有人住、哪块是空地”。因为它是系统元文件普通资源管理器里根本看不到只有DiskGenius、bootice这类工具才能扫描到。分区工具在做缩容、扩容、移动簇之前必须先读取$Bitmap确认簇的真实状态。如果记账本本身记错了工具就不知道哪些簇能安全移动、哪些不能动强行操作轻则报错中断重则文件系统损坏。4.2 报错“bitmap中有标记为已使用的未用簇”是什么意思把报错翻译成人话$Bitmap里标记某个簇为“已使用”但文件系统扫描后却发现没有任何文件实际占用这个簇。就像一套民宿房的登记本写“有人住”开门一看里面空的。这种“账实不符”的状态很危险。产生原因最常见的就这么几种非正常关机或断电NTFS日志$LogFile没来得及回滚位图和真实文件分配表出现偏差蓝屏、死机后强制重启文件操作只完成了一半第三方分区工具调整过程中被中断比如电量耗尽、用户强退磁盘出现坏道或退化导致簇标记异常某些一键分区脚本或Ghost系统镜像恢复时留下的历史脏数据。出现这个报错后如果只是挂着不处理系统可能短期内还能正常用但后续一旦写入数据覆盖到那些“假占用”的簇就可能出现文件损坏、目录打不开、分区工具拒绝操作。尤其是你想继续分区——图吧工具箱这类工具会发现磁盘状态不一致直接拒绝执行这就是很多人问“不能分区怎么弄”的原因。4.3 完整修复流程照着做就行先给个最重要的建议修复之前先把重要数据备份出去。分区操作本来就有风险加上$Bitmap状态错误这个前提任何意外都可能升级成数据灾难。数据备份完再接下面的步骤。第一步不做任何分区操作先用Windows的chkdsk修复文件系统。如果你修的是C盘最好进入Windows PE环境操作因为系统盘正在使用时chkdsk只能排队到重启时执行体验很差。PE怎么启动都行微软官方启动盘工具或者你习惯的PE工具箱都可以。第二步进入PE后打开命令行执行chkdsk c: /f /r /b参数解释一下/f修复发现的错误/r定位坏扇区并恢复可读信息/b是NTFS专用参数会重新评估卷上的坏簇相当于把磁盘坏道信息也刷一遍。C盘如果是固态或大容量机械盘这步可能要跑几十分钟到几小时别中途断电或者直接关窗口跑完再看结果。第三步chkdsk跑完后重启回Windows重新打开图吧工具箱或分区工具扫描C盘。正常情况下“bitmap中有标记为已使用的未用簇”的红字会消失这时再正常分区、扩容就顺了。第四步如果chkdsk修完还是报错用DiskGenius这类工具在C盘上右键选择“检查错误”或“修复”功能让它扫描并重建异常的位图区域。注意操作选项看清楚再点别点成“格式化”。第五步以上都不行且你确实需要分区最稳妥的兜底方案是导出数据格式化C盘后重做系统。格式化会重建NTFS的$Bitmap等于是把账本整个换新的但代价是原系统环境和软件全没了。4.4 “不能分区”的几个排查方向如果你并不是因为bitmap报错而是分区工具点了半天没反应先按这几个方向排查当前磁盘有没有程序正在占用比如杀毒软件、索引服务、虚拟内存页面文件有没有其他分区工具或磁盘管理窗口还开着磁盘本身是否健康。有条件可以在PE下操作PE环境加载的驱动最少干扰最小。很多工具在Windows桌面下分区会提示“无法锁定磁盘”“需要重新启动才能继续”这都是因为系统进程占用了卷。遇到这种情况别硬来乖乖去PE。我之前遇到过一台Windows 10机器分区工具反复提示无法锁定进PE一把就成功了问题就出在后台一堆常驻进程锁住了卷。注意千万别拿“低格工具”去处理bitmap报错。低格是对磁盘物理扇区重新初始化对固态盘寿命有毁伤性影响而且压根解决不了文件系统层面的记账错误。分区问题就修文件系统物理层面没坏就不要上重刑。5. 操作系统里的页分配器与位图内存管理的基建5.1 用位图给物理内存“记账”操作系统的物理内存管理同样藏着一个位图。现代操作系统把物理内存切成固定大小的页Page通常一页4KB。物理内存4GB就有约100万个页。管理这些页的状态——空闲还是已分配——最朴素的做法就是维护一张位图每个bit对应一个物理页1表示已分配0表示空闲。算笔账心里就有底了4GB内存 / 4KB页大小 1048576个页位图只需要1048576 / 8 131072字节也就是128KB。也就是说管理4GB物理内存的状态信息只占128KB内存占比约0.003%。这就是为什么位图作为物理内存记账本在教科书里地位那么高便宜、直接、查询单个页的状态只要一次位运算。网上有个热词叫“页分配器与位图安装”其实就是内核启动早期做的事物理内存探测完成后内核会把整个物理内存的页状态初始化成一张位图然后把内核镜像本身、启动参数占用的内存区域、ACPI表等等保留区域对应的页标记成“已分配”剩下的页标记成“空闲”。这一步做完页分配器才算有了可以操作的地基。5.2 位图式分配算法的实现思路和代价一个基于位图的页分配器核心逻辑就两块分配时找到一段连续的空闲页把对应bit从0改为1释放时把对应bit从1改回0。下面是核心思路用C语言表达#define PAGE_NR (1024 * 1024) // 管理100多万个页 static unsigned int frame_map[PAGE_NR / 32]; // 位图数组每个unsigned int管32个页 static inline int test_bit(unsigned int nr) { unsigned int idx nr / 32; unsigned int offset nr % 32; return (frame_map[idx] offset) 1; } static inline void set_bit(unsigned int nr) { unsigned int idx nr / 32; unsigned int offset nr % 32; frame_map[idx] | (1u offset); } static inline void clear_bit(unsigned int nr) { unsigned int idx nr / 32; unsigned int offset nr % 32; frame_map[idx] ~(1u offset); } // 分配连续n页成功返回起始页号失败返回-1 int alloc_pages(int n) { for (int i 0; i PAGE_NR - n; i) { int j; for (j 0; j n; j) { if (test_bit(i j)) break; } if (j n) { for (j 0; j n; j) set_bit(i j); return i; } } return -1; } // 释放从start开始的连续n页 void free_pages(int start, int n) { for (int i 0; i n; i) clear_bit(start i); }这个实现是教科书级别的“首次适配”优点是代码极其简单状态查询快单个页分配释放都是O(1)缺点是分配较大连续块时要线性扫描位图内存快满时会明显变慢。更现实的系统比如Linux的伙伴系统Buddy System用的是按2的幂次组织的空闲链表配合位图辅助标记某些中间状态它比单纯位图更能应对碎片问题。如果你在做OS课设看到“页分配器与位图”这个题目一般就是让先实现这种位图式分配器跑几个进程分配的作业验证正确性然后再考虑要不要升级成伙伴系统。5.3 手写一个简易内存分配器要注意什么我建议有课设需求的同学走这套流程先定义页大小4KB和总页数分配器底层维护一个char* mem_pool指针和上面那张位图初始化时把前N页标记为已分配模拟“内核占用的内存”然后实现void* mem_alloc(int pages)和void mem_free(void* addr)两个接口。写代码时有几个经验值得记一下。一是位图操作必须加锁或原子指令多进程或多线程并发分配时两个执行流可能同时发现同一个空闲块不加保护会重复分配同一块内存这是所有手写分配器最容易出的并发bug。二是释放时要校验起始地址是否确实是分配记录的开始地址否则把中间一块解引用释放位图状态就彻底乱了。三是连续页分配在总内存较满时可能失败但此时零散的碎片页明明还有不少这时候要么做内存紧缩把空闲页搬到一起要么改用更高级的伙伴系统。还有个小细节很多课设代码里测试分配器习惯直接拿printf打印页号我测试时更建议写一个随机分配/释放的脚本循环几千次每次分配后用assert检查从分配器拿到的内存区间能正常读写且范围不重叠。这种压力测试比手工点几十次更能暴露问题。6. 四种“位图”的对比和选型建议6.1 一张表看清四种位图的差别把前面四类位图放一起看很直观维度数据结构位图图像BitmapNTFS $Bitmap内存页位图本质bit数组像素数组磁盘簇状态表物理页状态表最小单位1 bit 一个标记位1 像素 多个字节1 bit 一个簇1 bit 一个物理页常见操作set/get/位运算旋转/裁剪/压缩chkdsk修复分配/释放物理页典型问题去重/存在性判断OOM/方向错误分区报错碎片/并发内存开销结果集大小/8宽×高×字节数取决于卷大小和簇大小物理内存/页大小/8你会发现它们本质是同一个模型一个很长的数组数组每个位置记录某个“对象”的状态。只不过在数据结构里“对象”是数字ID在图像里是像素坐标在文件系统里是磁盘簇号在内存管理里是物理页号。6.2 什么时候该用位图什么时候别用我自己的判断标准很简单状态是二值的、对象数量大、整体范围可预估这三点都满足位图基本就是最优解。比如判断几亿个ID是否出现过、统计磁盘哪些块被占用、管理物理内存页是否空闲都非常契合。反之如果状态不止“是/否”比如要记录“这个ID出现过几次”或者“这个资源属于哪个进程”位图的bit位就不够用了硬要扩展可能得一个对象分配好几个bit或者维护多个位图还不如用哈希表或普通数组。另外如果对象范围极大但实际出现的数据极少位图的“空间固定”优势反而变成劣势比如范围是64位整数但总共只有几百个值位图直接炸出几EB空间这时候哈希表或者布隆过滤器才是合理方案。数据库里的位图索引也是同理适合低基数列枚举值就几十个不适合高基数主键。看到“位图”先别条件反射觉得高大上先算一下状态空间到底有多大、数据够不够稀疏再决定用不用。最后分享两条实际体会跟“位图”打了这些年交道我最大的感受是位图就是一张账本账本和真实状态一旦不一致后面所有操作都会踩雷。不管磁盘、内存还是你自己写的bit数组记账和实际永远要对得上。写代码时记住负数偏移、范围上限、释放时标记清零这些看起来是小细节真出事基本都是从这里开始。最后再给一个排查小技巧遇到“C盘bitmap中有标记为已使用的未用簇”这类报错别急着折腾分区工具也别动不动就重装系统先进PE跑一遍chkdsk c: /f /r /b。绝大部分记账错误在这个阶段就能被修正跑完后重启再打开图吧工具箱红字往往就没了。我处理过的机器里这台旧笔记本就是这么救回来的分区照常进行数据一点没丢。