A high performance, immutable, light-weight, dependency-free, ring consistent hash library.
var nodeToWeight = new Dictionary<string, int>()
{
{ "NodeA", 100 },
{ "NodeB", 150 },
};
var hasher = ConsistentHash.Create(nodeToWeight);
var node = hasher.Hash(Guid.NewGuid());
// node = "NodeB"
// {NodeA: 100, NodeB: 150}
hasher = hasher.AddOrSet(node: "NodeA", weight: 200);
// {NodeA: 200, NodeB: 150}
hasher = hasher.AddOrSetRange(new Dictionary<string, int>() { { "NodeC", 500 }, {"NodeD", 35 } });
// {NodeA: 200, NodeB: 150, NodeC: 500, NodeD: 35}
hasher = hasher.AddOrSet(node: "NodeC", weight: 0);
// {NodeA: 200, NodeB: 150, NodeD: 35}
hasher = hasher.AddOrSet(node: "NodeD", weight: -100);
// {NodeA: 200, NodeB: 150}
// {NodeA: 200, NodeB: 150, NodeC: 500, NodeD: 35}
hasher = hasher.Remove("NodeA");
// {NodeB: 150, NodeC: 500, NodeD: 35}
hasher = hasher.Remove("NonExistingNode");
// {NodeB: 150, NodeC: 500, NodeD: 35}
hasher = hasher.RemoveRange(new[] { "NodeC", "NodeD" });
// {NodeB: 150}
- High performance - Internally uses GetHashCode and XxHash for mapping nodes to values, and RadixSort for sorting
- Deterministic - Given particular node/weight pairs, and hash key, the hash result will be identical.
- Immutable
- Handles collisions in a deterministic manner (WIP)
- Thoroughly tested
- Zero dependencies
- Super light weight
Operation | Runtime | Memory usage | Details |
---|---|---|---|
Hash | O(log(N)) | n/a | N = Number of nodes |
Construction | O(βni=0Ni) | O(βni=0Ni) | Ni = Weight defined for node i |
AddOrSetRange | O(βni=0Ni) | O(βni=0Ni) | Ni = Weight defined for node i |
RemoveRange | O(βni=0Ni) | O(βni=0Ni) | Ni = Weight defined for node i |
Update | O(βni=0Ni) | O(βni=0Ni) | Ni = Weight defined for node i |
Contains | O(1) | n/a | |
TryGetWeight | O(1) | n/a | |
Equals | O(N) | n/a | N = Number of nodes |
NOTE: Any altering call creates a new instance, so costing sum of all weights.
ConsistentHashπͺ is free and open-source software licensed under the GNU General Public License