[infinispan-dev] Hash calculation in DefaultConsistentHash

[Manik Surtani]

On 1 Oct 2009, at 13:38, Krzysztof Sobolewski wrote:

> Dnia czwartek 01 październik 2009 o 14:25:11 Manik Surtani napisał(a):
>
>> 2.  The use of the entire range of ints on the number line.  I can  
>> see
>> the benefits here (removal of the mod and abs functions in my impl),
>> but this greatly increases the range of numbers to scan.  Granted a
>> binary search is fast - O (log n) - but still such a massive number
>> range is unnecessary given that, even at a push (for now anyway),  
>> we'd
>> see 10,000 servers in a cluster?  :-)
>
> Well, doing it on the whole range instead on half of it would  
> increase lookup
> time by O(1). Or, exactly by one iteration. At most.
> But that's moot anyway, because the n in O(log n) is not the size of  
> search
> space (it's 2 billion in your current impl.), it's the number of  
> items we care
> about, that is number of nodes. At least that's how I understand it :)

D'oh, of course - I need more coffee.  :-)

--
Manik Surtani
manik at jboss.org
Lead, Infinispan
Lead, JBoss Cache
http://www.infinispan.org
http://www.jbosscache.org