A Java & C implementation of the FlipHash algorithm from the research paper by Charles Masson & Homin K. Lee.
Title: FlipHash: A Constant-Time Consistent Range-Hashing Algorithm
Authors: Charles Masson, Homin K. Lee
Published: arXiv:2402.17549 [cs.DS] — February 27, 2024
DOI: 10.48550/arXiv.2402.17549
Full Paper: arxiv.org/abs/2402.17549
Consistent range-hashing is a foundational technique in distributed systems. It assigns keys (requests, data chunks, user IDs) to one of N numbered resources (servers, cache nodes, shards) such that:
- Keys are evenly distributed across all N resources
- When N changes (a server is added or removed), only the minimum required keys are remapped — no unnecessary reshuffling occurs
FlipHash solves this with O(1) constant-time complexity — beating the widely-used Jump Consistent Hash which runs in O(log N).
- Load balancers routing HTTP requests to backend servers
- Distributed caches (like Memcached clusters) assigning keys to nodes
- Sharded databases mapping records to shards
- Content delivery networks routing assets to edge servers
FlipHash is composed of two functions: fliphashPow2 for power-of-2 resource counts and fliphashGeneral for any arbitrary N.
All hash calls use a two-dimensional seed:
seed(a, b) = a + (b << 16)
This lets the algorithm derive multiple independent hash values for the same key without storing state, simply by varying a and b.
Maps a key to range [0, 2^r) consistently:
1. a = H(key, seed(0, 0)) mod 2^r
↓
2. b = ⌊log₂(a)⌋ ← position of highest set bit in a
↓
3. c = H(key, seed(b, 0)) mod 2^b
↓
4. return a + c
Intuition: a falls in the range [2^b, 2^(b+1)). Adding c ∈ [0, 2^b) fills in all buckets in [2^b, 2^(b+1) + 2^b) uniformly. The second hash ensures that when N shrinks or grows, keys are remapped predictably.
Java code from FlipHash.java:
private static long fliphashPow2(String key, int twoPower) {
Hasher64 xxh3 = XXH3_64.create(seeding((short) 0, (short) 0));
long a = xxh3.hashCharsToLong(key) & ((1L << twoPower) - 1); // a mod 2^r
long temp = a; int b = 0;
while (temp > 1) { temp >>= 1; b++; } // b = floor(log₂(a))
xxh3 = XXH3_64.create(seeding((short) b, (short) 0));
long c = xxh3.hashCharsToLong(key) & ((1L << b) - 1); // c mod 2^b
return a + c;
}Handles any arbitrary N using fliphashPow2 as a building block:
1. r = ceil(log₂(N)) ← smallest r with 2^r ≥ N
↓
2. d = fliphashPow2(key, r)
↓
3. d < N? → return d ← direct hit ✅
↓
4. d ≥ N (forbidden zone [N, 2^r)):
For i = 0 → 63:
e = H(key, seed(r-1, i)) mod 2^r
e < 2^(r-1) → return fliphashPow2(key, r-1) ← "flip down" 🔃
e < N → return e ← remap to valid zone ✅
↓
5. Fallback: return fliphashPow2(key, r-1)
The "flip" insight: When a key lands in the forbidden zone [N, 2^r), the algorithm flips it either down to [0, 2^(r-1)) or maps it directly to the valid upper zone [2^(r-1), N). This is the namesake operation that gives FlipHash its O(1) complexity — no iteration over the full N range.
Java code from FlipHash.java:
public static long fliphashGeneral(String key, Resource resource) {
long N = resource.count;
int r = 0;
for (long temp = N; temp > 0; temp >>= 1) { r++; } // r = ⌈log₂(N)⌉
long d = fliphashPow2(key, r);
if (d < N) return d; // direct hit
long halfRange = 1L << (r - 1); // 2^(r-1)
for (int i = 0; i < 64; i++) {
Hasher64 xxh3 = XXH3_64.create(seeding((short)(r-1), (short)i));
long e = xxh3.hashCharsToLong(key) & ((1L << r) - 1);
if (e < halfRange) return fliphashPow2(key, r - 1); // flip down
if (e < N) return e; // remap
}
return fliphashPow2(key, r - 1); // fallback
}| Property | Jump Consistent Hash | FlipHash |
|---|---|---|
| Time Complexity | O(log N) | O(1) |
| Memory | O(1) | O(1) |
| Even distribution | ✅ | ✅ |
| Minimal remapping on change | ✅ | ✅ |
| Sequential resource indexing | Required | Required |
| Speed at large N | Slower | Faster |
From the paper: "FlipHash beats Jump Consistent Hash's cost both theoretically and in experiments over practical settings."
FlipHash-main/
├── Java implementation/ # Full Java implementation with load balancer simulation
│ └── fliphash/ # Core package: FlipHash algorithm + server/client demo
├── C implementation./ # C implementation of the FlipHash algorithm
├── Final Submission/ # Final academic project submission package
├── Jar files/ # Precompiled standalone JAR files
├── Client.java # Standalone client entrypoint
└── README.md # This file
cd "Java implementation/fliphash"
# Compile
javac -cp ".:jna-5.13.0.jar:oshi-core-6.3.0.jar:slf4j-api-2.0.9.jar:slf4j-simple-2.0.9.jar" *.java
# Run the core algorithm
java -cp ".:jna-5.13.0.jar:oshi-core-6.3.0.jar:slf4j-api-2.0.9.jar:slf4j-simple-2.0.9.jar" fliphash.FlipHashOn Windows replace
:with;in the classpath.
cd "C implementation."
make
./onlyfliphashAuthors: Charles Masson & Homin K. Lee
Paper: FlipHash: A Constant-Time Consistent Range-Hashing Algorithm
arXiv: arXiv:2402.17549 [cs.DS]
This implementation is based directly on the algorithm described in this paper.
Author: Yann Collet
Repository: github.com/Cyan4973/xxHash
The XXH3-64 hash function is used as the underlying hash primitive in all FlipHash operations.
Repository: github.com/oshi/oshi
Used for real-time CPU and memory monitoring in the load balancer demonstration.
Repository: github.com/java-native-access/jna
Enables the Java implementation to interface with native system libraries.
Implemented by Prabin Kumar Sabat
Based on research by Charles Masson & Homin K. Lee
📬 Connect with me
Sri Sathya Sai Institute of Higher Learning
Prasanthi Nilayam (Puttaparthi) — Department of Mathematics and Computer Science