Guava

This is a library with a fast and minimal memory-consuming hashing function also known as Jump Consistent Hash from the original work "A Fast, Minimal Memory, Consistent Hash Algorithm" by Google (see 1406.2294v1.pdf).

In comparison to the algorithm of Karger et al., jump consistent hash requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets and of evenly dividing the workload when the number of buckets changes.

Installation

Add this to your application's shard.yml:

dependencies:
  guava:
    github: creadone/guava

Then run shards install.

Usage

require "guava"

Guava.jump(7234672323_u64, 12_i32) # => 9

Tests

Data distribution

require "guava"

ary = Array.new(10){ Array.new(1){ 0 } }
values = (0_u64..1_000_000_u64).to_a

values.each do |i|
  num = Guava.jump(i, 10_i32)
  ary[num].push 0
end

ary.each_with_index do |cell, idx|
  puts [idx, cell.size]
end

Result

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 100001 | 100001 | 100022 | 100004 | 99960 | 100058 | 99945 | 100070 | 99957 | 99992 |

CPU time to call

3,6 GHz Quad-Core Intel Core i3, Mac Mini 2018

values = (0_u64..1_000_000_u64).to_a

puts Benchmark.measure {
  values.each do |i|
    Guava.jump(i, 10_i32)
  end
}

Result

| User CPU | System CPU | Sum of previous | Elapsed real time | | --------- | --------- | --------- | --------- | | 0.027966 | 0.000021 | 0.027987 | 0.028015 |

Contributing

  1. Fork it (https://github.com/creadone/guava/fork)
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create a new Pull Request

Contributors