大数据的海量性(海量数据是做什么的)

海量数据，不能一次加载到内存中

海量数据topK(最大和最小k个数)，第k大，第k小的数海量数据判断一个整数是否存在其中海量数据找出不重复的数字找出A,B两个海量url文件中共同的url

最大K使用最小堆，最小K使用最大堆，这里以最大K为例

海量数据hash分块维护最小堆的K个数据的数据容器堆中数据是topK大的数据，堆顶的数据是第K大数据

先将海量数据hash再取模m，分成m个小文件，hash(num)%m，也可以直接取模在每个小文件中维护K个数据的最小堆，堆顶是当前堆中的最小值遍历每个小文件中剩余的数据，与堆顶的数据进行比较，更新最小堆中的数据生成m * K个数据，然后对这些数据再进行排序，或者再次通过维护最小堆

变形

第K大不只是topK，此时堆顶数据即是只求最大或最小海量数据不仅仅是整数，也可以是字符串海量数据按照出现的次数或者频率排序，topK

海量数据按照出现的次数或者频率排序，topK

先将海量数据hash再取模m，分成m个小文件，hash(num)%m扫描每个小文件的数据，通过hash_map建立值和频率的键值对以出现的频率维护最小堆的K个数据的数据容器遍历每个小文件中剩余的数据，与堆顶的数据进行比较，更新最小堆中的数据生成m * K个数据，然后对这些数据再进行排序，或者再次通过维护最小堆

题目：两个文件各存50亿个url，每个url64个字节，内存限制4G，找出A,B共同的url

单个文件读取肯定超出内存大小，所以还是采取之前的分治思想，大化小，对A/B分别取模分成1000个文件存储，这样两个文件中相同的url都被分到相同的小文件中，若有一方的小文件还是太大，则可以扩大分块或者通过不同hash函数继续hash（若继续，两方应该一起），50亿url算下来每个文件300M。对小文件求公共url的时候可以使用hash_set去重。A文件Set建立后另外一个文件的内容遍历跟Set中内容比对，如果相等则记录

bitmap一般是total/32 + 1个数组，从a[0]开始，每组是32bit表示，对应位的0或1表示十进制的0-31是否存在，可以用于快速排序，快速去重，快速查询

分治思想，首先分成小文件，然后建立HashTable进行统计可以使用BitMap，每个数分配1Bit，0不存在，1存在建立完毕扫描数据把对应位置的比特位描成0/1，最后查找整数的位置是否为1（通过商判断在哪个数组中，余数判断哪一位）

可以使用BitMap，每个数分配两Bit，00不存在，01出现一次，10出现多次，11没意义。需要内存2^32 * 8 * 2bit，建立完毕扫描数据把对应位置的比特位描成00/01/10/11，最后查找01