# 海量数据处理

## 备忘

*   `1 GB`: 十亿个字节（Byte）

    > `1(B) * 10*10^8 / 1024 / 1024 ≈ 953.67(MB) ≈ 1000(MB) ≈ 1(GB)`
*   `400 MB`: 一亿个 4 字节（Byte） int 整型占用的内存

    > `4(B) * 10^8 / 1024 / 1024 ≈ 381.57(MB) ≈ 382(MB) ≈ 400(MB)`
    >
    > * 10 亿个整型 -> `400(MB) * 10 = 4(GB)`
    > * 40 亿个整型 -> `4(GB) * 4 = 16(GB)`
*   `12 MB`: 一亿个比特（bit）占用的内存（相比于 int 型，节省了 32 倍内存）

    > `1(b) * 10^8 / 8 / 1024 / 1024 ≈ 11.92(MB) ≈ 12(MB)`
    >
    > * 10 亿个比特 -> `12(MB) * 10 = 120(MB)   ≈ 4(GB)/32 = 128(MB)`
    > * 40 亿个整型 -> `120(MB) * 4 = 480(MB)   ≈ 16(GB)/32 = 500(MB)`

## Index

* [判断一个整数是否在给定的 40 亿个（不重复）整数中出现过](#判断一个整数是否在给定的-40-亿个不重复整数中出现过)
* [Reference](#reference)

## 判断一个整数是否在给定的 40 亿个（不重复）整数中出现过

> [腾讯面试题：给定 40 亿个不重复的...](https://blog.csdn.net/wenqiang1208/article/details/69669084) - CSDN博客

**思路 1**

* BitMap

**思路 2**

* Hash 分桶 + 排序 + 二分查找

**思路 3**

* 外部排序 + 结构存储 + 二分查找
  * int 型整数的范围是 `2^32 ≈ 42亿`，那么对于 40 亿个整数，必然存在大量连续的范围
  *   排序后，必然存在大量以下情况：

      ```
      1 2 3 4  7 8 9  ...
      ```
  *   对于这种形式的序列，可以构造如下结构

      ```
      struct {
          start;        // 记录连续序列的开头
          n_continue;   // 连续字段的长度
      }
      ```
  *   则上述示例，可以存储为

      ```
      (1, 4), (7, 3), ...
      ```
* 复杂度分析
  * 这样最差情况存在 `2(=42-40)` 亿个断点，即 `2` 亿个结构体，每个结构体占 `8` 个字节，共 `400(MB) * 4 = 1.6(GB)`
  * 每次查找的时间复杂度为 `O(logN)`

**思路 4**

* 多机分布式

## Reference

* [海量数据处理面试题集锦](https://blog.csdn.net/v_july_v/article/details/6685962) - CSDN博客&#x20;
* [十道海量数据处理面试题与十个方法大总结](https://blog.csdn.net/v_JULY_v/article/details/6279498) - CSDN博客&#x20;
