布隆过滤器

布隆过滤器（英語：Bloom Filter）是1970年由伯頓·霍華德·布隆（Burton Howard Bloom）提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

基本概念

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为。

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。所以布隆过滤器可能会产生假阳性（误报），但不会产生假阴性（漏报）。

这里有一个布隆过滤器可视化页面，提供了多种操作布隆过滤器的方式。可以通过输入框添加单个元素，只需在输入框中输入想要添加的字符串，然后点击"添加"按钮，系统就会将该元素加入过滤器中。添加成功后，您可以在位数组上观察到对应位置被标记为绿色，直观地展示了元素的存储位置。

优点

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

和相同，使用同一组散列函数的两个布隆过滤器的交并[來源請求]运算可以使用位操作进行。

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

外部链接

Read other articles:

Un Dia Normal

Un Día NormalAlbum studio karya JuanesDirilis21 Mei 2002DirekamLos Angeles, KaliforniaJanuari – Maret 2002GenreRock latinDurasi42:40LabelUniversal Music LatinoProduserJuanesAnibal KerpelGustavo SantaolallaMelissa MatteyKronologi Juanes Fijate Bien(2000)Fijate Bien2000 Un Día Normal (2002) Mi Sangre (2004)Mi Sangre2004 Un Dia Normal (Indonesia: Sebuah Hari Biasa) adalah album yang kedua dirilis oleh penyanyi musik Latin asal Kolombia, Juanes. Album ini dirilis pada 21 Mei 2002. Album i...

 

 

Lucky Hakim

Lucky Hakim Wakil Bupati Indramayu ke-6Masa jabatan26 Februari 2021 – 13 Februari 2023GubernurRidwan KamilBupatiNina Agustina PendahuluTaufik HidayatPenggantiPetahanaAnggota Dewan Perwakilan RakyatRepublik IndonesiaMasa jabatan1 Oktober 2014 – 3 Juli 2018 PenggantiIntan Fitriana FauziDaerah pemilihanJawa Barat VI Informasi pribadiLahirLucky Hakim12 Januari 1978 (umur 46)Cilacap, Jawa Tengah, IndonesiaPartai politikNasDem (2021–sekarang)PAN (2013–2018)Suami/i...

 

 

PKS 1302-102

PKS 1302-102Observation data (Epoch J2000.0)ConstellationVirgo[1]Right ascension13h 05m 33.01498s[2]Declination−10° 33′ 19.4266″[2]Redshift0.2784[1]Distance3.5×10^9 ly (1.1 Gpc)[1]TypeFSRS, FSRQ, FSQ, QSO, E4[2][1]Apparent magnitude (V)14.9[1]Other designationsPG 1302-102, PG 1302-103, ICRF J130533.0-103319, PKS 1302-102, PKS 1302-103, PKS J1305-1033, PKS B1302-102, QSO J1305-1033, QSO...

Keuskupan Sør-Hålogaland

Keuskupan Sør-HålogalandSør-Hålogaland bispedømmeGereja Norwegia Pemandangan Katedral BodøLokasiNegaraNorwegiaWilayahNordlandDekanatBodø domprosti, Lofoten, Ofoten, Vesterålen, Salten, Nord-Helgeland, Indre Helgeland, Sør-HelgelandStatistikParoki96Umat198,420InformasiDenominasiGereja NorwegiaPendirian1952KatedralKatedral BodøKepemimpinan kiniUskupAnn-Helen Fjeldstad JusnesPetaLokasi Keuskupan Sør-HålogalandSitus webhttp://www.kirken.no/sor-haalogalandReferensi[1] Sør...

 

 

Boretto

Questa voce o sezione sull'argomento centri abitati dell'Emilia-Romagna non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Borettocomune Boretto – VedutaLa chiesa parrocchiale di San Marco LocalizzazioneStato Italia Regione Emilia-Romagna Provincia Reggio Emilia AmministrazioneSindacoMatteo Benassi (lista civica di centro-sinistra) da...

 

 

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

Panīpeirōtikos Athlītikos Syllogos Giannina

Questa voce o sezione sull'argomento società calcistiche greche non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. PAS GianninaCalcio Ajax dell'Epiro Segni distintivi Uniformi di gara Casa Trasferta Terza divisa Colori sociali Bianco · blu Inno ΠΑΣ ΠΑΣ Γιάννινα (PAS PAS Giannina)Kitsakis Alekos Dati societari Città Giannina Nazione ...

 

 

Sector mass spectrometer

Class of mass spectrometer This article is about mass spectrometers. For sector compasses, see sector (instrument). A five sector mass spectrometer A sector instrument is a general term for a class of mass spectrometer that uses a static electric (E) or magnetic (B) sector or some combination of the two (separately in space) as a mass analyzer.[1] Popular combinations of these sectors have been the EB, BE (of so-called reverse geometry), three-sector BEB and four-sector EBEB (electric...

 

 

Villa Borghese

Disambiguazione – Se stai cercando altri significati, vedi Villa Borghese (disambigua). Villa BorgheseL'ingresso monumentale su piazzale Flaminio UbicazioneStato Italia LocalitàRoma CaratteristicheTipoVilla, parco storico[1] Superficie80 ettari Inaugurazione1903 GestoreRoma Capitale AperturaTutti i giorni dall'alba al tramonto Ingressiv. U. Aldrovandiv. A. Raimondi(2 ingressi)v. di Porta Pinciana (2 ingressi)P.le S. Paolo del Brasilep.le Flaminiop.le Cervantesp.le P. Picasso(...

Loyalism

Allegiance to the British crown or the United Kingdom Loyalist redirects here. For other uses, see Loyalist (disambiguation). Loyalism, in the United Kingdom, its overseas territories and its former colonies, refers to the allegiance to the British crown or the United Kingdom. In North America, the most common usage of the term refers to loyalty to the British Crown, notably with the loyalists opponents of the American Revolution, and United Empire Loyalists who moved to other colonies in Bri...

 

 

Longze station

Beijing Subway station Longze龙泽PlatformGeneral informationLocationHuilongguan Subdistrict, Changping District, BeijingChinaCoordinates40°04′15″N 116°19′09″E / 40.0709°N 116.3193°E / 40.0709; 116.3193Operated byBeijing Mass Transit Railway Operation Corporation LimitedLine(s)     Line 13Platforms2 (2 side platforms)Tracks2ConstructionStructure typeElevatedAccessibleYesOther informationStation code1307HistoryOpenedSeptember ...

 

 

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Франц (герцог Саксен-Кобург-Заальфельдский)

Франц Саксен-Кобург-Заальфельдскийнем. Franz von Sachsen-Coburg-Saalfeld герцог Саксен-Кобург-Заальфельдский 8 сентября 1800 — 9 декабря 1806 Предшественник Эрнст Фридрих Саксен-Кобург-Заальфельдский Преемник Эрнст I Саксен-Кобург-Заальфельдский Рождение 15 июля 1750(1750-07-15)Кобург, Сакс...

 

 

Pittosporaceae

Family of flowering plants Pittosporaceae Hōʻawa (Pittosporum confertiflorum) Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Clade: Asterids Order: Apiales Family: PittosporaceaeR.Br.[1][2] Genera See text. Diversity 9 genera[3] Pittosporaceae is a family of flowering plants that consists of 200–240 species of trees, shrubs, and lianas in 9 genera.[4] Habitats range from tropical to temperate climates of t...

 

 

乌克兰总理

 烏克蘭總理Прем'єр-міністр України烏克蘭國徽現任杰尼斯·什米加尔自2020年3月4日任命者烏克蘭總統任期總統任命首任維托爾德·福金设立1991年11月后继职位無网站www.kmu.gov.ua/control/en/（英文） 乌克兰 乌克兰政府与政治系列条目 宪法 政府 总统 弗拉基米尔·泽连斯基 總統辦公室 国家安全与国防事务委员会 总统代表（英语：Representatives of the President of Ukraine） 总...

Ancient Roman philosophy

Philosophy in the Roman world, influenced by Hellenistic philosophy Roman philosophy redirects here. For philosophy in (lands descended from) the Western Roman Empire, see Latin philosophy (disambiguation). For philosophy in the Eastern Roman Empire, see Byzantine philosophy. Part of a series onPhilosophy Philosophy portal Contents Outline Lists Glossary History Categories Disambiguation Philosophies By period Ancient Ancient Egyptian Ancient Greek Medieval Renaissance Modern Contemporary...

 

 

Glenn Miller

American big band musician (1904–1944) This article is about the swing musician. For other uses, see Glenn Miller (disambiguation). Glenn MillerMiller c. 1942BornAlton Glen Miller(1904-03-01)March 1, 1904Clarinda, Iowa, U.S.DisappearedDecember 15, 1944 (aged 40)over English ChannelStatusDeclared dead in absentiaDecember 16, 1945(1945-12-16) (aged 41)Spouse Helen Burger ​(m. 1928)​Children2Musical careerGenresSwing music, big bandOccupation(s)Band...

 

 

Olympic Air

Olympic Air IATA ICAO Kode panggil OA OAL OLYMPIC Didirikan2009Mulai beroperasi29 September 2009PenghubungBandar Udara Internasional Eleftherios VenizelosPenghubung sekunder Bandar Udara Internasional Thessaloniki, Macedonia Bandar Udara Internasional Rhodes, Diagoras Program penumpang setiaTravelair Club[1]Anak perusahaanMacedonian AirlinesArmada33 (+2 pesanan)Tujuan47SloganΗ Ελλάδα Ψηλά - Greece, flying high[2]Perusahaan indukMarfin Investment GroupKantor pusatKor...

Secular Order of Discalced Carmelites

Third order of Catholic lay persons Secular Order of Discalced CarmelitesOrdo Carmelitarum Discalceatorum SaecularisCoat of arms of the orderAbbreviationOCDSFormation1452; 572 years ago (1452)FounderJohn SorethTypeThird orderHeadquartersCasa Generalizia dei Carmelitani Scalzi, Corso d’Italia 38, 00198 Rome, ItalyAffiliationsDiscalced CarmelitesWebsitewww.carmelitaniscalzi.com/en/ The Secular Order of Discalced Carmelites (Latin: Ordo Carmelitarum Discalceatorum Saecularis;...

 

 

'Til Death Do Us Part: Carmen and Dave

American reality tv series (2004) 'Til Death Do Us Part: Carmen and DaveLogo for 'Til Death Do Us Part: Carmen and DaveStarring Carmen Electra Dave Navarro Country of originUnited StatesNo. of episodes7ProductionRunning timeapproximately 20 minutes (per episode)Original releaseNetworkMTVRelease21 January (2004-01-21) –3 March 2004 (2004-03-03) 'Til Death Do Us Part: Carmen and Dave (often written 'Til Death Do Us Part: Carmen + Dave or 'Til Death Do Us Part: C...