HBase学习笔记（三）——布隆过滤器(Bloom Filter)的原理
生活随笔
收集整理的這篇文章主要介紹了
HBase学习笔记（三）——布隆过滤器(Bloom Filter)的原理
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
文章目錄
- 布隆過(guò)濾器介紹
- 布隆過(guò)濾器原理
- 布隆過(guò)濾器的優(yōu)缺點(diǎn)與用途
- 布隆過(guò)濾器使用場(chǎng)景
布隆過(guò)濾器介紹
????布隆過(guò)濾器（Bloom Filter）由 Burton Howard Bloom 在 1970 年提出，是一種空間效率高的概率型數(shù)據(jù)結(jié)構(gòu)。它專門用來(lái)檢測(cè)集合中是否存在特定的元素。
布隆過(guò)濾器帶有以下特點(diǎn)：
- 一個(gè)很長(zhǎng)的二進(jìn)制向量（位數(shù)組）
- 一系列隨機(jī)函數(shù)（哈希）
- 空間效率和查詢效率高
- 有一定的誤判率（哈希表是精確匹配）
布隆過(guò)濾器原理
布隆過(guò)濾器（Bloom Filter）的核心是實(shí)現(xiàn)一個(gè)超大的位數(shù)組和幾個(gè)哈希函數(shù)。
????假設(shè)位數(shù)組的長(zhǎng)度為m，哈希函數(shù)的個(gè)數(shù)為k，以上圖為例。
具體操作流程如下：
布隆過(guò)濾器添加元素
- 將要添加的元素給k個(gè)哈希函數(shù)
- 得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置
- 將這k個(gè)位置設(shè)為1
布隆過(guò)濾器查詢?cè)?/strong>
- 將要查詢的元素給k個(gè)哈希函數(shù)
- 得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置
- 如果k個(gè)位置有一個(gè)為0，則肯定不在集合中
- 如果k個(gè)位置全部為1，則可能在集合中
布隆過(guò)濾器的優(yōu)缺點(diǎn)與用途
優(yōu)點(diǎn)
- 不需要存儲(chǔ)數(shù)據(jù)本身，只用比特表示，因此空間占用相對(duì)于傳統(tǒng)方式有巨大的優(yōu)勢(shì)，并且能夠保密數(shù)據(jù)；
- 時(shí)間效率也較高，插入和查詢的時(shí)間復(fù)雜度均為O(k)；
- 哈希函數(shù)之間相互獨(dú)立，可以在硬件指令層面并行計(jì)算。
缺點(diǎn)
- 存在假陽(yáng)性的概率，不適用于任何要求 100% 準(zhǔn)確率的場(chǎng)景；
- 只能插入和查詢?cè)?#xff0c;不能刪除元素，這與產(chǎn)生假陽(yáng)性的原因是相同的。我們可以簡(jiǎn)單地想到通過(guò)計(jì)數(shù)（即將一個(gè)比特?cái)U(kuò)展為計(jì)數(shù)值）來(lái)記錄元素?cái)?shù)，但仍然無(wú)法保證刪除的元素一定在集合中。
????所以，Bloom Filter 在對(duì)查準(zhǔn)度要求沒(méi)有那么苛刻，而對(duì)時(shí)間、空間效率要求較高的場(chǎng)合非常合適，本文第一句話提到的用途即屬于此類。另外，由于它不存在 假陰性 問(wèn)題，所以用作“不存在”邏輯的處理時(shí)有奇效，比如可以用來(lái)作為 緩存系統(tǒng)（如Redis）的緩沖，防止緩存穿透。
布隆過(guò)濾器使用場(chǎng)景
總結(jié)
以上是生活随笔為你收集整理的HBase学习笔记（三）——布隆过滤器(Bloom Filter)的原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 单片机基础知识点 05 （中断-1）
- 下一篇： 螺孔视觉定位|螺丝孔视觉定位|孔视觉定位