如何在4G内存中重新排序20亿个数字：快来尝试BitMap

作者是知道代码的叔叔（CodeDaShu），有一个广为流传的采访问题：给您一个4G内存机器，一组20亿无序正整数，如何快速确定这组数字中是否存在正整数N在？还是如何快速对这组数据进行排序？让我们首先计算20亿个整数将占用多少内存空间。 Java的int类型占用4个字节，那么转换为G的20亿* 4约为7.5G，大于问题中的4G内存限制，不能立即使用。
定期将数据放入内存；此时，一些合作伙伴会说：“将数据放在磁盘上，然后将数据批量读取到内存中以进行查询”，但是这种方法会导致多个磁盘IO，并且仅是为了解决第一个搜索问题，没有办法排序。 01 BitMap的概念BitMap可以很好地解决这个问题。
它使用位来标记与元素相对应的值，而Key为元素。例如，我们初始化一个类型为bit和length 8的数组。
下标0-7，数组中的内容1表示存在，0表示不存在，则：00000001是下标为0的位置，并且对应的值为1，则表示0；否则，则表示0。相同的原因：00000010表示1； 00000100表示​​2; 00001000代表3; ... 10000000代表7;如果一组数据{2,3,4,7}放在同一数组中，则为10011100：如果存储在一个int数组中，则{2,3,4,7}仅需要4 * 4 * 8位存储数据，但是现在BitMap只需要8位就可以存储数据，大大节省了存储空间，重新排序后的排序变得非常简单。
如果以字节为单位实现，则仅需要1个字节（1个字节= 8位）。如果添加数字10，则1字节是不够的：02数据结构和初始化我们可以知道BitMap的容量取决于最大值，例如存储{2,3,4,7,10}：如果实现对于位数组（如果有），则需要10 +1的长度；如果使用字节数组实现，则需要10/8 + 1的长度；如果使用int数组实现，则/ 32 + 1长度需要10（1 int等于4个字节，等于32位）；在理解了这一点之后，可以确定一个简单的BitMap数据结构：公共类BitMap {// data private byte []＆amp; nbsp; bits; //最大值private int max_value; // Capacity private int的能力； / ** *初始化* @参数容量* /公共BitMap（int max_value）{this.max_value＆amp; nbsp; =＆amp; nbsp; max_value; // 1位存储8个数据，具有max_value最大值的数组需要max_value / 8 + 1个字节，除以8表示将右移3位。
＆amp; gt; 3）＆nbsp; +1；位=新字节[容量]； }} 03添加数据以添加数据，您需要快速定位元素在整个数组中的存储位置。这里有两个概念：索引号索引：将数据存储在整个数组中的位置。
位置编号position：数据在此下标元素中的位置；例如，将10存储在索引= 1，位置= 2（从0开始）中。在该位置可以计算：索引= N / 8位置= N％8在知道保存的位置10后，如何将对应位置的数据更改为1？您可以使用“按位或”手术。
将10加到BitMap的完整步骤如下：计算索引= 10/8 = 1；计算排名= 10％8 = 2;进行“位或”运算字节[1]和0000100的数据之间的运算，其中0000100是传递1向左移动2以获得。完整的代码如下：public void add（int num）{//其中整个数组的下标是存储的数据int index = num / 8; //此下标元素中的数据在哪里int position = num％8; bits [index] | ＝ 1＆amp; lt;} 04确定该数字是否存在在知道如何确定该数字的索引号和位置号之后，容易确定该数字是否存在。
使用“与”位直接执行操作，代码如下：public boolean contains（int num）{if（num＆amp; gt; max_value）{return false;} //在整个数组的下标中存储的数据int index = num / 8 ; //此下标元素int position中的数据在哪里=＆amp; nb＆amp; nbsp;％8; return（bits [index]＆amp; amp; amp; amp; amp; lt; 0;} 05测试让我们对其进行测试：public class BitMapTest {public static void main（String [] agrs）{BitMap bm = new BitMap（100） ; bm.add（1）; bm.add（12）; bm.add（14）; bm.add（51）; bm.add（71）; bm.add（100）; System.out。println（“ ; 12：“ +（bm.contains（12）？” exists“：”不存在“）））; System.out.println（” 13：“ +（bm.contains（13）？” ；；“存在”：“不存在”））； System.out.println（“ 51：” +（bm.contains（51）？“存在”：“不存在”）））。
out.println（“ 66：” +（bm。contains（66）？“ exist”：“不存在”）））; System.out.println（“ 1。