Problema che sto cercando di risolvere, mi scuso in anticipo per la lunghezza:
Dato un gran numero di record archiviati, ognuno con un campo (String) unico S. Mi piacerebbe poter trovare attraverso una query indicizzata tutti i record dove Hash (S)% N == K per qualsiasi N arbitrario , K (ad esempio, dato un milione di stringhe, trova tutte le stringhe in cui HashCode (s)% 17 = 5. Esiste un modo di memoizzarlo per poter rispondere rapidamente a qualsiasi domanda di questo modulo senza fare la% su ogni valore?
La motivazione per questo è un sistema di N nodi distribuiti, in cui ogni record deve essere assegnato ad almeno un nodo. I nodi sono numerati 0 - (K-1) e ogni nodo deve caricare tutti i record che corrispondono al suo numero:
Se abbiamo 3 nodi
- Il nodo 0 carica tutti i record in cui Hash% 3 == 0
- Il nodo 1 carica tutti i record in cui Hash% 3 == 1
- Il nodo 2 carica tutti i record in cui Hash% 3 == 2
aggiungendo un quarto nodo, ovviamente tutti i compiti devono essere ricalcolati -
- Il nodo 0 carica tutti i record in cui Hash% 4 == 0
- ...
- etc
Mi piacerebbe trovare facilmente questi record attraverso una query indicizzata senza dover calcolare singolarmente la mod.
Il meglio che ho potuto fare finora:
Se prendiamo i fattori primi di N (p1 * p2 * ...)
se N% M == I allora p% M == I% p per tutti i fattori primi di N
es. 10 nodi:
N% 10 == 6 quindi
- N% 2 = 0 == 6% 2
- N% 5 = 1 == 6% 5
quindi l'archiviazione di un array di "%" di N per il primo numero "ragionevole" di numeri primi del mio set di dati dovrebbe essere utile. Ad esempio nell'esempio precedente memorizziamo l'hash e i primi
HASH PRIMES (array di% 2,% 3,% 5,% 7, ...])
16 [0 1 1 2 ..]
quindi cercare N% 10 == 6 equivale a cercare tutti i valori dove array [1] == 1 e array [2] == 1.
Tuttavia, questo si rompe al primo primo più grande del numero più alto che sto memorizzando nella tabella dei fattori. Esiste un modo migliore?