位圖

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中。
解決方案：

遍歷，時間復雜度O(N)

排序(O(NlogN))，利用二分查找: logN

這兩種方案所需的內存空間都很大，如何利用更小的空間解決這件事情呢？

位圖概念
所謂位圖，就是用每一位來存放某種狀態，適用于海量數據，數據無重復的場景。通常是用來判斷某個數據存不存在的。

在該問題中，我們可以取40億個比特位，每個比特位表示一個數，如果該數出現則標記為1，未出現則標記為0。

布隆過濾器

給10億個不重復的字符串。給一個字符串，如何快速判斷該字符串是否在這10億個字符串中。

我們采取類似位圖的思想，將一個字符串通過相同的方式映射成一個整數，再將對應的下表，標位1。

但是這樣會遇到一個問題，兩個不同的字符串通過映射后得到相同的整數。為了降低這樣的概率，就有人提出了布隆過濾器。

概念
布隆過濾器是由布隆（Burton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數據結構，特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”，它是用多個哈希函數，將一個數據映射到位圖結構中。此種方式不僅可以提升查詢效率，也可以節省大量的內存空間。

查找

分別計算每個哈希值對應的比特位置存儲的是否為零，只要有一個為零，代表該元素一定不在哈希表中，否則可能在哈希表中。

哈希切割

給一個超過100G大小的log ?le, log中存著IP地址, 設計算法找到出現次數最多的IP地址？

概念

哈希切割就是將一個大文件，利用哈希的原理，將其分為若干個小文件。相同的數據都被分到同一個文件里。

將每一個log中的IP通過哈希函數映射成一個整數%100，分到100不同的小文件，在進行計數