bitmap

bitmap往往是做一个映射，来减小数原数据占用空间的大小。在Java中，一个int类型的大小是32位，也就是32bit，它占4字节，也就是4byte，现考虑如下场景：

现在要存储三个数字，比如说5，16，20，如果用一个int数组存储，那么就需要3 * 4 = 12字节，但是我们可以换一个思路，比如说使用byte数组，1byte是8位，也就是说可以通过这8位的值位0或1，来代表是否存在数字0-7。那么原来的4字节，就可以代表数字0-31是否存在于集合当中。具体如下表所示

数组值	1	1	0	0	0	0	1	1
下标	0	1	2	3	4	5	6	7
说明	值为1，代表存在数字0	值为1，代表存在数字1	值为0，代表不存在数字2	值为0，代表不存在数字3	值为0，代表不存在数字4	值为0，代表不存在数字5	值为1，代表存在数字6	值为1，代表存在数字7

通过这种转换，我们就使用了1字节存储原来需要16字节（4个数字0，1，6，7）才可以存储的集合。

在具体的实现中，我们初始化一个byte数组

1	byte[] bytes = new byte[20];

我们在计算某一个数字是否存在时，我们要先计算该数字在byte[]数组中的下标，当计算完下标之后，我们就需要将该数字移位，计算出它在该下标在哪一位。

这里的bytes[i]就是上面表格中的样子。每一个byte的大小为2^8 - 1，可以表示0~2^8 - 1。

题目思路

1GB大小的文件，全部存储单词，我们假设平均每个单词的长度为10，查阅资料得知Java中空字符串占用40字节，我们做一个大致的估算，一个单词长度为10，那么每个单词占用空间大小就是60字节（一个char[]数组中每个字符占2字节）。那么这1GB大小的文件当中一共有1 * 1024 * 1024 / 60 = 17476个单词。

1	对象头（8 字节）+ 引用 (4 字节 ) + char 数组（16 字节）+ 1个 int（4字节）+ 1个long（8字节）= 40 字节

一个最笼统的思路，我们可以对每一个单词做一个Hash，然后将他映射到一个bitmap上，通过这种转化，原先1G大小的单词，就可以通过该映射存储到对应的位置。

但是这种思路好像没办法解决对应的问题，因为bitmap只能存储0或者1，如果存在两个相同的单词，并不能够进行统计，并且还有Hash冲突的可能。

另外一个思路

这是一个经典的top k的问题，所以说一般采用大根堆或者小根堆来处理。但是文件比较大，内存又比较小，这时就引入另一种解决问题的方案，分治。

即我们可以先通过hash，将这一个文件打散，这里可以确定地一点是，相同地单词一定可以hash到一个文件中，不同的单词有可能hash到一个文件中，可以经过多次打散，具体可以看内存中可以读入多少个单词。然后记录每个文件中的top k ，最终将所有文件的统计结果做一个合并即可。