Hashing.consistentHash() algorithm

[David Wahler]

Hi,

I'm curious about the design of the Hashing.consistentHash() method. It's a clever but fairly cryptic piece of code. Is there a paper or something that describes how it was derived? 

The Javadoc refers to the Wikipedia article on consistent hashing, but Guava's implementation doesn't really resemble the standard approach described there, or in any of the cited references. It seems to use an implicitly n-dimensional space of hash values instead of a unit circle, which makes it much harder to visualize. I'm also curious about the expected running time; empirically, it looks highly sublinear (logarithmic?), but I haven't been able to prove a rigorous bound.

Also, is it likely that the weightedConsistentHash() functionality will eventually be open-sourced? I've seen it referenced on Stack Overflow [1] and in the Guava tests/Javadoc [2], and it seems like it would make a really useful addition to the library. As Chris Povirk points out, consistentHash() isn't all that useful at the moment, because buckets can only be added or removed at the end of the list.

Thanks,

-- David

[1]: http://stackoverflow.com/a/12320186/183802

[2]: https://code.google.com/p/guava-libraries/source/browse/guava-tests/test/com/google/common/hash/HashingTest.java?r=f44ab11f78a1b9f86bb37de45bb6dfb1e0516507#209

[Kurt Alfred Kluever]

Hi David,

The authors of the original C++ code from which this originally was ported are in the process of releasing a technical report about it's design. I'll update this thread once it's released (which I have been told is "real soon").

Thanks for your patience!

--
--
guava-...@googlegroups.com
Project site: http://guava-libraries.googlecode.com
This group: http://groups.google.com/group/guava-discuss
 
This list is for general discussion.
To report an issue: http://code.google.com/p/guava-libraries/issues/entry
To get help: http://stackoverflow.com/questions/ask (use the tag "guava")
---
You received this message because you are subscribed to the Google Groups "guava-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to guava-discus...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/guava-discuss/c0c00a03-4df9-4a32-bc3b-f4fc4875667d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
kak

[Kurt Alfred Kluever]

Hi again David,

The paper about is now available externally.  Here is a link to it:

Abstract and download link:  http://arxiv.org/abs/1406.2294

Direct link to PDF:  http://arxiv.org/pdf/1406.2294v1

Hope this helps!