需求：在做图库稳定性测试时，需要将斯坦福大学的社区网络图数据集顶点的去重导入到图库中。
去重方法：:
①在PC有限资源中实现（通过byte位置映射方式）,效率中等，文本主要是讲该方法。
②通过Spark mapreduce实现，效率高，实现简单，但需要spark环境。
③通过Hadoop mapreduce实现，效率较高，实现简单，但需要hadoop环境。
④将数据导入到数据库中，创建唯一索引，效率极低。
⑤将大文件才分若干个小文件，在小文件内去重，再将2个或多个小文件合并去重，以此类推（当文件中非重复内容很庞大时依然不能解决问题）。
⑥……
数据集下载地址：http://snap.stanford.edu/data/com-Friendster.html ，数据集解压后大概30GB左右。

Java基础知识

容量关系

//EB(艾字节)、PB(拍字节)、TB(太字节)、GB(千兆字节)、MB(兆字节)、KB(千字节)、Byte(字节)、bit(比特)
1EB=1024PB
1PB=1024TB
1TB=1024GB      
1GB=1024MB
1MB=1024KB
1KB=1024Byte
1Byte=8bit

位运算符

参考文章Java位运算

分析与实现

到这里我们对数据的二进制操作有了初步的认识，一个Byte字节是占8个比特的，一个bit是由0和1两个取值，那么可以通过0和1来表示某个值是否存在(既0:不存在,1:存在)。我们知道一个int值是占32(4*8)个bit的，那现在只需要一个1bit就能标示该值，一个int整整减少了31bit空间。假设要对4个int进行去重原来需要4*4=16Byte=128bit，当需要对32亿个int进行去重时原来需要32亿*4=128亿Byte=1028亿bit≈11.92GB，通过Byte数组+01标识方式只需要(32亿-31亿)*4=4亿Byte=32亿bit≈372MB, 前者需要的空间成本和时间成本远远超出想象。详解如下：例如，已知有个array数组，数组内容是{6,9,29,9},在byte字节数组中表示如下图：

要对数组进行去重就需要将各个数组的数值映射到byte数组的某个bit位上，用0或1来表示该卡位上是否存在数据，这里面就涉及到两个重要的变量index和position，index表示bytes数组的某个字节的索引，position表示在某个字节的哪个卡位。公式：

index = n / 8;//等于 n >> 3。eg:6/8=0,表示6在bytes[0]字节上
postion = n % 8;//等于n & 0x07。eg:6%8=6,表示在第6个卡位上

无符号int

在Java语言中本身是不支持无符号整数（unsigned int）的，这里所说的无符号只是为了说明取值在[0-Integer.MAX_VALUE]的数值空间，因为该方式能更好的节约内存空间，如果你处理的数据没有负数，那么可以采用该方法。
完整代码:

/**
 * 无符号Int BitMap，int取值[0,2147483647]
 *
 * @author Jianbo.Peng
 * @date 2021/9/25 2:12 下午
 */
public class UnsignedIntBitMap {

    private final byte[] bytes;

    /**
     * 根据maxInt创建BitMap
     *
     * @param maxInt 需处理的整数最大值
     */
    public UnsignedIntBitMap(int maxInt) {
        //计算所需的空间大小，其中+1是为0预留的
        int spaceSize = calcByteSpace(maxInt) + 1;
        this.bytes = new byte[spaceSize];
    }

    /**
     * 赋值
     *
     * @param n
     */
    public void setBit(int n) {
        //计算bytes的index索引值
        int index = n / 8;
        //计算byte的卡位值
        int position = n % 8;

        //给index索引下的position卡位复制
        //eg:position = 6,那么1 << position == 64,所以卡位上值是1
        //bytes[index]       0    0    0    0    0    0    0    0
        //1 << position      0    1    0    0    0    0    0    0
        //|                  0    1    0    0    0    0    0    0
        //结果是1
        bytes[index] |= 1 << position;
    }

    /**
     * 判断是否存在
     *
     * @param n
     * @return
     */
    public boolean exist(int n) {
        //计算bytes的index索引值
        int index = n / 8;
        //计算byte的卡位值
        int position = n % 8;
        //判断index索引和position卡位上的值是不是为1
        return (bytes[index] & (1 << position)) != 0;
    }

    public boolean setBitNotExist(int n) {
        boolean exist = exist(n);
        if (exist) {
            return false;
        }
        setBit(n);

        return true;
    }

    /**
     * 重置
     *
     * @param n
     */
    public void reset(int n) {
        //计算bytes的index索引值
        int index = n / 8;
        //计算byte的卡位值
        int position = n % 8;

        //清空index索引和position卡位的数据
        //eg:position = 6,那么1 << position == 64
        //bytes[index]       0    1    0    0    0    0    0    0
        //~(1 << position)   1    0    1    1    1    1    1    1
        //&                  0    0    0    0    0    0    0    0
        //结果是0
        bytes[index] &= ~(1 << position);
    }

    /**
     * 根据需要去重的最大的int值进行计算需要开辟多大的空间
     *
     * @param maxInt 所需的byte数量
     * @return
     */
    public int calcByteSpace(int maxInt) {
        return maxInt / 8 + (maxInt % 8 > 0 ? 1 : 0);
    }

    public byte[] getBytes() {
        return bytes;
    }
}

测试程序:

/**
 * 简单的测试程序，主要是验证下代码没有问题
 */
@Test
public void testSimpleUnsignedIntBitMap() {
  int arraySize = 10;
  int maxIntVal = 5;
  int[] array = new int[arraySize];
  for (int i = 0; i < arraySize; i++) {
    array[i] = randomInt(maxIntVal);
  }
  System.out.println("原数组：" + Arrays.toString(array));
  UnsignedIntBitMap bitMap = new UnsignedIntBitMap(maxIntVal);
  List<Integer> endResults = new ArrayList<>();
  for (int val : array) {
    boolean b = bitMap.setBitNotExist(val);
    if (b) {
      endResults.add(val);
    }
  }
  System.out.println("处理后数组：" + endResults.toString());
}

/**
  * 复杂测试
  * @throws IOException
  */
@Test
public void testMagnitudeUnsignedIntBitMap() throws IOException {
  //com-friendster.all.cmty.txt文件大概30GB左右
  File file = new File("com-friendster.all.cmty.txt");
  LineIterator iterator = FileUtils.lineIterator(file, "UTF-8");

  File outFile = new File("target.txt");
  //临时缓存，达到一定阈值，保存到文件中
  List<String> cacheList = new ArrayList<>();
  int cacheSize = 1000;

  UnsignedIntBitMap bitMap = new UnsignedIntBitMap(Integer.MAX_VALUE);

  long startDate = System.currentTimeMillis();
  while (iterator.hasNext()) {
    String line = iterator.nextLine();
    if (!StringUtils.startsWith(line, "#")) {
      String item[] = line.split("\t");
      int num0 = Integer.parseInt(item[0]);
      int num1 = Integer.parseInt(item[1]);

      boolean b = bitMap.setBitNotExist(num0);
      if (b) {
        cacheList.add(item[0]);
      }
      b = bitMap.setBitNotExist(num1);
      if (b) {
        cacheList.add(item[1]);
      }

      if (cacheList.size() >= cacheSize) {
        FileUtils.writeLines(outFile, cacheList, true);
        cacheList.clear();
      }
    }
  }

  if (!cacheList.isEmpty()) {
    FileUtils.writeLines(outFile, cacheList, true);
    cacheList.clear();
  }
  System.out.println("处理耗时：" + (System.currentTimeMillis() - startDate));
}

private int randomInt(int maxIntVal) {
  return new Random().nextInt(maxIntVal + 1);
}

有符号int

有符号int相对无符号int所需的空间是乘2的，根据需求酌情选择。
完整代码：

/**
 * 有符号Int BitMap int取值[-2147483648,2147483647]
 *
 * @author Jianbo.Peng
 * @date 2021/9/25 2:12 下午
 */
public class IntBitMap {

    private final byte[] bytes;
    private int spaceSize;
    private int midSpaceSize;

    /**
     * 根据maxInt创建BitMap
     *
     * @param maxInt 需处理的整数最大值,maxInt应该是Math.abs(maxInt)
     */
    public IntBitMap(int maxInt) {
        //正数和负数空间要乘2,其中+1是为0预留的
        this.midSpaceSize = calcByteSpace(maxInt);
        this.spaceSize = this.midSpaceSize * 2 + 1;
        this.bytes = new byte[spaceSize];
    }

    /**
     * 赋值
     *
     * @param n
     */
    public void setBit(int n) {
        //计算bytes的index索引值
        int index = (n / 8);
        //将要正数负数各占一半空间
        index = (midSpaceSize + index);

        //计算byte的卡位值
        int position = n % 8;

        //给index索引下的position卡位复制
        //eg:position = 6,那么1 << position == 64,所以卡位上值是1
        //bytes[index]       0    0    0    0    0    0    0    0
        //1 << position      0    1    0    0    0    0    0    0
        //|                  0    1    0    0    0    0    0    0
        //结果是1
        bytes[index] |= 1 << position;
    }

    /**
     * 判断是否存在
     *
     * @param n
     * @return
     */
    public boolean exist(int n) {
        //计算bytes的index索引值
        int index = n / 8;
        //将要正数负数各占一半空间
        index = (midSpaceSize + index);
        //计算byte的卡位值
        int position = n % 8;
        //判断index索引和position卡位上的值是不是为1
        return (bytes[index] & (1 << position)) != 0;
    }

    public boolean setBitNotExist(int n) {
        boolean exist = exist(n);
        if (exist) {
            return false;
        }
        setBit(n);

        return true;
    }

    /**
     * 重置
     *
     * @param n
     */
    public void reset(int n) {
        //计算bytes的index索引值
        int index = n / 8;
        //将要正数负数各占一半空间
        index = (midSpaceSize + index);
        //计算byte的卡位值
        int position = n % 8;

        //清空index索引和position卡位的数据
        //eg:position = 6,那么1 << position == 64
        //bytes[index]       0    1    0    0    0    0    0    0
        //~(1 << position)   1    0    1    1    1    1    1    1
        //&                  0    0    0    0    0    0    0    0
        //结果是0
        bytes[index] &= ~(1 << position);
    }

    /**
     * 根据需要去重的最大的int值进行计算需要开辟多大的空间
     *
     * @param maxInt 所需的byte数量
     * @return
     */
    public int calcByteSpace(int maxInt) {
        return maxInt / 8 + (maxInt % 8 > 0 ? 1 : 0);
    }

    public byte[] getBytes() {
        return bytes;
    }
}

测试代码：
略，和无符号int测试程序类同

有符号long

略，和int类型类似

排序

根据上文分析与实现可以得出数据存在bytes数组中本来就是有序的，只需遍历整个bytes数组，将卡位上数值为1数据去除即可。
方法1：
直接遍历bytes数组取byte卡位上的值，如果是无符号还需要考虑负数问题(这里就不阐述了)

List<Integer> sortList = new ArrayList<>();
for (int index = 0; index < bitMap.getBytes().length; index++) {
  byte bVal = bitMap.getBytes()[index];
  for (int position = 0; position < 8; position++) {
    //boolean exist = ((bVal >> position) & 0x1) != 0; 与下一行代码等同
    boolean exist = (bVal & (1 << position)) != 0;
    if (exist) {
      int val = index * 8 + position % 8;
      sortList.add(val);
    }
  }
}
System.out.println("排序结果：" + sortList.toString());

方法2：
已知maxIntVal值，循环检测exist是否存在值

List<Integer> sortList = new ArrayList<>();
for (int i = 0; i <= maxIntVal; i++) {
  if (bitMap.exist(i)) {
    sortList.add(i);
  }
}
System.out.println("排序结果：" + sortList.toString());
最后修改：2022 年 09 月 04 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏