算法与数据结构——大数据题目（java）（b站左程云课程笔记总结）

1. 哈希函数可以把数据按照种类均匀分流（比较万能）
2. 布隆过滤器用于集合的建立与查询，可以节省大量空间
3. 一致性哈希解决数据服务器的负载管理问题
4. 利用并查集结构做岛问题的并行计算
5. 位图解决某一范围上数字的出现情况，并可以节省大量空间
6. 利用分段统计思想，并进一步节省大量空间
7. 利用堆、外排序来做多个处理单元的结果合并

布隆过滤器中提过的位bit

2^32/8字节约等于500多MB，即申请一个500多MB的整型数组，就可以表示所有数字有没有出现过（0、1）

进阶问题：

先把全部内存拿去生成一个整型数组，假设现在给的内存是3kb，则此时能生成一个大小为3000/4的int数组，3000/4约等于700，向下取最接近的2的某次方，即512，题目范围是0-2^{32-1，一共有2}32个数，除以512等于8388608，就能均分该范围的所有数，分成512份

此时每进来一个数，就除以8388608得到一个0-511之间的数，数组中对应的索引上的数++，40亿个数全部统计完的时候，肯定有小于8388608的数，就可以知道缺的数字来自哪个范围，然后就可以在该范围继续用512去分（还是用40个数去检验），周而复始就能定位到没出现过的数字

哈希：分到不同的机器或不同的时间分到同一台机器进行统计，同一种url会进一个文件，在每个文件（机器）中进行统计

布隆过滤器：每次添加之前进行查询操作，如果已经加入过（即重复），则将重复的url记录在文件中，有失误率

同样使用哈希分流将词汇分流到不同的小文件中，每个小文件中包含的是大根堆（词频），每个小文件的堆顶拿出来单独再组成一个大根堆（总堆），把总堆的堆顶弹出即词汇量排名第一的，然后找到该词汇对应的小文件，把小文件的堆顶弹出并把新的堆顶加入到总堆中，周而复始，直到弹出100个数，都是堆，时间复杂度都是O(logN)，代价低

可以使用万能的哈希来处理，取hash＋取模的方式，同一个数会进入同一个文件，再用哈希表等方式统计即可

用两个位来表示一个数出现的状态

00表示出现0次

01表示出现1次

10表示出现2次

11表示出现了2次以上

40亿个数*2位即80亿位

80亿/8字节=10亿字节<1GB

2^32个数经过上述处理刚好是1GB的内存

分段思想，假设现在要求更加严格，是10KB，看10KB能申请一个多长的无符号整型数组，10KB/4B=2500，取小于等于的最大2的次方数2048，现在范围是0-2^{32-1，所有数的范围可以被等分成2048份，2}32/2048=2097152，即0-2097151是第一个范围，40亿个数每进来一个就除以2097152看落在哪个范围，例如1/2097152=0，数组0索引上对应的数+1，统计词频，全部数字都统计完成之后，记录从arr[0]+arr[1]+arr[2]直到该数等于或大于20亿，就可以直到中位数再哪个范围，就可以知道在某一个长度为2097152的范围上有中位数，再将该范围的数等分成2048份，重复上述操作，最终就可以得到全局的中位数

给定一个10GB的文件，里面放着无序的int整型数，现在一定的内存（5GB、5KB…），要求将原先再文件中的数都放到另一个文件中并且保证有序

内存所使用的数据结构是小根堆，小根堆中存放的是数以及出现的次数，根据数值组织，每条数据八个字节，都是int类型，小根堆都还有其他存储空间的消耗，假设每条数据16字节，5GB的内存可以存放5GB/16≈2^{28字节条数据（1GB=2}30字节），该文件中存放的数范围是-2^31~231-1，可以将该范围的数均分成2^32/228=2^{4份，将文件中所有的数都除以2}4，只关注在第一个范围上的数（即-2^31~(-231+2^{28-1)），不在该范围上的数忽略，重复的数在小根堆中是以value词频的形式出现，然后小根堆一个个往外弹出加入到新文件中，以小根堆中的数据的key作为数字，value作为次数，小根堆全部依次弹出后，再关注下一个范围上的数，依次进行2}4次，完成文件迁移以及结果有序

//实现一个函数，n是非负数就返回1，n是负数就返回0，不使用比较的方式
public int sign(int n){
    return flip((n>>31)&1);//n右移31位就是符号位
}

//保证输入参数n不是1就是0 输入1的话输出0 输入0的话输出1
public int filp(int n){
    return n^1;
}


//此方法有问题，a-b可能会溢出
public int getMax1(int a,int b){
    int c=a-b;
    int scA=sign(c);//a-b为非负的话，scA为1  a-b为负数的话，scA为0
    int scB=flip(scA);//scA为0，scB就为1;scA为1，scB就为0
    return a*scA+b*scB;//返回较大的那个数  互斥条件相加替代了比较的过程
}

//a和b的符号相同的话就不会溢出，溢出的情况只会发生在a和b符号不同的情况
//返回a有两种情况，第一种：a和b相同且a-b>=0  第二种：a和b不相同且a>0
public int getMax2(int a,int b){
    int c=a-b;
    int sa=sign(a);
    int sb=sign(b);
    int sc=sign(c);
    int difSab=sa^sb;//a和b的符号不一样，就为1，a和b的符号一样就为0
    int sameSab=flip(difSab);//a和b的符号一样，就为1，a和b的符号不一样就为0
    int returnA=difSab*sa+sameSab*sc;//a的总状态
    int returnB=flip(returnA);//b的总状态与a的总状态互斥
    return a*returnA+b*returnB;
}

2的幂二进制位上只有一个是1，其他都是0

方法一：得到这个数最右侧的1，判断这个数是不是与原来的数相等 A&(~A+1)

方法二：判断x&(x-1)是否等于0

public boolean is2Power1(int n){
    return (n&(~n+1))==n;
}

public boolean is2Power2(int n){
    return (n&(n-1))==0;
}

判断是否是4的幂，首先判断是否是2的幂

如果不是2的幂就也不是4的幂

如果是2的幂说明只有一个1

而4的幂的特征是那个1的位置在奇位数上

再和01010101…01这个数做&操作，结果等于0，则不是4的幂，不等于零则是4的幂

public boolean is4Power(int n){
    return (n&(n-1))==0&&(n&0x55555555)!=0;//0x55555555就是01010101....01这个数
}

异或^：无进位相加

两个数相加=无进位相加+进位信息

进位信息=两数求与&再往左移动一位

再将异或结果和进位结果做相同操作直到进位结果为0，此时的异或结果就是答案

public int add(int a,int b){
    int sum=a;
    while(b!=0){
        sum=a^b;
        b=(a&b)<<1;
        a=sum;
    }
    return sum;
}

减法就是a+b的相反数

b的相反数就是取反+1

public int minus(int a,int b){
    return add(a,negNum(b));
}

public int negNum(int n){
    return add(~n,1);
}

小学乘法计算

public int multi(int a,int b){
    int res=0;
    while(b!=0){
        if((b&1)!=0){//b的最后一位等于1才会进入
            res=add(res,a);
        }
        a<<=1;
        b>>>=1;
    }
    return res;
}

a/b：b尽可能地向左移动，但不要超过a

乘法的逆向思维

比如b向右移动了三位，说明要得到的结果从右往左数第四位是1

然后将a与b右移三位的数做差

将做差的结果与b再做上述操作，看右移几位然后判断

最后有余数不管（计算机除法）

public int div(int a,int b){
    int x=isNeg(a)?negNum(a):a;
    int y=isNeg(b)?negNum(b):b;
   	int res=0;
    for(int i=31;i>-1;i=minus(i,1)){
        if((x>>i)>=y){//这里使用x右移的方式更加安全
            res|=(1< 
nt y=isNeg(b)?negNum(b):b;
 int res=0;
 for(int i=31;i>-1;i=minus(i,1)){
 if((x>>i)>=y){//这里使用x右移的方式更加安全
 res|=(1< x=minus(x,y< }
 }
 return isNeg(a)^isNeg(b)?negNum(res):res;
 }