Salt for hash computations.

Choosing good hash functions is imperative for a good performance of a cuckoo filter. The hash functions must be

• independent and
• provide good uniformity on the lower bits of the output.

The default implementations use sip hash for cuckooHash and fnv1a (64 bit) for cuckooFingerprint.

Computes a Sip hash for a value that has an Storable instance.

The first argument is a salt value that is used to derive the key for the hash computation.

Computes a Sip hash for a value that is an instance of ByteArrayAccess.

The first argument is a salt value that is used to derive the key for the hash computation.

Computes a 64 bit Fnv1a hash for a value that has an Storable instance.

The first argument is use as a salt.

Computes a 64 bit Fnv1a hash for a value that is an instance of ByteArrayAccess.

The first argument is use as a salt.

Cuckoo Filter with

• State token s :: Type,
• bucket size b :: Nat,
• fingerprint size f :: Nat, and
• content type a :: Type.

The following constraints apply

• \(0 < f \leq 32\)
• \(0 < b\)

The implementation is not thread safe. For concurrent use the filter must be wrapped in a read-write lock.

Cuckoo filter that can be used in the IO monad.

Create a new Cuckoo filter that has at least the given capacity.

The type parameters are

• bucket size b :: Nat,
• fingerprint size f :: Nat,
• content type a :: Type, and
• Monad m :: Type -> Type,

Enabling the TypeApplications language extension provides a convenient way for passing the type parameters to the function.

The following constraints apply:

• \(0 < f \leq 32\),
• \(0 < b\).

The false positive rate depends mostly on the value of f. It is bounded from above by \(\frac{2b}{2^f}\). In most cases 4 is a good choice for b.

Actual performance depends on the choice of good hash functions that provide high uniformity on the lower bits.

The actual capacity may be much larger than what is requested, because the actual bucket count is a power of two.

Insert an item into the filter and return whether the operation was successful. If insertion fails, the filter is unchanged.

This function is not thread safe. No concurrent writes or reads should occur while this function is executed. If this is needed a lock must be used.

This function is not exception safe. The filter must not be used any more after an asynchronous exception has been throw during the computation of this function. If this function is used in the presence of asynchronous exceptions it should be apprioriately masked.

Test whether an item is in the set that is represented by the Cuckoo filter.

A negative result means that the item is definitively not in the set. A positive result means that the item is most likely in the set. The rate of false positives is bounded from above by \(\frac{2b}{2^f}\) where b is the number of items per bucket and f is the size of a fingerprint in bits.

Delete an items from the filter.

IMPORTANT An item must only be deleted if it was successfully added to the filter before (and hasn't been deleted since then).

Deleting an item that isn't in the filter will result in the filter returning false negative results.

This function is not thread safe. No concurrent writes must occur while this function is executed. If this is needed a lock must be used. Concurrent reads are fine.

The total number of bytes allocated for storing items in the filter.

Total number of items that the filter can hold. In practice a load factor of ~95% of this number can be reached.

Number of items currently stored in the filter.

Note that computing this number is expensive \(\mathcal{O}(n)\).

The current load factor of the filter in percent.

loadFactor f = 100 * itemCount f / capacityInItems

Note that computing this number is expensive \(\mathcal{O}(n)\).

Show the contents of the filter as a list of buckets with values show in hex. Used for debugging purposes.

Returns the different hashes that are associated with an item in the filter. Used for debugging purposes.