Package org.elasticsearch.common.util

Class CuckooFilter

  • All Implemented Interfaces:
    Writeable
    public class CuckooFilter
extends java.lang.Object
implements Writeable
    An approximate set membership datastructure CuckooFilters are similar to Bloom Filters in usage; values are inserted, and the Cuckoo can be asked if it has seen a particular value before. Because the structure is approximate, it can return false positives (says it has seen an item when it has not). False negatives are not possible though; if the structure says it _has not_ seen an item, that can be trusted. The filter can "saturate" at which point the map has hit it's configured load factor (or near enough that a large number of evictions are not able to find a free slot) and will refuse to accept any new insertions. NOTE: this version does not support deletions, and as such does not save duplicate fingerprints (e.g. when inserting, if the fingerprint is already present in the candidate buckets, it is not inserted). By not saving duplicates, the CuckooFilter loses the ability to delete values. But not by allowing deletions, we can save space (do not need to waste slots on duplicate fingerprints), and we do not need to worry about inserts "overflowing" a bucket because the same item has been repeated repeatedly NOTE: this CuckooFilter exposes a number of Expert APIs which assume the caller has intimate knowledge about how the algorithm works. It is recommended to use SetBackedScalingCuckooFilter instead. Based on the paper: Fan, Bin, et al. "Cuckoo filter: Practically better than bloom." Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. ACM, 2014. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

    • Method Summary

      Modifier and Type Method Description
      boolean equals​(java.lang.Object other)  
      int getCount()
      Get the number of unique items that are being tracked
      long getSizeInBytes()  
      int hashCode()  
      void writeTo​(StreamOutput out)
      Write this into the StreamOutput.

      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

    • Method Detail

      • getCount

        public int getCount()
        Get the number of unique items that are being tracked

      • getSizeInBytes

        public long getSizeInBytes()

      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object

      • equals

        public boolean equals​(java.lang.Object other)
        Overrides:
        equals in class java.lang.Object