Bitmap 的基本思想
Bitmap 的基本思想
Bitmap 的基本思想是将不同数据映射到特定 Bit 位上,用 Bit 位来记录 0 和 1 两种状态,0 表示数据不存在,1 表示数据存在。因为 Bitmap 是使用 Bit 进行数据记录,由此可以显著节省存储空间。Bitmap 的关键是确定 10 进制到 2 进制的关系映射,可以使用 int(32bit)或 long(64bit)进行映射,然后通过确定数据在对应数组中的下标,来完成数据到 Bit 数组的转换。
Bitmap 的优缺点
Bitmap 的优缺点
Bitmap 的优点体现在计算快、内存占用少。原因在于使用 Bit 为单位进行数据存储并建立映射关系,数据处理所占用计算机内存小,可以加快大量数据查询的时间,适合快速去重。Bitmap 的缺点主要体现在数据碰撞、无法对重复数据排序、因数据稀疏造成空间冗余。另外,Bitmap 只适用于密集的数据,例如需要存入的数据是(9998,2345,9)时,就需要建立一个 9999 长度的 Bitmap,但实际存入的只有三个数据。
三种不同的 Bitmap
三种不同的 Bitmap
RoaringBitmp
RoaringBitmp 又叫做压缩 Bitmp,简称 RBM,是基于 Bitmap 原理的位图压缩算法。RoaringBitmp 的本质是将 Bitmap 分为若干个小块,当小块中需要存储数据才会被使用。相较 Bitmp,占用内存更少,操作速度更快。
Roaring64NavigableMap
Roaring64NavigableMap 也是基于 Bitmap 的压缩算法,是将 Bitmap 拆分为高 32 位和低 32 位。其中,高 32 位代表索引,低 32 位会被存储到 RoaringBitmp 中。
Java BitSet
Java BitSet 是 Java 中的位图数据结构。Java BitSet 每个组件都存在一个 boolean 值,可以将 Bitset 的 bit 编入索引,进行测试、设置和清除。Java 中,使用 Bitset 可以对另外一个 Bitset 进行修改。
RoaringBitmp
RoaringBitmp 又叫做压缩 Bitmp,简称 RBM,是基于 Bitmap 原理的位图压缩算法。RoaringBitmp 的本质是将 Bitmap 分为若干个小块,当小块中需要存储数据才会被使用。相较 Bitmp,占用内存更少,操作速度更快。
Roaring64NavigableMap
Roaring64NavigableMap 也是基于 Bitmap 的压缩算法,是将 Bitmap 拆分为高 32 位和低 32 位。其中,高 32 位代表索引,低 32 位会被存储到 RoaringBitmp 中。
Java BitSet
Java BitSet 是 Java 中的位图数据结构。Java BitSet 每个组件都存在一个 boolean 值,可以将 Bitset 的 bit 编入索引,进行测试、设置和清除。Java 中,使用 Bitset 可以对另外一个 Bitset 进行修改。