① 布隆過濾器詳解
布隆過濾器 （英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。主要用於判斷一個元素是否在一個集合中。
通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為 ， ， 。
這個時候，布隆過濾器（Bloom Filter）就應運而生。
了解布隆過濾器原理之前，先回顧下 Hash 函數原理。
哈希函數的概念是：將任意大小的輸入數據轉換成特定大小的輸出數據的函數，轉換後的數據稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：
所有散列函數都有如下基本特性：
但是用 hash表存儲大數據量時，空間效率還是很低，當只有一個 hash 函數時，還很容易發生哈希碰撞。
BloomFilter 是由一個固定大小的二進制向量或者點陣圖（bitmap）和一系列映射函數組成的。
在初始狀態時，對於長度為 m 的位數組，它的所有位都被置為0，如下圖所示：
當有變數被加入集合時，通過 K 個映射函數將這個變數映射成點陣圖中的 K 個點，把它們置為 1（假定有兩個變數都通過 3 個映射函數）。
查詢某個變數的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了
為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。
布隆過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在於相同的 bit 位被多次映射且置 1。
這種情況也造成了布隆過濾器的刪除問題，因為布隆過濾器的每一個 bit 並不是獨占的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)
相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數 ，另外，散列函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何數據結構都不能；
但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加 1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。
在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。
在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。
如網頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷和緩存穿透等問題。
布隆過濾器的典型應用有：
知道了布隆過濾去的原理和使用場景，我們可以自己實現一個簡單的布隆過濾器
分布式環境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實現了布隆過濾器。
當然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個文件，放入OSS、S3這類對象存儲中。
Redis 提供的 bitMap 可以實現布隆過濾器，但是需要自己設計映射函數和一些細節，這和我們自定義沒啥區別。
Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件載入到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。
在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式
直接編譯進行安裝
使用Docker進行安裝
使用
布隆過濾器基本指令：
我們只有這幾個參數，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這里就不做這個實驗了。
上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次 add 的時候自動創建。
Redis 還提供了自定義參數的布隆過濾器， bf.reserve 過濾器名 error_rate initial_size
但是這個操作需要在 add 之前顯式創建。如果對應的 key 已經存在，bf.reserve 會報錯
我是一名 Javaer，肯定還要用 Java 來實現的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴展機制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這里用 Redisson
為了解決布隆過濾器不能刪除元素的問題，布穀鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者將布穀鳥過濾器和布隆過濾器進行了深入的對比。相比布穀鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數。
由於使用較少，暫不深入。
https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf
http://www.justdojava.com/2019/10/22/bloomfilter/
https://www.cnblogs.com/cpselvis/p/6265825.html
https://juejin.im/post/5cc5aa7ce51d456e431adac5
② 垃圾簡訊郵件判斷演算法
垃圾簡訊，垃圾郵件和推銷的電話使我們深受其擾，不過也有些手機軟體助手，可以幫助我們垃圾這些垃圾簡訊和電話，這些軟體的背後的演算法是什麼？
像360手機衛士這種APP在手機本地或雲端保存一份電話的手機黑名單數據，來電的時候手機判斷下就可以決定是否為騷擾電話了，本地存儲，黑名單的數據量如果很大的話，可能會占內存比較大，不過這個可以借鑒以前的布隆過濾器這種數據結構來解決，但是布隆過濾器有誤判的可能，有可能來電非黑名單卻當成黑名單進行處理了，這對於攔截軟體來說是比較嚴重的問題，所以可能是多種方法來結合判斷，或者對於布隆過濾判斷是屬於黑名單的電話，再通過一次聯網到網上的雲端再判斷一次是否為真正為黑名單用戶，不過這就需要聯網，還存在延遲的可能；對於布隆過濾器判斷為正常用戶的，則一定是正常用戶，那麼大部分時間是不需要聯網判斷或結合其他辦法判斷的。
像很多病毒檢測軟體，或IDS或WAF軟體一樣，垃圾簡訊和騷擾電話 也可以建立自己的規則庫，通過規則庫進行垃圾簡訊的判斷，同樣像IDS等軟體存在誤判的情況一樣，垃圾簡訊採用規則判斷的話，也存在一定的誤判性，一般也要結合其他的判斷規則綜合判斷。
規則有下面幾個：
凡是規則判斷，都存在著檢測死板，不能檢測到不在規則裡面的情況，而且會被有心者特意設計避開規則的垃圾簡訊等。
直觀地想一下，垃圾簡訊，垃圾郵件這些一般都包含特定的詞語，或者鏈接等，那麼我們反過來統計郵件中特定的詞語的數量，達到一定標准，我們就判斷為垃圾郵件。
現在對於這種垃圾郵件的判斷問題，一般都通過機器學習來解決，在機器學習的演算法中，做垃圾郵件判斷這個是屬於一個二分類問題，可以用很多中演算法來解決，常用的有決策樹，貝葉斯，SVM，神經網路等，其中貝葉斯演算法是屬於一個基於統計學的演算法，也是本次要介紹的演算法。
貝葉斯演算法是為了解決「逆序概率」的問題，舉個簡單的例子，比如我們袋子中有10個紅球，8個白球，然後隨機從袋子中拿出一個球，問是紅球的概率是多少？這是一個非常簡單的概率問題，結果就是10/(10+8),這種正向概率問題比較好理解。那麼反過來，如果我們只知道袋子中有紅球和白球，但是不知道數量和比例，我們拿了幾次球，通過拿出這些球的顏色是否可以推斷出袋子中兩種球的比例那？
貝葉斯演算法中有些根據以前經驗總結出來的概率，稱為先驗概率，可以理解成先前的經驗的概率，所以叫先驗概率，比如清明時節一般會下雨，下雨的概率大概為70%，這就是通過以前的經驗總結的；
後驗概率， 是事情發生了，推測可能原因，比如小明遲到了，那麼起晚了造成遲到的概率假設為30%，這就是後驗概率。條件概率，就是在一個事情假設A發生的情況下，另外一個事情B也發生的概率，記作P(B|A),讀作在A發生的情況下，B發生的概率，比如起晚的情況下，小明遲到的概率。
總結一句話：先驗概率是經驗總結，後驗概率是由果推因，條件概率是由因推果。
根據條件概率的定義，可以推導出貝葉斯公式，推導過程在網路裡面如下：
說明：
1）P(A|B) = A和B同時發生的概率/B發生的概率，直觀想下，B發生的概率一定大於A和B同時發生的概率，相除的含義就是在B發生的概率情況下，有多少A也同時發生的概率，也就符合了條件概率的定義。
2）把除法變乘法就得到了合並後的式子，再變化下，就得到了貝葉斯公式。
可能還比較抽象,舉個wiki上的例子：
我們用兩種演算法進行計算，一是自己直觀想，二是用樸素貝葉斯。
假設學校一共有U個人，直觀想法計算：
P(是女生|穿褲子） = 所有穿褲子的女生數量/所有穿褲子的人數
= U*0.4（女生數量）*0.5（一半穿褲子） / (U*0.4*0.5 +U*0.6*1)
= 0.2*U /0.8*U = 25%
如果用樸素貝葉斯演算法：
P(是女生|穿褲子) = P(穿褲子|是女生) *P(是女生)/P(穿褲子)
= 0.5*0.4/[(0.6*1 +0.4*0.5）/1]
= 0.2 /0.8
= 25%
說明： P(穿褲子） = 穿褲子人數/總人數= U*0.6*1 + U*0.4*0.5/U = 80%
這樣看起來，樸素貝葉斯公式也不是很難。
具體來看下垃圾郵件的分類問題：我們用D表示一封郵件，D是由很多單片語成。用f+表示是垃圾郵件，用f-表示是正常郵件，根據貝葉斯公式，問題形式化：
其中P(f+)和P(f-)比較容易得到，算下一個郵箱裡面有多少個是垃圾郵件，多少個是正常郵件即可，不過最好多找幾個，算下平均值，這就是所謂的先驗概率。
P(D|f+) 表示是垃圾郵件，單詞出現的概率，把D展開成N個單詞就是:
P(d1,d2,d3...dn|f+) 即垃圾郵件中，同時出現這些單詞的概率，這個沒辦法求，假設這些單詞之間是獨立的，沒有什麼關聯關系，那麼P(d1,d2,d3...dn|f+) 就可以擴展為P(d1|f+)* P(d2|f+) P(d3|f+).... P(dn|f+) 這個裡面的獨立假設，就是樸素貝葉斯的樸素來源，因為不是那麼精確，所以叫樸素。計算一個單詞在垃圾郵件中出現的概率就比較簡單了。
翻譯一下：
P(垃圾郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1,單詞d2...同時出現|是垃圾郵件）*P(是垃圾郵件)]/P(單詞d1,單詞d2...同時出現在一封郵件裡面）
根據獨立假設：
P(垃圾郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1出現|是垃圾郵件）*P(單詞d2出現|是垃圾郵件）*P(單詞d3出現|是垃圾郵件）...*P(是垃圾郵件)]/P(單詞d1,單詞d2...同時出現在一封郵件裡面）
其實我們在判斷是否是垃圾郵件的時候，並一定要計算出來P(單詞d1,單詞d2...同時出現在一封郵件裡面），這個也無法精確計算，我們只需要比較垃圾郵件的概率和非垃圾郵件的概率，取大的那一個就可以了，那麼久只要計算：
P(垃圾郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1出現|是垃圾郵件）*P(單詞d2出現|是垃圾郵件）*P(單詞d3出現|是垃圾郵件）...*P(是垃圾郵件)]
P(正常郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1出現|是正常郵件）*P(單詞d2出現|是正常郵件）*P(單詞d3出現|是正常郵件）...*P(是正常郵件)]
1.找到N封郵件，標記好垃圾郵件和非垃圾郵件。
2.對N封郵件進行去掉停詞部分，然後採用分詞演算法做分詞。
3.分別計算每個詞在垃圾郵件中出現的比例，在正常郵件中出現的比例
4.帶入公式算下哪個概率相對大一些，就屬於哪個分類。
這裡面總結的比較簡單，貝葉斯演算法，還有很多沒有說到，我也理解的不夠深刻，先只聊點這種簡單的吧，下一篇將找個例子實戰下樸素貝葉斯演算法。
參考：
1. 數據結構和演算法之美：概率統計
2. 數據分析實戰：樸素貝葉斯
3. 平凡而又神奇的貝葉斯方法
③ 布隆過濾器
如果使用哈希表，內存空間需要100億*64位元組=640G(10億位元組（byte）是1G)，空間就爆掉了。此時就輪到布隆過濾器登場了。
布隆過濾器應用場景：黑名單 爬蟲去重
布隆過濾器優勢：節省內存(30G以內)，查詢速度快
布隆過濾器劣勢：存在一定失誤率
但布隆過濾器的失誤率是可以容忍的，一是可以通過設計人為的把失誤率控制的很低；二是就算失誤了不會誤報已經在黑名單里的URL。布隆過濾器只會把正常的URL當成黑名單系統里的，但不會誤報已經在黑名單里的URL。形象點說就是「寧可錯殺三千不會放過一個」
在講解布隆過濾器原理之前先講點陣圖。
點陣圖是bit類型的數組。 int類型4位元組即32bit，所以長度100的int類型數組可以看出長度3200的bit數組。假如要找1782位比特，那麼在int數組里下標是1782/32，在下標里存的int數字里第幾個比特位？即1782%32的計算結果，從而把整型數組操作轉換成比特類型數組操作。
布隆過濾器即大點陣圖，假設是長度為m的bit數組，那麼佔用m/8位位元組（Byte）,
URL加黑名單過程：開始時m位比特都是0（白）的狀態，該URL通過哈希函數f1得到一個哈希值，然後%m,得到0~m-1上某個位置，將該位置描黑（變成1），再用哈希函數f2得到一個哈希值，再描黑，再用哈希函數f3同樣處理（f1、f2、f3是獨立的哈希函數），假設一共用了k個哈希函數，那麼描黑了k個位置（某個位置重復了就重復了，但一旦描黑就沒有描白的時候）完成後可以說該URL加入了點陣圖里。對下一個URL同樣處理，用k個哈希函數描黑k個位置……一直做100億個，點陣圖中有相當多位置被描黑了。
如何查某個URL在不在黑名單里？把待查的URL用K個哈希函數算出對應的哈希值，再把該哈希值%m，把K個位置的狀態都拿出來，如果全黑，就說這個URL屬於黑名單系統，如果有一個是白，就不屬於黑名單系統。如果m很小，100億個URL之後所有點陣圖都是黑的，那麼不論查誰都在黑名單里；如果m取的大一些，失誤率就會降低。
但布隆過濾器需要准備多少個bit位和單樣本的大小無關。一個URL經過K個哈希函數得到K個哈希值，對m取模後去相應的大比特map中描黑，只要保證哈希函數能接收單樣本這種類型的參數就可以了，與樣本是64位元組還是128位元組無關。所以影響失誤率的重要參數就是樣本量N和點陣圖比特數組長度m。
布隆過濾器三公式： 出處
1.確定m:對於輸入的數據量n（這里是100億）和失誤率p（這里是萬分之一），布隆過濾器的大小m：m = - (n lnp) / (ln2 ln2)
2.確定K：K假如很少，例如只有一個哈希函數，相當於每個數據只採集了一個特徵點，只把一個位置描黑，查的時候也只用一個哈希函數，特徵點不夠，失誤率雖然不至於很高但有一定的量，如果K很大，例如用10萬個哈希函數去把10萬個位置描黑，m的空間會接近耗盡，查什麼URL都是黑的，失誤率非常高。需要的哈希函數的個數k：k = ln2 * m/n = 0.7 * m/n
3.因為前兩步中公式1公式2都會進行向上取整，所以公式3算出的實際的失誤率與比預期失誤率要低
布隆過濾器在Hadoop中的應用：Hadoop中的分布式文件系統，是由許多小文件組成的，如何查詢一個數據在哪個文件里？首先不可能記錄每個小文件的索引，這樣做佔用空間太大了。所以每個小文件里都搞一個布隆過濾器，當Hadoop想知道某個key在哪個文件里，就查每一個布隆過濾器，文件a的布隆過濾器會說明你這個key在我這個文件里，但可能會有誤報；文件c的布隆過濾器會說明你這個key在我這個文件里，但可能會有誤報……如果失誤率很低，哪怕有幾萬個分布式文件，最終可能算出來只有3個文件里可能含有這個key。那麼就只用把這3個小文件遍歷一遍，就知道key在哪個小文件里了。通俗點講，如果一個文件真的含有key，那麼它的布隆過濾器會說這個key屬於我；但因為有失誤率，可能會發生一個文件不含有這個key，它還是會說這個key屬於我；可是這也沒關系，多查一遍就可以，反正失誤率很低，需要遍歷的文件很少。
④ 布隆過濾器
[TOC]
通過解決方案：
Java中如將數據存儲在內存中，最簡單的演算法結構是HashMap。通過HashMap判斷key是否存在，來判斷數據是否存在。通過hash演算法查找元素，時間復雜度基本是 O(1) （可能存在hash沖突後轉換成鏈表或紅黑樹的情況，時間復雜度的影響可以忽略）。
使用HashMap速度很快，存儲簡單，絕大部分場景可以使用。但是HashMap 佔用的空間比較大 ：
為什麼出現布隆過濾器：
舉例：
如1000萬個Integer存儲在內存中，佔用空間為：4x32x10000000位，即1220兆。如布隆過濾器通過4位元組存儲（布隆過濾器通過多次hash對數據計算後-->幾次hash根據數據量指定，得到多個數據， 佔用多個位 ），則佔用空間為610M。比原有空間少一半。
個人覺得，此比較在字元等的比較中尤為有效。
一個字元串多個字元，根據編碼方式，一個字元兩個或三個位元組，如10個字元，字元串存儲佔用20個位元組，還有相關字元串相關的類信息的內存佔用。
位存儲，根據數據量的大小，hash的位數，靈活計算。如4個位元組，則是原hashMap佔用空間的五分之一。
（1）定義位元組向量
先定義一個指定長度的位元組數組（位元組數組，數組內每個元素的值）。
如長度為8（一個位元組大小），默認所有元素值均為0，如下：
（2）計算哈希值
將要寫入過濾器的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。
（3）更新位元組向量
將計算出的位元組向量的索引， 對應的位元組向量中的元素值更高為1 （無論之前為0或者為1，均更改為1）。如下：
（1）計算哈希值
將要判斷過濾器中是否存在的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。
注意：哈希函數的判斷方式和計算索引的方式，需和寫入數據時完全一致。
（2）判斷是否存在
如原位元組數組中，對應1，3，7中存在的元素的值都為1。則判定為此元素 可能存在 ，但凡有一個元素的值不為1，則判定此元素 一定不存在 。
布隆過濾器，主要需實現的目標是， 在指定的數據個數范圍內，滿足誤判率在設定的范圍內 ，誤判率太高的話，無法起到過濾數據的情況，誤判率不能為0。
因此需要計算兩個數據來滿足 存儲數據的個數 和 誤判率 ：
使用布隆過濾器的決定性因素之一，就是此演算法插入數據和查詢數據的速度必須非常快。因此在對數據進行哈希運算的時候， 需選擇計算快的哈希演算法 。
而且， 寫入數據以及查詢數據的哈希演算法，順序和演算法都需完全一致 。
待完善。。。。。
可以通過google的 guava ，在內存中輕松實現布隆過濾器。
無需手動計算滿足位元組數組的長度和哈希個數，只需要輸入 擬輸入數據的個數 和 期望誤判率 即可。
不輸入期望誤判率的情況下，誤判率為0.03，即100個非范圍內的數據進行校驗時，約三個數據會判定為存在。
多次執行，結果一致，根據結果判定：
內存的存儲存在局限性，可以使用redis中的bitMap來實現位元組數組的存儲。
使用redis實現布隆過濾器。需要根據公式，手動計算位元組數組的長度和哈希的個數。
實現過程，待完善。。。。。。
⑤ 什麼是緩存穿透
緩存穿透又稱緩存擊穿,是指在高並發場景下緩存中(包括本地緩存和Redis緩存)的某一個Key被高並發的訪問沒有命中,此時回去資料庫中訪問數據,導致資料庫並發的執行大量查詢操作,對DB造成巨大的壓力。
⑥ Java通過id訪問方法,不讓id重復訪問怎麼實現
就是一個id只能訪問一次嗎？
1，在調用方法前要有控制
2，判定id是否訪問過
比較簡單的，比如訪問過的id存起來，調用前查一下看看是不是已經有了，有了不允許訪問
然後說點逼格高的，
1，用資料庫保存已經訪問的id，但是資料庫會慢一點
2，用緩存保存先過濾一下，不過會越來越大。id不長還是能存很多很多很多的，如果緩存失效再向庫里查，萬無一失
3，布隆過濾器特別適合你這個，每次id訪問過來就加到過濾器裡面，後面直接先用布隆過濾器過濾下，性能特別高，誤判再往後面緩存資料庫走就行
⑦ 布隆過濾器和替代演算法
布隆過濾器和替代演算法：但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。
但是包含查找的數據項的數據文件它一定是會返回的，key-value系統中bloom filter返回的數據文件還是需要查看裡面的內容才能知道是否存在所需的數據的，這就保證了執行結果的正確性和完整性。
只是多訪問一些數據文件而已。在數據量很大key-value系統中，建立統一的B+樹索引的代價是非常大的，維護成本也很高，因此綜合起來bloom filter的性能是最好的。
缺點：
但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。常見的補救辦法是建立一個小的白名單，存儲那些可能被誤判的元素。但是如果元素數量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數數組，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。
⑧ 緩存穿透有哪些解決辦法
具體有哪些解決辦法？
最基本的就是首先做好參數校驗，一些不合法的參數請求直接拋出異常信息返回給客戶端。比如查詢的資料庫 id 不能小於 0、傳入的郵箱格式不對的時候直接返回錯誤消息給客戶端等等。
1）緩存無效 key : 如果緩存和資料庫都查不到某個 key 的數據就寫一個到 redis 中去並設置過期時間，具體命令如下：SET key value EX 10086。這種方式可以解決請求的 key 變化不頻繁的情況，如何黑客惡意攻擊，每次構建的不同的請求key，會導致 redis 中緩存大量無效的 key 。很明顯，這種方案並不能從根本上解決此問題。如果非要用這種方式來解決穿透問題的話，盡量將無效的 key 的過期時間設置短一點比如 1 分鍾。另外，一般情況下我們是這樣設計 key 的： 表名:列名:主鍵名:主鍵值。
2）布隆過濾器：布隆過濾器是一個非常神奇的數據結構，通過它我們可以非常方便地判斷一個給定數據是否存在與海量數據中。我們需要的就是判斷 key 是否合法，有沒有感覺布隆過濾器就是我們想要找的那個「人」。具體是這樣做的：把所有可能存在的請求的值都存放在布隆過濾器中，當用戶請求過來，我會先判斷用戶發來的請求的值是否存在於布隆過濾器中。不存在的話，直接返回請求參數錯誤信息給客戶端，存在的話才會走下面的流程。總結一下就是下面這張圖(這張圖片不是我畫的，為了省事直接在網上找的)：
⑨ 如果面試官問你布隆過濾器，你該怎麼回答
假設遇到這樣一個問題：一個網站有 20 億 url 存在一個黑名單中，這個黑名單要怎麼存？若此時隨便輸入一個 url，你如何快速判斷該 url 是否在這個黑名單中？並且需在給定內存空間（比如：500M）內快速判斷出。
可能很多人首先想到的會是使用 HashSet，因為 HashSet基於 HashMap，理論上時間復雜度為：O(1)。達到了快速的目的，但是空間復雜度呢？URL字元串通過Hash得到一個Integer的值，Integer佔4個位元組，那20億個URL理論上需要：20億*4/1024/1024/1024=7.45G的內存，不滿足空間復雜度的要求。
這里就引出本文要介紹的「布隆過濾器」。
網路上對布隆過濾器的介紹是這樣的：
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率和刪除困難。
是不是描述的比較抽象？那就直接了解其原理吧！
還是以上面的例子為例：
哈希演算法得出的Integer的哈希值最大為：Integer.MAX_VALUE=2147483647，意思就是任何一個URL的哈希都會在0~2147483647之間。
那麼可以定義一個2147483647長度的byte數組，用來存儲集合所有可能的值。為了存儲這個byte數組，系統只需要：2147483647/8/1024/1024=256M。
比如：某個URL（X）的哈希是2，那麼落到這個byte數組在第二位上就是1，這個byte數組將是：000….00000010，重復的，將這20億個數全部哈希並落到byte數組中。
判斷邏輯
如果byte數組上的第二位是1，那麼這個URL（X）可能存在。為什麼是可能？因為有可能其它URL因哈希碰撞哈希出來的也是2，這就是誤判。
但是如果這個byte數組上的第二位是0，那麼這個URL（X）就一定不存在集合中。
多次哈希
為了減少因哈希碰撞導致的誤判概率，可以對這個URL（X）用不同的哈希演算法進行N次哈希，得出N個哈希值，落到這個byte數組上，如果這N個位置沒有都為1，那麼這個URL（X）就一定不存在集合中。
Guava框架提供了布隆過濾器的具體實現：BloomFilter，使得開發不用再自己寫一套演算法的實現。
BloomFilter提供了幾個重載的靜態 create方法來創建實例：
最終還是調用：
真正的byte數組維護在類：BitArray中。
最後通過：put和 mightContain方法，添加元素和判斷元素是否存在。
1、因使用哈希判斷，時間效率很高。空間效率也是其一大優勢。
2、有誤判的可能，需針對具體場景使用。
3、因為無法分辨哈希碰撞，所以不是很好做刪除操作。
1、黑名單
2、URL去重
3、單詞拼寫檢查
4、Key-Value緩存系統的Key校驗
5、ID校驗，比如訂單系統查詢某個訂單ID是否存在，如果不存在就直接返回。
⑩ 生日悖論是啥我用它省了上百G的內存
生日悖論 : 是指在不少於 23 個人中至少有兩人生日相同的概率大於 50%。例如在一個 30 人的小學班級中，存在兩人生日相同的概率為 70%。對於 60 人的大班，這種概率要大於 99%。從引起邏輯矛盾的角度來說，生日悖論並不是一種 「悖論」。但這個數學事實十分反直覺，故稱之為一個悖論。
生日悖論是有個有趣的概念，但這和我省上百G的內存有什麼關系？
首先介紹下背景，工作中我負責了一個廣告數據系統，其中一個功能就是對同一次請求的廣告曝光去重，因為我們只需要知道這次請求這個廣告的一次曝光就行了，那些同一次請求產生的重復曝光記錄下來沒有意義，而且還耗會增加我們的存儲成本。所以這里就需要有個邏輯去判斷每條新到的曝光是否只之前已經記錄過的，舊的方案是在redis中存儲請求唯一標識(uuid)和廣告ID(adid)，每次數據過來我們就看redis里有沒有uuid+adid這個key，有就過濾掉，沒有就不過濾並在redis記錄下來已出現。
問題就來了，redis記錄的這份數很大(兩天數據超過400G)，而且隨著我們業務的增長，我們的Redis集群快盛不下了…… 當然花錢加機器是最簡單的方式，畢竟能用錢解決的問題都不是問題。而優秀的我，為了替公司省錢，走了優化的路。
首先可以肯定的是數據條數不會少，因為業務量就在那裡，所以減少數據量的這條路肯定行不通。那是否可以減少每條數據的長度呢？
我們再來看下redis存儲的設計，如下圖：
這里我們用的是隨機UUID，這個版本中有效二進制位是122個，所以總共有 個有效的UUID。 因為是隨機產生的所以肯定有重復的概率，UUID重復的概率有多少？ 要算這個重復概率，光有 這個總數還不行，還得知道你擁有的UUID個數。 我把這個問題具體下，求：在 個UUID中有重復的概率是多少？
這不就是生日悖論的數據放大版嗎？ 當然這個概率可以根據上面公式計算，其中x是UUID的總數 ，n是 ，引用網路的數據，概率為 這比你出門被隕石撞的概率還小很多。
另外，從上面的公式也可以看出，在n固定的時候，隨著有效二進制位的減少，概率p就會增加。 回到我們廣告去重的場景下，每天最大請求數n是基本固定的，而且我們也可以忍受一個較小的概率p（小於萬分之一），然後就可以反推出這個x有多大。
其實只要 ，p就會小於萬分之一。我可以從歷史數中統計出n的大小，然後計算出x，再留一定的buff，然後根據n的大小重新設計了redis的key。(因為涉及公司數據，這里不公布中間計算過程)
最終有效位我選取了40個有效二進制位(10個16進制位)，但我並沒有直接截取UUID的前10位，因為UUID的前幾位和時間有關，隨機性並不強。我選擇將整個UUID重新md5散列，然後截取md5的前10位，然後拼接adId形成最終的key，如下圖：
明顯看出，key的長度縮小了一半，總體上能節省至少50%的存儲空間。備註：但其實我們redis的具體存儲實現和上文描述略有差異，為了不喧賓奪主上文特意對實際實現做了簡化描述，所以最終實際沒有省一半以上的內存，只省了35%左右。
實際優化就到這了，但其實還是不夠極致，其實adId中也包含大量的冗餘信息也可以截取，其實我們可以承受更高的重復率，其實我們可以把redis數據存儲時間設的更短一些……
上面幾種方法都可以進一步優化，但存儲空間不會有量級級別的減少，而下面一種方式，可以將存儲空間減小99%以上。
關於布隆過濾器的原理，可以參考我之前寫的一篇文章 布隆過濾器(BloomFilter)原理 實現和性能測試 。 布隆過濾器完全就是為了去重場景設計的，保守估計我們廣告去重的場景切到布隆過濾器，至少節省90%的內存。
那為什麼我沒有用布隆過濾器，其實還是因為實現復雜。redis在4.0後支持模塊，其中有人就開發設計了布隆過濾器的模塊 RedisBloom ，但無奈我們用的redis 還是3.x版本 ！我也考慮過應用端基於redis去實現布隆過濾器，但我們應用端是個集群，需要解決一些分布式數據一致性的問題，作罷。
其實我們redis的具體存儲實現和上文描述略有差異，為了不喧賓奪主上文特意對實際實現做了簡化描述，所以最終實際沒有省一半以上的內存，只省了35%左右。
最終400G+優化後能減少100多G的內存，其實也就是一台伺服器，即便放到未來也就是少擴容幾台伺服器。對公司而言就是每個月節省幾千的成本，我司這種大廠其實是不會在乎這點錢的。不過即便這幾千的成本最終不會轉化成我的工資或者獎金，但像這種優化該做還是得做。如果每個人都本著 用最低的成本做同樣事 的原則去做好每一件事，就我司這體量，一個月上千萬的成本還是能省下來的。