Editing Binary search (section)

=== Set membership algorithms ===
A related problem to search is [[Set (abstract data type)|set membership]]. Any algorithm that does lookup, like binary search, can also be used for set membership. There are other algorithms that are more specifically suited for set membership. A [[bit array]] is the simplest, useful when the range of keys is limited. It compactly stores a collection of [[bit]]s, with each bit representing a single key within the range of keys. Bit arrays are very fast, requiring only <math display="inline">O(1)</math> time.{{Sfn|Knuth|2011|loc=§7.1.3 ("Bitwise Tricks and Techniques")}}  The Judy1 type of [[Judy array]] handles 64-bit keys efficiently.<ref name="judyarray">{{Citation|last1=Silverstein|first1=Alan|title=Judy IV shop manual|publisher=[[Hewlett-Packard]]|url=http://judy.sourceforge.net/doc/shop_interm.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://judy.sourceforge.net/doc/shop_interm.pdf |archive-date=2022-10-09 |url-status=live|pages=80–81}}</ref>

For approximate results, [[Bloom filter]]s, another probabilistic data structure based on hashing, store a [[set (mathematics)|set]] of keys by encoding the keys using a [[bit array]] and multiple hash functions. Bloom filters are much more space-efficient than bit arrays in most cases and not much slower: with <math display="inline">k</math> hash functions, membership queries require only <math display="inline">O(k)</math> time. However, Bloom filters suffer from [[False positives and false negatives|false positives]].{{Efn|This is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.<ref name="cuckoofilter">{{cite conference|last1=Fan|first1=Bin|last2=Andersen|first2=Dave G.|last3=Kaminsky|first3=Michael|last4=Mitzenmacher|first4=Michael D.|title=Cuckoo filter: practically better than Bloom|conference=Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies|date=2014|pages=75–88|doi=10.1145/2674005.2674994|doi-access=free}}</ref>}}{{Efn|There exist improvements of the Bloom filter which improve on its complexity or support deletion; for example, the cuckoo filter exploits [[cuckoo hashing]] to gain these advantages.<ref name="cuckoofilter" />}}<ref>{{cite journal|last1=Bloom|first1=Burton H.|s2cid=7931252|title=Space/time trade-offs in hash coding with allowable errors|journal=[[Communications of the ACM]]|date=1970|volume=13|issue=7|pages=422–426|doi=10.1145/362686.362692|df=dmy-all|citeseerx=10.1.1.641.9096}}</ref>