認識布隆過濾器
不安全網頁的黑名單包含 100 億個黑名單網頁，每個網頁的 URL 最多占用 64B。 現在想要實現一種網頁過濾系統，可以根據網頁的 URL 判斷該網頁是否在黑名單上，請設計該系統。
1.該系統允許有萬分之一以下的判斷失誤率。
2.使用的額外空間不要超過 30GB。


哈希離散函數性質：
①輸入域無窮大
②輸出域有限
③當輸入同樣的參數，一定有相同的輸出值
④在不同輸入值的情況下，對于結果域中的不同輸出值出現概率相等
結果結果分布越離散，該函數性能越好


一般這種題，應該問是否可以有失誤的情況


預期樣本量，預期失誤率，選擇多少個哈希函數，輸入域無限制，十分省空間

一致性哈希算法的基本原理
工程師常使用服務器集群來設計和實現數據緩存，以下是常見的策略:
1.無論是添加、查詢還是刪除數據，都先將數據的 id 通過哈希函數轉換成一個 哈希值，記為 key。
2.如果目前機器有N臺，則計算key%N的值，這個值就是該數據所屬的機器編號，無論是添加、刪除還是查詢操作，都只在這臺機器上進行。
請分析這種緩存策略可能帶來的問題，并提出改進的方案。


解決數據遷移的壓力，便于擴容
若真實機器數量不足以體現離散的優勢，則主要思路是添加很大數量的虛擬機，并維持一個路由表，以實現一致性哈希算法的優勢 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的布隆过滤器、一致性哈希算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。