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

  8. 之前的课已经介绍过前4个内容，本节内容为介绍解决大数据题目的后3个技巧

    32位无符号整数的范围是0~4，294，967，295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数？
    【进阶】
    内存限制为10MB，但是只用找到一个没出现过的数即可

    利用分段统计思想、并进一步节省大量空间
    40亿个数可以表示为2^32，2^32 / 8 = 500M
    基础做法可以遍历这40亿个数，创建一个500M的位图将它们都放进去看看那个位的状态没有被修改，就没有出现过哪个数。
    在此题目的基础上内存限制为3KB，如何做？

  9. 先把3KB的内存生成一个最大的整形数组，一个int可以占32位，也就是四个字节。看3kb能产生多大的int数组，且这个数组得是2的多少次方，这个2的多少次方得小于3kb。3000/4 ≈ 700，也就是创建一个int[512]的数组

  10. 将40亿个数也就是0~2^32 - 1，划分成512份，每一个都是等量的。
    2^32 / 512 = 8388608，
    arr[0] 表示 0~8388608范围内的数，出现了多少次，arr[1] 表示 8388609~XXXXXX出现了多少次，剩下的依次类推。让遍历的每一个数都除以8388608，结果是几对应的arr[X]++
  11. 一共40亿个数，数组可以统计的数是42亿，也就是哪个范围内的数没有被统计到，arr[X]就会小于8388608
  12. 找到arr[X] < 8388608的数组下标，就可以找到缺少的数所在的范围
  13. 然后将这个范围内的数再次划分为512份，再次进行全部的遍历统计

假设只能申请几个变量，可以将2^32 / 2 因为只有40亿个数，总有一边小于另一边，然后就一直二分下去，最多分32次

有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL
【补充】
某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种求出每天热门Top100词汇的可行办法

原问题的解决方法：

  1. 可以用哈希分流，将URL放到不同的文件里，然后统计每个文件URL出现的次数
  2. 可以位图，但是有一定的失误率，先查看URL对应的位图的状态，如果为1，就已经有了

补充解法：

  1. 先根据哈希函数对词汇进行分流，分到不同的文件里
  2. 然后统计每个文件里词汇的个数，创建一个哈希表（map）key是词汇，value是个数。
  3. 把每个文件的词汇和它所对应的词汇个数创建一个对象，然后给每个文件创建一个大根堆，把对象放进去。
  4. 把每个文件所对应的堆的堆顶复制一份，放到一个新的大根堆，然后就可以比较出每个文件中出现个数最多的词汇，将它作为Top1。

  5. 然后将它所在的堆的堆顶弹出，也就是弹出它自己，然后再弹出一个，将它放到比较的大根堆里，再进行比较，然后重复4-5步

    32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。
    【补充】
    可以使用最多10MB的内存，怎么找到这40亿个整数的中位数？

    40亿个数表示2^32
    解决方法用位图，但是普通的位图不行，普通的位图只能表示0次和1次，得用两个位来表示一个数出现了几次，
    00没有出现，01出现一次，10出现两次，11表示出现大于两次。2^32 * 2bit / 8 < 1GB此方法可以

    腾讯面试题

    有一个10G文件，它里面都是数而且都是无序，给你5G内存，对此文件的数进行一个排序，输出到另一个文件里

  6. 创建一个小根堆，小根堆放的是很多条记录，key是数，value是数出现的次数，每一条记录占8bit

  7. 1G = 2^30 5 2^30 / 2^4 = 5 2^26最后找的是2^27
    5*2^30表示5G内存
    2^4 = 16 8bit表示每一条数据，剩余的是堆的索引及其它消耗
    2^27 表示堆可以存多少条数据
    image.png
    int表示的范围是-2^31-2^31 - 1也就是2^32，堆的总大小是2^27，2^32 / 2^27 = 2^5，2^5也就是每一条数据统计的范围是2^5，也就是划分成5份
  8. 第一份-2^31~-2^31+2^27 - 1
    第二份的范围是-2^31+2^27~-2^31+2^27*2-1
  9. 创建小根堆，然后遍历文件中的所有的数，先看在第一个范围内的数，在小根堆里创建数据统计他们创建了多少次，遍历完之后就可以得到第一个范围内的数出现了多少次，而且是从小到大排序的

上面方法不是最优解
假设有10个数，大根堆只能存放3个记录【数，此数出现的次数】，如果堆里没有数据直接添加，有则看此数是否小于大根堆的堆顶，如果小就把它放进去，把堆顶弹出。这个堆只收集最小的三个数，维护一个变量y=Integer.MIN_VALUE，遍历完第一次之后，y = 堆顶的值，下一次遍历时最小的三个数得大于y，重复这些步骤

位运算的题目

之前介绍过一些，下面继续。给定两个有符号32位整数a和b，返回a和b中较大的。
【要求】不用做任何比较判断。

  1. public class GetMax {
  2.     // 请保证参数n，不是1就是0的情况下
  3.     // 1 -> 0
  4.     // 0 -> 1
  5.     public static int flip(int n) {
  6.         return n ^ 1;
  7.     }
  9.     // n是非负数，返回1
  10.     // n是负数，返回0
  11.     public static int sign(int n) {
  12.         return flip((n >> 31) & 1);
  13.     }
  15.     public static int getMax1(int a, int b) {
  16.         int c = a - b;    //此方法可以会产生错误，有可能a - b会溢出
  17.         int scA = sign(c);    // a-b为非负，scA为1；a-b为负，scA为0
  18.         int scB = flip(scA);    // scA为0，scB为1；scA为1，scB为0
  19.         // scA为0，scb必为1；scA为1，scB必为0
  20.         return a * scA + b * scB;
  21.     }
  23.     // 此方法不会进行溢出
  24.     public static int getMax2(int a, int b) {
  25.         int c = a - b;
  26.         int sa = sign(a);
  27.         int sb = sign(b);
  28.         int sc = sign(c);
  29.         int difSab = sa ^ sb;    // a和b的符号不一样，为1；一样，为0；
  30.         int sameSab = flip(difSab);    // a和b的符号一样，为1；不一样，为0
  31.         // 返回a：
  32.         // 1. a和b的符号相同，并且a - b >= 0
  33.         // 2. a和b 不相同，并且 a > 0
  34.         int returnA = difSab * sa + sameSab * sc;
  35.         int returnB = flip(returnA);
  36.         return a * returnA + b * returnB;
  37.     }
  39.     public static void main(String[] args) {
  40.         int a = -16;
  41.         int b = 1;
  42.         System.out.println(getMax1(a, b));
  43.         System.out.println(getMax2(a, b));
  44.         a = 2147483647;
  45.         b = -2147480000;
  46.         System.out.println(getMax1(a, b)); // wrong answer because of overflow
  47.         System.out.println(getMax2(a, b));
  48.     }
  49. }

判断一个32位正数是不是2的幂、4的幂

  1. public class Power {
  2.     // 或者取出这个数最右侧的1，如果和原来的数相同，则返回true
  3.     public static boolean is2Power(int n) {
  4.         return (n & (n - 1)) != 0;
  5.     }
  6.     // 一个数是4的幂，也就是2的幂
  7.     public static boolean is4Power(int n) {
  8.                                           // 0x55555555 = 01010101，4的幂都只会在这些位置上
  9.         return (n & (n - 1)) != 0 && (n & 0x55555555) != 0;
  10.     }
  11. }

给定两个有符号32位整数a和b，不能使用算数运算符，分别实现a和b的加、减、乘、除运算
【要求】
如果给定a、b执行加减乘除的运算结果就会导致数据的溢出，那么你实现的函数不必对此负责，除此之外请保证计算过程不发生溢出

  1. public class AddMinusMultiDivideByBit {
  2.     // 如果，用户传入的参数，a + b就是溢出的，用户活该
  3.     public static int add(int a, int b) {
  4.         int sum = a;
  5.         while (b != 0) { // 循环是因为相加产生的进位也有可能产生进位
  6.             sum = a ^ b; // 无进位相加
  7.             b = (a & b) << 1; // 与是进位信息，必须左移一位
  8.             a = sum;
  9.         }
  10.         return sum;
  11.     }
  13.     public static int negNum(int n) {
  14.         return add(~n, 1);
  15.     }
  17.     public static int minus(int a, int b) {
  18.         return add(a, negNum(b));
  19.     }
  21.     public static int multi(int a, int b) {
  22.         int res = 0;
  23.         while (b != 0) {
  24.             if ((b & 1) != 0) {
  25.                 res = add(res, a);
  26.             }
  27.             a <<= 1;
  28.             b >>>= 1;
  29.         }
  30.         return res;
  31.     }
  33.     public static boolean isNeg(int n) {
  34.         return n < 0;
  35.     }
  37.     public static int div(int a, int b) {
  38.         int x = isNeg(a) ? negNum(a) : a;
  39.         int y = isNeg(b) ? negNum(b) : b;
  40.         int res = 0;
  41.         for (int i = 31; i > -1; i = minus(i, 1)) {
  42.             if ((x >> i) >= y) {
  43.                 res |= (1 << i);
  44.                 x = minus(x, y << i);
  45.             }
  46.         }
  47.         return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
  48.     }
  50.     public static int divide(int a, int b) {
  51.         if (b == 0) {
  52.             throw new RuntimeException("divisor is 0");
  53.         }
  54.         if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
  55.             return 1;
  56.         } else if (b == Integer.MIN_VALUE) {
  57.             return 0;
  58.         } else if (a == Integer.MIN_VALUE) {
  59.             int res = div(add(a, 1), b);
  60.             return add(res, div(minus(a, multi(res, b)), b));
  61.         } else {
  62.             return div(a, b);
  63.         }
  64.     }
  66.     public static void main(String[] args) {
  67.         int a = (int) (Math.random() * 100000) - 50000;
  68.         int b = (int) (Math.random() * 100000) - 50000;
  69.         System.out.println("a = " + a + ", b = " + b);
  70.         System.out.println(add(a, b));
  71.         System.out.println(a + b);
  72.         System.out.println("=========");
  73.         System.out.println(minus(a, b));
  74.         System.out.println(a - b);
  75.         System.out.println("=========");
  76.         System.out.println(multi(a, b));
  77.         System.out.println(a * b);
  78.         System.out.println("=========");
  79.         System.out.println(divide(a, b));
  80.         System.out.println(a / b);
  81.         System.out.println("=========");
  83.         a = Integer.MIN_VALUE;
  84.         b = 32;
  85.         System.out.println(divide(a, b));
  86.         System.out.println(a / b);
  87.     }
  88. }