Bitmap讲解及其应用
程序员文章站
2024-01-30 18:08:58
...
百度百科:
来自于《编程珠玑》。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。
一个byte是占8个bit,如果每一个bit的值就是有或者没有,也就是二进制的0或者1,如果用bit的位置代表数组值有还是没有,那么0代表该数值没有出现过,1代表该数组值出现过。
优点:1.运算效率高,不许进行比较和移位;
2.占用内存少,比如N=10000000;只需占用内存为N/8=1250000Byte=1.25M。
缺点:所有的数据不能重复。即不可对重复的数据进行排序和查找。举例说明:
一个数组arr{2,5,4,3},使用bitmap算法:
byte[0]
我们遍历byte数组输出的就是按照从小到大的顺序;
bitmap算法适合处理大量连续数据的问题,可以大大的节省空间;