hash4j

Similarity hashing algorithms compute hash signatures for sets, allowing you to estimate set similarity (like Jaccard similarity) without storing the original sets.

Supported algorithms:

• MinHash
• SuperMinHash
• SimHash
• FastSimHash (a bit-hack optimized SimHash implementation)

To use it, you create a SimilarityHashPolicy (e.g., using superMinHash), create a SimilarityHasher, and compute signatures using an ElementHashProvider that maps elements to long hashes.

ToLongFunction<String> stringHashFunc = s -> Hashing.komihash5_0().hashCharsToLong(s);

Set<String> setA = IntStream.range(0, 90000).mapToObj(Integer::toString).collect(toSet());
Set<String> setB = IntStream.range(0, 100000).mapToObj(Integer::toString).collect(toSet());

int numberOfComponents = 1024;
int bitsPerComponent = 1;

SimilarityHashPolicy policy = SimilarityHashing.superMinHash(numberOfComponents, bitsPerComponent);
SimilarityHasher simHasher = policy.createHasher();

byte[] signatureA = simHasher.compute(ElementHashProvider.ofCollection(setA, stringHashFunc));
byte[] signatuerB = simHasher.compute(ElementHashProvider.ofCollection(setB, stringHashFunc));

double fractionOfEqualComponents = policy.getFractionOfEqualComponents(signatureA, signatuerB);

// Estimate Jaccard similarity
double estimatedJaccardSimilarity = (fractionOfEqualComponents - Math.pow(2., -bitsPerComponent)) / (1. - Math.pow(2., -bitsPerComponent));

When using HyperLogLog for approximate distinct counting, the accuracy and memory usage are determined by the precision parameter $p$.

Memory Usage

The memory required for a HyperLogLog sketch is calculated as: 0.75 * m bytes, where m = 2^p (the number of registers).

Expected Relative Standard Error

The expected relative standard error depends on the estimator used. For $p \geq 6$ and large distinct counts, the error is approximately:

• Default estimator: $\frac{1.039}{\sqrt{m}}$
• Maximum-likelihood (ML) estimator: $\frac{1.037}{\sqrt{m}}$
• Martingale estimator: $\frac{0.833}{\sqrt{m}}$

Accuracy Notes

• Small Counts: The error is significantly smaller when the distinct count is in the order of $m$ or smaller.
• Bias: The bias is much smaller than the root-mean-square error (rmse) and can generally be neglected.
• Precision: Higher values of $p$ increase the number of registers $m$, which reduces the relative error but increases memory consumption.

For counting distinct elements in large data streams with minimal memory, hash4j provides two main algorithms:

• HyperLogLog: Uses 6-bit registers. It is highly space-efficient and supports various estimators (default, maximum-likelihood, or martingale for non-distributed streams).
• UltraLogLog: Uses 8-bit registers for faster random access and updates. It offers a significant reduction in storage factor compared to HyperLogLog.

Both algorithms feature:

• Constant-time add operations
• Allocation-free updates
• Idempotency
• Mergeability (even with different precision parameters)
• Order-independent final state

Hasher64 hasher = Hashing.komihash5_0();

// Create an UltraLogLog sketch with precision 12
UltraLogLog sketch = UltraLogLog.create(12);

sketch.add(hasher.hashCharsToLong("foo"));
sketch.add(hasher.hashCharsToLong("bar"));
sketch.add(hasher.hashCharsToLong("foo"));

double distinctCountEstimate = sketch.getDistinctCountEstimate(); // close to 2

The Hashing interface allows you to hash Java objects without first mapping them to byte arrays, which minimizes memory allocations. You can use three main approaches:

1. Hash Stream: Pass data directly into a hash stream (e.g., putInt, putLong, putString).
2. Hash Funnel: Define a HashFunnel that describes how to map an object to the hash sink.
3. Reusable Hash Stream: For allocation-free performance, reuse a pre-allocated HashStream instance by calling .reset().

class TestClass { 
    int a = 42;
    long b = 1234567890L;
    String c = "Hello world!";
}

TestClass obj = new TestClass();
var hasher = Hashing.komihash5_0();

// variant 1: hash object by passing data into a hash stream
long hash1 = hasher.hashStream().putInt(obj.a).putLong(obj.b).putString(obj.c).getAsLong();

// variant 2: hash object by defining a funnel
HashFunnel<TestClass> funnel = (o, sink) -> sink.putInt(o.a).putLong(o.b).putString(o.c);
long hash2 = hasher.hashToLong(obj, funnel);

// variant 3: allocation-free by reusing a pre-allocated hash stream instance
var hashStream = Hashing.komihash5_0().hashStream();
long hash3 = hashStream.reset().putInt(obj.a).putLong(obj.b).putString(obj.c).getAsLong();

// variant 4: allocation-free and using a funnel
long hash4 = hashStream.resetAndHashToLong(obj, funnel);