Algorithmic problem - quickly finding all #'s where value %x is some given value

Question

Problem I'm trying to solve, apologies in advance for the length:

Given a large number of stored records, each with a unique (String) field S. I'd like to be able to find through an indexed query all records where Hash(S) % N == K for any arbitrary N, K (e.g. given a million strings, find all strings where HashCode(s) % 17 = 5. Is there some way of memoizing this so that we can quickly answer any question of this form without doing the % on every value?

The motivation for this is a system of N distributed nodes, where each record has to be assigned to at least one node. The nodes are numbered 0 - (K-1) , and each node has to load up all of the records that match it's number:

If we have 3 nodes

• Node 0 loads all records where Hash % 3 ==0
• Node 1 loads all records where Hash % 3 ==1
• Node 2 loads all records where Hash % 3 ==2

adding a 4th node, obviously all the assignments have to be recomputed -

• Node 0 loads all records where Hash % 4 ==0
• ...
• etc

I'd like to easily find these records through an indexed query without having to compute the mod individually.

The best I've been able to come up with so far:

If we take the prime factors of N (p1 * p2 * ... )

if N % M == I then p % M == I % p for all of N's prime factors

e.g. 10 nodes :

N % 10 == 6 then

• N % 2 = 0 == 6 %2
• N % 5 = 1 == 6 %5

so storing an array of the "%" of N for the first "reasonable" number of primes for my data set should be helpful. For example in the above example we store the hash and the primes

HASH PRIMES (array of %2, %3, %5, %7, ... ])

16 [0 1 1 2 .. ]

so looking for N%10 == 6 is equivalent to looking for all values where array[1]==1 and array[2] == 1.

However, this breaks at the first prime larger than the highest number I'm storing in the factor table. Is there a better way?

• Sergey Kalinichenko: You may get a better luck on math.stackexchange.com. You may need to re-phrase this a bit to bridge the gap between CS and Math.
• PhD: Agreed - the fact that it's an "algorithm" doesn't necessarily mean CS skills :) This is highly mathematical in nature and I second @dasblinkenlight on migrating this to math.SE
• user53019: presumably, you're doing this for load balancing of some sort. How often are you re-balancing? How often and how do the Strings change? How often does your range of nodes change? If your problem can accept some constraints (such as only allowing N nodes to range between X and Y) then some pragmatic solutions can be presented. They won't necessarily be the mathematically pure solutions, but they will still work.
• phant0m: Have I misunderstood something, or did N change its meaning throughout your question? At first, it seemed to be the number of nodes, later, it seems to represent a hash code?
• NoChance: If you data is stored in RDBMS, then the operation you are trying to avoid is very cheap using a SQL SELECT (assuming HASH(s) is a column in your table)

Answer 1

How important is it that formula be "Hash % num_machines"? This formula is used for distributed caches, like memcached. It works great until you add/remove nodes. At that point, the advice is to abandon it and use consistent hashing.

• Steve B.: Thanks for the excellent suggestion, although I didn't see an easy application of consistent hashing in this case. Suggestions for a better distribution than Hash % #machines (i.e. anything that's both fair and stable) would also be welcome.

Answer 2

Unless I've misunderstood something, your conjecture is incorrect.

If we take the prime factors of N (p1 * p2 * ... )

if N % M == I then p % M == I % p for all of N's prime factors

How did you come up with that?

Let's say N = 36 and M = 6

The prime factorization of N = 2 * 2 * 3 * 3. 36 % 6 = 0

According to your statement, the following should hold:

p % 6 = 0 % p = 0

But clearly, this is not the case: 2 % 6 = 2 != 0