Supongamos que tengo un gran número de cadenas (digamos 10 mil millones de cadenas de ~ 50 caracteres cada una). Quiero distribuir las cadenas en exactamente 10 cubos. Cada cubo debe contener alrededor del 10% de las cuerdas. Con una función hash h() que puedo hacer:Mejorar la distribución de los valores de la función hash
int bucket_for_s = h(s) % 10
Sin embargo, esto no proporciona ninguna garantía sobre la uniformidad de la distribución. Supongamos que hago lo anterior para todas las cadenas y encuentro que el 30% va al cubo 1, el 5% va al cubo 2 y así sucesivamente. Mi pregunta es:
Dada la distribución h(), ¿hay alguna forma de generar una nueva función hash h2() que distribuya las cadenas de forma más pareja?
Alternativamente, hay un proceso que puede generar una serie de funciones hash h2(), h3() ... de modo que 1: cada función hash es mejor que la anterior y 2: solo tengo que generar un cantidad razonable de funciones hash?
También debo mencionar que, desafortunadamente, no puedo simplemente dividir la entrada en 10 partes porque mi entrada está repartida entre varias máquinas. Estoy buscando una solución determinista que pueda aplicar a cada máquina por separado y obtener los mismos resultados (por lo que eventualmente "hola" iría al cubo x, sin importar en qué máquinas se almacenara).
¿Es esta una pregunta teórica? ¿O tienes datos empíricos sobre esto? Además, ¿estás usando un sistema artesanal o algo así como Hadoop? – cyroxx
Esta es una pregunta teórica que cruzó mi mente mientras pensaba en diseñar un sistema artesanal. Hasta el momento no he encontrado una respuesta para eso. – user1424934