BitMap对数字去重+排序
2019-01-04 本文已影响7人
小幸运Q
https://www.cnblogs.com/yangjiannr/p/da-shu-ju-chu-libitmap.html
思想：
- 32位机器上，用对应的32bit位存储十进制的0-31个数，这就是Bit-map的基本思想。Bit-map算法利用这种思想处理大量数据的排序、查询以及去重。
Bitmap在用户群做交集和并集运算的时候也有极大的便利。
32位下最大规模： 2^32bit=2^29Byte=512MB
应用：快速排序:
- 优点：
运算效率高，不需要进行比较和移位；
占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。 - 缺点：
所有的数据不能重复。即不可对重复的数据进行排序和查找。
应用：快速去重
注：JAVA语言中1byte=8bit
image.png
但是对于更大规模的数据：（比如64位机器）就凉凉了。
64位下的最大规模： 2^64bit=2^61Byte=2048PB=2EB
这时候就需要Bloom过滤器了
