Daily Plan
更新: 5/3/2025 字数: 0 字 时长: 0 分钟
#todo
Daily Study
更新: 5/3/2025 字数: 0 字 时长: 0 分钟
场景题
#暑期实习 1g内存 40亿qq号（理解为 [0,2^32-1] 大小的整数 去重问题 参考：高效压缩位图RoaringBitmap的原理及使用 - 知乎 高位压缩图算法：将32位拆分为高16位和低16位两个部分（两个short）来处理。数据结构如下
text
short[] keys;
Container[] values;
int size;每个32位的整形，高16位会被作为key存储到short[] keys中，低16位则被看做value，存储到Container[] values中的某个Container中。keys和values通过下标一一对应。size则标示了当前包含的key-value pair的数量，即keys和values中有效数据的数量。 包含三种Container
- ArrayContainer：使用short[] content直接将低16位的值存起来。每个short有2个字节，因此总共会占2N个字节
- BitmapContainer： 根据位图原理，16位整形的数据需要65536个b来存，每个比特位代表一个数据，例如第5位为1代表有值为5的数。因此该容器大小为 2^16 b = 8kb
- RunContainer：利用了行程长度压缩算法。对于连续出现的数列，例如11,12,13,14记录为
11，3这样极端情况下只需要2个short即4个字节就可以存完低16位的数据。
三种容器的选择根据实际情况来定，当插入值容量超过 4096*2^16 , 容器会从Array变为Bitmap；当调用runOpimize()方法进行优化时，会比较Bitmap和RunContainer的大小来选择小的容器。
Daily Problem
更新: 5/3/2025 字数: 0 字 时长: 0 分钟