使用BitMap怎么实现大数据排序去重

今天就跟大家聊聊有关使用BitMap怎么实现大数据排序去重，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。1、问题 问题提出：M（如10亿）个int整数，只有其中N个数重复出现过，读取到内存中并将重复的整数删除。2、解决方案 问题分析：我们肯定会先想到在计算机内存中开辟M个int整型数据数组，来one bye one读取M个int类型数组， 然后在一一比对数值，最后将重复数据的去掉。当然这在处理小规模数据是可行的。我们考虑大数据的情况：例如在java语言下，对10亿个int类型数据排重。java中一个int类型在内存中占4byte。那么10亿个int类型数据共需要开辟10^9次方*4byte≈4GB的连续内存空间。以32位操作系统电脑为例，最大支持内存为4G，可用内存更是小于4G。所以上述方法在处理大数据时根本行不通。思维转化：既然我们不能为所有 int 类型的数据开辟 int 类型数组，那么可以采取更小的数据类型来读取缓存 int 类型数据。考虑到计算机内部处理的数据都是 01 序列的bit，那么我们是否可以用 1bit 来表示一个 int 类型数据。位映射的引出：使用较小的数据类型指代较大的数据类型。如上所说的问题，我们可以用1个 bit 来对应一个int 整数。假如对应的 int 类型的数据存在，就将其对应的 bit 赋值为1，否则，赋值为0（boolean类型）。java中 int 范围为 -2^31 到 2^31-1. 那么所有可能的数值组成的长度为2^32. 对应的 bit 长度也为 2^32. 那么可以用这样处理之后只需要开辟2^32 b 香港云主机it = 2^29 byte = 512M 大小的 内存空间 。显然，这样处理就能满足要求了，虽然对内存的消耗也不太小。问题解决方案：首先定义如下图的int – byte 映射关系，当然，映射关系可以自定义。但前提要保证你的数组上下标不能越界。但如上定义的bit[]数组显然在计算机中是不存在的，所我们需要将其转化为 java 中的一个基本数据类型存储。显然，byte[] 是最好的选择。将其转化为byte[] 数组方案：自定义的映射关系表，每个bit对应一个 int 数值，将 int 的最大值，最小值与数组的最大最小索引相对应。从上图可以看出来 int 数值与bit索引相差 2^31次方。当然，你也可以定义其他的映射关系，只是注意不要发生数组越界的情况。bit[]索引：由于最大值可能是2^32,故用long接收: long bitIndex = num + (1l
byte[]索引: int index = (int) (bitIndex / 8); ，在字节byte[index]中的具体位置： int innerIndex = (int) (bitIndex % 8);更新值： dataBytes[index] = (byte) (dataBytes[index] | (1
` import java.util.Random;/**问题：M（如10亿）个int整数，只有其中N个数重复出现过，读取到内存中并将重复的整数删除。
使用位映射来进行海量数据的去重排序，原先一个元素用一个int现在只用一个bit， 内存占比4*8bit:1bit=32:1
亦可用java语言提供的BitSet，不过其指定bit index的参数为int类型，因此在此例中将输入数转为bit index时对于较大的数会越界

*/ public class BigDataSort {private static final int CAPACITY = 1_000_000;// 数据容量public static void main(String[] args) {
}public static void testMyFullBitMap() { MyFullBitMap ms = new MyFullBitMap();
} }class MyFullBitMap { // 定义一个byte数组表示所有的int数据，一bit对应一个，共2^32b=2^29B=512MB private byte[] dataBytes = new byte[1
}`Bit-map应用之快速去重 　　2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。 　　首先，根据“内存空间不足以容纳这2.5亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这2.5亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间几十兆左右。 　　接下来的任务就是遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，,对应的转态位保持不变。 　　最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。 转自：https://www.cnblogs.com/yale/p/9307363.html看完上述内容，你们对使用BitMap怎么实现大数据排序去重有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注开发云行业资讯频道，感谢大家的支持。

相关推荐: 清软英泰对于机械产品生命周期管理标准与新技术运用

摘要 ： 近些年来 ， 我国机械产品的生产获得极大程度的提升 ， 其在促进我国经济发展过程中日渐彰显重要地位。这也让对机械产品的管理与新技术应用受到人们的关注。融入重要的生命周期理念 ， 进行相应的管理标准建设 ， 以及探索更好的新技术应用措施 ， 才能够从根…