Module hash4j
Package com.dynatrace.hash4j.consistent

Class ConsistentHashing

java.lang.Object
com.dynatrace.hash4j.consistent.ConsistentHashing
public final class ConsistentHashing extends Object
Consistent hash algorithms.

  • Method Details

    • jumpHash

      public static ConsistentBucketHasher jumpHash(PseudoRandomGeneratorProvider pseudoRandomGeneratorProvider)
      Returns a ConsistentBucketHasher.

      This algorithm is based on Lamping, John, and Eric Veach. "A fast, minimal memory, consistent hash algorithm." arXiv preprint arXiv:1406.2294 (2014).

      The average computation time depends logarithmically on the number of buckets.

      Parameters:
      pseudoRandomGeneratorProvider - a PseudoRandomGeneratorProvider
      Returns:
      a ConsistentBucketHasher

    • improvedConsistentWeightedSampling

      public static ConsistentBucketHasher improvedConsistentWeightedSampling(PseudoRandomGeneratorProvider pseudoRandomGeneratorProvider)
      Returns a ConsistentBucketHasher.

      This algorithm is based on the method described in Sergey Ioffe, "Improved Consistent Sampling, Weighted Minhash and L1 Sketching," 2010, doi: 10.1109/ICDM.2010.80. which is applied to a one-dimensional input vector whose value is equal to the number of buckets.

      The computation time is constant independent of the number of buckets. This method is faster than jumpHash(PseudoRandomGeneratorProvider) for large number of buckets.

      Parameters:
      pseudoRandomGeneratorProvider - a PseudoRandomGeneratorProvider
      Returns:
      a ConsistentBucketHasher

    • jumpBackHash

      public static ConsistentBucketHasher jumpBackHash(PseudoRandomGeneratorProvider pseudoRandomGeneratorProvider)
      Returns a ConsistentBucketHasher.

      In contrast to other algorithms, JumpBackHash runs in constant time and does not require floating-point operations. On some machines it may achieve similar performance as a modulo operation. See Ertl, Otmar. "JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets." Software: Practice and Experience 55.3 (2025)., 10.1002/spe.3385.

      Parameters:
      pseudoRandomGeneratorProvider - a PseudoRandomGeneratorProvider
      Returns:
      a ConsistentBucketHasher

    • jumpBackAnchorHash

      public static ConsistentBucketSetHasher jumpBackAnchorHash(PseudoRandomGeneratorProvider pseudoRandomGeneratorProvider)
      Returns a ConsistentBucketSetHasher.

      This implementation combines ideas from multiple papers:

      • AnchorHash: Mendelson, Gal, et al. "Anchorhash: A scalable consistent hash." IEEE/ACM Transactions on networking 29.2 (2020), 10.1109/TNET.2020.3039547
      • MementoHash: Coluzzi, Massimo, et al. "MementoHash: a stateful, minimal memory, best performing consistent hash algorithm." IEEE/ACM Transactions on Networking (2024), 10.1109/TNET.2024.3393476
      • JumpBackHash: Ertl, Otmar. "JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets." Software: Practice and Experience 55.3 (2025), 10.1002/spe.3385.

      This algorithm is based on the memory-optimized version of AnchorHash.

      In case of random bucket removals, the expected lookup time has a complexity of O(1 + ln^2(n_max / n)) where n is the current number of buckets and n_max is the maximum number of buckets in the history of this ConsistentBucketSetHasher. However, for particular (non-random) bucket removal orders the expected lookup time complexity can be O(n_max / n). For example, adding n_max buckets, followed by removing n_max-1 buckets with IDs 0, n_max-1, n_max-2, n_max-3, ..., 3, 2 in that order would result in an expected worst-case time complexity of O(n_max).

      The in-memory space scales linearly with the maximum number of buckets n_max. However, the state, that can be obtained via ConsistentBucketSetHasher.getState(), takes 4 * (n_max - n + 1) bytes, scaling only linearly with the number of removed buckets given by n_max - n.

      In contrast to AnchorHash, this implementation dynamically adapts to any number of buckets using JumpBackHash. Compared to AnchorHash and MementoHash, this implementation does not require a family of hash functions, as it only requires a simple random sequence. Compared to MementoHash, it has a better time complexity with respect to n_max/n which is important when many buckets are removed.

      Parameters:
      pseudoRandomGeneratorProvider - a PseudoRandomGeneratorProvider
      Returns:
      a ConsistentBucketHasher