Yo he realizado algoritmos rápidos y eficientes en cuanto a colisiones con precisamente cadenas (arrays) de pocos caracteres...
Básicamente lo que contará y bastante es el tamaño del array... así conviene dimensionarlo a un tamaño tal que se prevea que no será llenado más de x%... Cuanto más baja sea la ocupación tanta menos probabilidad de colisiones, lógicamente...
Por ejemplo supongamos que pretendes generar 32 hashes, tu array podría ser de no más de 256 elementos... lo cual supone una ocupación de 1/8 del array. Por cuestiones de evitar colisiones conviene que el valor de módulo sea un primo (como bien tienes), luego el primer primo mayor que 256 es 257... ese podría ser el módulo.
Nota que el array si no vas almacenar los hashes en memoria, no lo precisas, pero igualmente el tamaño será el módulo de la función Hash. Es decir si solo vas a calcular hashes y no vas a recuperar valores guardados...
Resolví tanto el problema de colisiones excesivas como su distribución, usando 2 primos en vez de 1, cuyo producto sean no menor que el array (el primo antes usado). Además encontré que lo más óptimo se daba cuando ambos primos eran consecutivos, así para el array previo del ejemplo de 255 valores, el par de primos 'p' y 'q' son muy válidos '17' y '19' ; 17*19=323, el par previo (13*17= 221) que no contiene la suficiente cantidad de valores...
También encontré que 2 valores (no necesariamente primos), que multiplicados entre sí arrojen un valor equivalente al módulo, eran más eficientes, que usar un solo primo, (y por supuesto que usar el valor límite del array) así por ejemplo para el mismo array de ejemplo 'p' y 'q' podrían ser '15' y '17' (15*17=255), como mejor que usar el módulo 257 (o el límite del array 255).
Aquí uno de los algoritmo que utilizo, para pequeñas cadenas de texto o arrays (nota que los valores primos dependerán pués de la cantidad máxima de valores que consideres y la ocupación máxima que uno estuviere dispuesto a utilizar, en función siempre de la memoria del equipo, etc... es decir que hay que afinar dichos parámetros a valores consecuentes):
El algoritmo está pensado también para eficiencia en velocidad, por lo cual de entrada recibe un array de bytes...
// id es el array de bytes (los caracteres de una 'key', por ejemplo)
// 'p' y 'q' son los primos, que hacne de módulo...
int = Funcion Hashing(array bytes Id() , int P , int Q )
int k As Long, j, t, h, max,n
int grupos, resto, ultimos
Constante T15 = 15
Constante T03 = 3
Constante SIZE_2_30 = ((2 ^ 30) - 1) // pensado para no superar un entero de 32 bits con signo, ni pelearse con errores de desbordamiento...
max = sizearray(Id) //tamaño del array
ultimos = (max Modulo T03)
max = (max - ultimos - 1)
// Si de seguro tus hashes no van a tener más de 15 bytes, este bloque puede ser omitido.
// Se hacen iteraciones sobre grupos de hasta 15 bytes
grupos = (max \ T15) //división entera...
Si (grupos > 0) luego
bucle para k = 0 To (max - 1 - T15) enIncrementosDe T15
// en cada ciclo se procesan 3 bytes, el bucle entero serían pués 5 iteraciones.
Hacer
t = ((Id(k + n) - n) * (Id(k + n + 1)) * (Id(k + n + 2) + (n + 2)))
h = (h + t)
n = (n + T03)
Repetir mientras (n < T15)
h = (h Modulo SIZE_2_30) // para evitar desbordamientos... el array podría ser hasta de MB. de largo...
n = 0
Siguiente
Fin si
// Cantidad de bytes que no caben en un 'grupo', es decir que no llegan a 15 bytes... pero todavía tiene más de 2 bytes...
resto = (max Modulo T15)
Si (resto > 0) luego
Hacer // el bucle 'do loop' es idéntico al previo... excepto el valor límite del bucle
t = ((Id(k + n) - n) * (Id(k + n + 1)) * (Id(k + n + 2) + (n + 2)))
h = (h + t)
n = (n + T03)
Repetir mientras (n < resto)
Fin si
// 1 ó 2 Ultimos bytes (o los únicos cuando solo haya 1 ó 2 bytes).
Si (ultimos > 0) luego
Si (ultimos = 1) luego
h = ((SIZE_2_30 - h) + Id(max-1)) // el último para evitar desbordamiento en tabla.
Sino
h = ((SIZE_2_30 - h) + (Id(max - 2) * (Id(max-1))))
Fin si
Fin si
Hashing = (((h Modulo P) * Q) + (h Modulo Q))
Fin Funcion
Nota que la constante 'size_2_30' arroja un valor de 1.073 millones... aunque manejases tipos de datos de 64 bits, deja que ese valor permita ir devolviendo siempre el resto cuando lo sobrepase....
Debes crearte una función para obtener los dos primos:
Si vas a usarlos en muchas partes (como me pasa a mi), donde se dan distintas circunstancias, mejor un pequeño puñado de funciones, para resolver distintas situaciones...
int p_SizeArray, p_PrimoP, p_PrimoQ
buleano Inicializado
// ========================================================================
// ========= Establecer el par de Primos y el tamaño de la tabla: =========
// ========================================================================
// Es decir sin el par de primos... (caso de querer usar 1 solo valor como módulo, que resulta ser el tamaño del array)
Funcion PorSizeFijo(int Size )
Si (Inicializado = False) luego
p_SizeArray = Size
Inicializado = True
Fin si
Fin funcion
//Una función delega en otra, así puede usarse cualquiera para generar el par de 'primos' según interese...
// Por un tamaño, de cuya raíz cuadrada se busca el primo anterior y siguiente a dichos valores.
Funcion PorSizeArray(buleano AseguraMinimo, ref int Size)
LlamarA PorPrimoMenor ( (SQR(Size)).ToInt)
Si AseguraMinimo luego
Si (p_SizeArray < Size) Luego
Inicializado = False
LlamarA PorPrimoMenor (p_PrimoQ)
Fin si
Fin si
Fin funcion
// Por el primo menor (que se trunca al primo menor que el valor si no lo es), y el primo siguiente a éste.
Funcion PorPrimoMenor(ref int V)
LlamadaA PorPrimos(0, V)
Fin Funcion
// Por los primos recibidos (Se truncan al primo menor y mayor que los respectivos valores recibidos, si no son primos).
Funcion PorPrimos(ref int Q, ref int V)
LlamadaA BuscaPrimos(V, Q)
LlamadaA PorValores(Q, V)
Fin Funcion
// Los valores designados (sean primos o no)
// Al caso: si se llama desde fuera pueden no ser primos,
// pero si es reinvocado desde otras funciones internas, ambos serán primos.
// Notar que en todas las funciones previas, los parámetros son devuelto modificados por referencia.
// aquí en cambio son por valor, y se asignan ya internamente...
Funcion PorValores(int Q, int V)
Si (Inicializado = False) Luego
p_PrimoP = Size
p_PrimoQ = Q
p_SizeArray = (p_PrimoP * p_PrimoQ)
Inicializado = True
Fin si
Fin funcion
Faltan, ahora las funciones de cálculo de primos... obviamente el contenido de EsPrimo(int Valor) la dejo a tu esfuerzo...
function BuscaPrimos(ref int P, ref int Q )
Si (EsPrimo(P) = False) Luego
P = PrimoAnterior(P)
Fin si
Si (Q = 0) Luego
Q = PrimoSiguiente(P)
Sino
Si (EsPrimo(Q) = False) Luego
Q = PrimoSiguiente(Q)
Fin si
Fin si
Fin funcion
// haya el anterior número primo al valor recibido.
int = Funcion PrimoAnterior(int Valor)
Si (Valor >= 4) Luego
Si (Valor And 1) = 0 Luego
Valor = (Valor + 1) // porque luego se restan 2.
Fin si
Hacer
Valor = (Valor - 2)
Repetir Mientras ((EsPrimo(Valor) = False) And (Valor > 2))
Sino
Valor = (Valor - 1)
Fin si
Devolver Valor
Fin Funcion
// haya el siguiente número primo al valor recibido.
int = Funcion PrimoSiguiente(int Valor)
Si (Valor And 1) = 0 Luego
Valor = (Valor - 1) // porque luego se suman 2.
Fin si
Hacer
Valor = (Valor + 2)
Repetir Mientras (EsPrimo(Valor) = False)
Devolver Valor
Fin Funcion
// Debe devolver si el valor entrado es o no es primo.
buleano = Funcion EsPrimo(int Valor)
// Esta función queda a tu esfuerzo...
Fin funcion
Un modo luego de obtener tales primos, es susurrar a la función específica partiendo del tamaño del array previsto (que será algo más grande, finalmente)...
Por ejemplo si el tamaño del array sería aprox. 255, se le pasa dicho valor a la función:
LlamadaA PorSizeArray(TRUE, 255)
Y nos devolverá para el par de primos los valores:
p_PrimoP = 17
p_PrimoQ = 19
Así como el tamaño final del array:
p_SizeArray = (p_PrimoP * p_PrimoQ) = 323
Si quieres forzar que sea 255 o lo más parecido posible, entonces usas la función:
LlamadaA PorValores(15, 17)
Y nos devolverá para el par de primos los valores:
p_PrimoP = 15
p_PrimoQ = 17
p_SizeArray = (p_PrimoP * p_PrimoQ) = 255
Ahora reserva memoria para tu array conforme a su tamaño y el tipo de datos que alojará... Si va de 0 a 255, el tipo de datos puede ser byte (por ejemplo)...
Finalmente tendrás tu hash...
int hash
hash = Hashing(array bytes Key(), p_PrimoP, p_PrimoQ)
Si se crea una clase, lo idela es que ambos primos se crearan con el constructor de la instancia y que la propia función ya los usara sin necesidad de pasarlos como parámetros....
Por otro lado, la función hash podría ser estática en un módulo, y cada instancia realmente invocar a esa estática, con los primos que dicha instancia tenga asignados. Es la situación ideal si tienes que generar hashes para diferentes campos y arrays de diferentes tamaños...
Tenía por ahí, un proyecto de prueba para modificar el tamaño del array (calcular los primos), la ocupación y mostrar gráficamente la distribución... pero no lo localizo, a ver si hay suerte y mañana doy con él... La distribución resulta increíblemente genial. No obstante por si no lo localizo o se me olvida, te describo brevemente en que consistía:
De momento céntrate en la función de hash, y pruébala con un array de pongamos 100.000 elementos, de la que ocupes pongamos un 20% para probar la distribución... usa ambos primos como si fueran sendos valores para el tamaño de filas y columnas, de un bitmap... deja en color negro cada 'píxel' (índice) que en el array está vacío, pinta de blanco el índice con cada casilla (hash) sin colisión y de otro color (por ejemplo rojo, para 1 colisión, verde para 2, azul para 3, amarillo para 4, violeta para más de 4), totaliza también cuántas colisiones tiene el hash que más haya colisionado, etc... tu mismo... Con un bittmap, creado así es fácil ver si la dispersión si es buena o mala, además ambos primos dan para un bitmap incluso de millones de píxeles (un array de varios millones, con lo que permite ver si además de comportarse bien con pequeños arrays lo hace bien también con otros más grandes)...
Autor
En línea
