1. 7

  2. 2

    I guess I can’t do bulk insertion with this as with bloom filters. (Add 1000 elements to a fresh bloom filter, then OR that one on top of the one I want to insert into.) Also, bloom filters increase their failure rate with more insertions, this data structure fails instead.

    An interesting variation of bloom filters to touch fewer cache lines is used in some ELF files: https://blogs.oracle.com/ali/gnu-hash-elf-sections

    Visualization for bloom filters: https://www.jasondavies.com/bloomfilter/

    Visualization for cuckoo hashing: http://www.lkozma.net/cuckoo_hashing_visualization/ (just imagine the two arrays are actually just one)

    1. 1

      And I went through all that time writing a bloom filter implementation.