我们在开发中后台应用或者中间件的时候，会存储一些数据在内存中以加快访问速度。随着数据量的增加，除了可以放置于堆外，还可以通过实时压缩来缓解。今天就给大家介绍一种压缩整形数组的方式
数组指 long[] 或者 int[] 类型，主要用来存索引数据。当数据量变大时，首先想到的就是缩减每个数字占用的空间，因为我们都知道一个 long 类型是占 8 个字节，而 int 也是占用 4 个字节。就以正数而言，int 3 个字节以上表示 2^24 = 16M 即 1600 百万以上的数字，一般我们是用不到的，大多数情况下高位都是闲置着的，所以可以将高位去掉，只存储用到的那几个字节（见图1）。当然为了可以还原，我们需要记录这个数字到底使用了几位。这里有两种方式：一是借用几位来表示，就拿 long 来说，我们只需要借用 3 位就可以表示用到的字节数了，另一方面，2^60 以后已经是非常大的数了，几乎用不到，所以我们借用也不会产生额外的效果；另一种就是利用字节最高位表示还有剩余数据（见图2）。这样一来，我们就把 long 或者 int 数组压缩成了 byte 数组，里面所有用到的字节都是有表示意义的。
图1
图2
这样一样我们就可以顺利地将数字进行压缩与解压缩了，在传输场景下可以很好的解决空间问题，这都是常见的思路。但是如果我们需要压缩后的数组仍然具备下标访问的能力怎么办？之前每个数字都是固定长度，我们可以通过 [单个数字占用的字节数]*[下标] 很快地找到对应的地址，但是压缩过后每个数字占用的空间不是一样的，这种方式就失效了。如果我们要取下标为 200 的数据，那我们就得线性查找 200 次？那么时间复杂度就由 O(1) 下降为了 O(n)。有没有更好的办法呢？当然是有的。我们可以建立索引（图3），即：
- 将数字分为若干个桶，每个桶的大小可心调节
- 我们使用另一个数组，大小为桶的数量，存储每个桶所第一个数据所在的下标
- 在查找时我首先使用二分查找到对应的桶，再使用线性查找到对应的数据
图3
由于在桶内是线性查找，因此不会太大，一般是 1KB 或者 4 KB。这样一来，我们查找速度就可以大大提升，接近 O(logn)。使用这套方式，经测试，在 4 亿随机数据的情况占用的空间可以缩减 30% 左右，但这并不是终点。利用桶的性质，我们可以只在桶内第一个元素存原数字，后面的都存一个偏移量，因为当数据不会明显离散（即一会儿是十几，一会是几十亿那种），可以很好地缩减数据大小，比如两个数都占用了 3 个字节，存偏移量后，第二个数字就可以使用 1~2 个字节来表示了。当然如果你对数组本身的顺序没有要求的话，还可以先对数组进行排序，这种偏移量的效果就可以暴表了。最理想的情况下，可以压缩至原来的 30%。
测试压缩效果（未排序）
UPDATE:2021-06-20
这里还有优化空间，之前采用二分查找是因数我们采用定长的桶，每个桶存储的数字数量不定，但如果我们采用变长桶，让每个桶存储 N 个数，那么，便可以直接通过 “整除+求余” 的方式快速打到数所在的桶，查询效率进一步提升。
