Funcion Hash para un diccionario de palabras.

[NextByte]

¿Alguien conoce algun algoritmo especifico para generar una función hash eficiente para un diccionario(tabla hash)?

Mi problema plantea el uso de un diccionario que utiliza como generadora del hash una cadena que por el contexto del problema no debería sobresalir de más de 15 caracteres y en promedio tendría un aproximado de 10 caracteres. Hasta ahorita me he empezado a formular una manera de que no existan tantas colisiones en el entero que genera cada string con referencia a que pueden existir string diferentes pero que en si tienen los mismo caracteres, he pensado en varias formas entre las cuales se encuentra por ejemplo multiplicar los valores  de cada posion por un valor que no pueda ser generado con la suma de los anteriores es decir:
Cadena "hola"
HASH = 0;
HASH += 'H' ;
HASH += 'O' +167
HASH += 'L' + 334
HASH += 'A' + 501

El factor 167 lo eligo debido a que el último caracter que se usaria en el contexto de mi problema seria las vocales con acento que se encuentran como maximo en el valor 165 del ASCII y de esta manera puedo generar valores distintos para cadenas que contiene los mismo caracteres pero en distintas posiciones

Nota. he considerado hacer este proceso hasta los 6 caracteres como maximo ya que considero que sería muy extraño que dos palabras empiecen con el mismo patron de 6 caracteres y esto solo estaria consumiendo mas tiempo para cadenas un poco mas largas.

Mi duda surge a la hora de adaptar lo que tengo hasta ahorita al arreglo que me va representar el diccionario. Actualmente mi diccionario esta representado por un arreglo de arboles binarios que cuando encuentran colisiones simplemente se añade a una rama del árbol. Mi pregunta es como se hace para ya teniendo un algoritmo generador de hash adaptarlo a la dimension del arreglo que en mi caso es el de tamaño "101". He probado con algoritmos como el anterior y no he conseguido valores de colisiones favorables, he probado con hash algo aleatorios y he conseguido llegar a que la desviacion estandar de las colisiones sea de 2.86  con una media de aproximadamente 8.44 y un total de datos ingresados de 853 pero como menciono no quedo satisfecho debido a que el algoritmo generador de hash no tiene mucho sentido.

ACTUALIZACIÓN. Cuando digo que no se como adaptar lo que llevo hasta ahorita para ingresarlo en arreglo me refiero a que no se como hacer que se distribuya de una manera ligeramente pareja en todas las posiciones , al menos al moment de ahora lo único que hago es relizar un modulo al hash obtenido:

HASH_OBTENIDO % TAMANO_ARREGLO( Es un numero primo)

[Loretz]

En C++ ya tienes un "diccionario", en la forma de un std::map. También, si no necesitas que se mantenga ordenado, la clase std::unordered_map es directamente una "hash table".

Va un ejemplo:

Código (cpp) [Seleccionar] Expandir

#include <map>
#include <string>
#include <iostream>
#include <functional>

int main()
{
     std::map<std::string, int> mi_map{ {"hola", 1}, {"chau", 2} };

    for (const auto& [k, v] : mi_map) {
        std::cout << "key == " << k << "; value == " << v << '\n';
    }

    // si solo se necesita calcular los hash:

    std::string hola{ "hola mundo!" };

    std::hash<std::string> hash_function;

    size_t el_hash = hash_function(hola);

    std::cout << "hash de \"hola mundo\" == " << el_hash << '\n';
}

[Serapis]

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...

Código [Seleccionar] Expandir


// 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...

Código [Seleccionar] Expandir


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...

Código [Seleccionar] Expandir


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...

Código [Seleccionar] Expandir


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)...

[NextByte]

Muchas gracias por tu respuesta y tu tiempo, prometo este fin de semana seguir con atención tu respuesta con más calma sin embargo me surge la pregunta de como llegaste a darte cuenta de todos estos aspectos. Durante mi viaje por varias notas y segmentos de libro solo hablan de manera muy superficial sobre como tratar las colisiones y cuales son las caracteristicas de una buena funcion hash sin embargo no he visto una respuestas tan construida como la tuya, supongo que profundizando un poco más sobre los temas de matematicas discretas se podrá fundamentar de mejor manera las conclusiones a las que llegaste pero ¿ Como lograste llegar a ellas ? , no las pongo en duda  pero me intriga el saber como fue la construcción de todos estos elementos.

[Serapis]

Trato de explicarte por encima...

La razón por la que un par de primos funciona mejor es bastante obvia (no, antes de que lo explique, claro)...
Un primo distribuye un hash en una de las 'cajas' (o líneas) del array... el otro primo, lo distribuye el hash, dentro de dicha caja... usar un solo primo es como tener un única caja... en la que lo distribuye.
Visto de otra manera: Considera como si fuera un array bidimensional, donde el primer primo selecciona el índice de la primera dimensión y el otro el indice en dicha dimensión, entonces dos hashes que un solo primo fueren a ser contiguos, ahora estarán bastante distantes, incluso en otra caja y ni siquier aocupando la misma posición 'contigua' en la otra caja, lo que logra que 'cadenas' casi iguales queden alejadas...
Un ejemplo: imaginemos (2 hashes obtenidos con un solo primo) cuyos índice absoluto 345678 y 345679, contíguos entre sí usando un solo primo, y supongamos los primos 787 y 797 (que he usado en el ejemplo de la imagen de más abajo), tendremos pués:
h1 = ((345678 modulo 787) * 797) + (345678 modulo 797) = 147445 + 577 = 148022
h2 = ((345679 modulo 787) * 797) + (345679 modulo 797) = 148242 + 578 = 148820
Como se ve, donde antes dos hashes estaban contíguos, ahora están distanciados 802.

En cuanto al porqué es preferible que los primos sean consecutivos, es porque es lo que hace que el 'area' sea lo más cerca posible de un cuadrado... digamos que cuanto más cuadrado más 'bidimensional' y cuanto más alargado resulte el rectángulo más se acerca a la 'unidimensionalidad'...

Considera que se podrían usar por ejemplo 3 primos con las mismas consideraciones, (lo más cercanos entre sí, así tendríamos un volumen (un array de tres dimensiones), e igualmente más primos para más dimensiones, el límite práctico, es el costo asociado al cálculo y también la ocupación de memoria dado que la multiplicación de más de dos primos hace que si un tamaño de array es pequeño para un conjunto dado, el siguiente 'cubículo', quizás sea excesivamente grande, por ejemplo para usar 3 primos: 5*7*11 = 385... supngamos que nuestro array estuviera bien conforme a 400 elementos, al ser 385, resulta insuficiente, pensmaos pués en tomar el siguiente conjunto de primos: 7*11*13 = 1001. Ahora ya, quizás se aleje en exceso y por tanto desperdicie más memoria de la aceptable. Claro que cuando los primos sean muy elevados , la cantidad no sea tan apreciable, pero es algo que claramente va 'a peor', cuantos más primos se utilicen... En tales sitauciones (utilizar varios primos), puede elegirse primos, no necesariamente contiguos que ronden su multiplicación un valor aproximado del tamaño del array adecuado... (en un ejemplo de abajo hago eso mismo, elegir dos primos distantes entre sí, que ofrecen un área más rectangular, pero cuyo producto arroja un array de tamaño muy similar al previo.

Lo normal, cuando desarrollas un algoritmo y necesitas verificar la eficiencia del mismo en diferentes aspectos, es que acabes por construir otros programas que lo pongan a prueba (al menos los aspectos que más interesan que sean verificados como óptimos).

La siguiente imagen procede de una de esas pruebas, se carga un fichero de texto de unas 90.000 líneas, se hashea cada línea (de cada línea se toman unos 44, d elos cuales los 32 últimos son números y letras A-E, para pronunciar la similaridad entre tales cadenas de texto), al caso la tabla tiene un tamaño para distribución de 627.239 elementos, resultado de aplicar los primos 787 * 797.
627.239 / 90.000 = arroja una ocupación de aproximadamente 1/7 de la tabla.

Los píxeles negros, son los huecos sin hash, los de colores los que tienen hash...
A la derecha el color azul simula la ocupación de cada línea, es decir se hace al final un barrido por cada línea, se cuentan los píxeles que no son negros y en la misma proporción del ancho del área azul (que refleja la línea entera) se dibuja en amarillo (que representa la ocupación en esa línea)...
Como se ve, no solo en la distribución de la imagen, si no también en la zona d ela derecha, en cada línea existe una cierta igualdad de prorcion en cuanto a la ocupación.
(hay que hacer scroll horizontal abajo del mensaje, para verlas, también incluyo nota  allí debajo).



Y en la siguiente imagen se ha rehaseado todo de nuevo pero ahora con primos: 607 * 1033, el array ahora (he buscado un par de primos que den un array de tamaño similar) es: 627031, una diferencia poco significativa con la anterior...
Como se ve sobre la imagen la distribución sigue siendo buena, la zona azul (a la derecha), ahora debiera ser más ancha (pués 1033 actúa como el ancho de línea), pero la he recortado al mismo ancho que el resto, para que no distorione la visualización de todas sobre el foro (después de todo es solo contenido azul, yla ocupación es similar 1/7, ya que el tamaño del array ha cambiado el tamaño sin relevancia).
Es importante notar que incluso en un área rectangular el comportamiento sigue siendo mejor que usando un solo primo como módulo.


En esta tercera imagen es lo mismo que la primera, simplemente se ha omitido dibujar las posiciones ocupadas pero sin colisión (puntitos grises), es decir se muestran solo los píxeles donde existen colisiones  (los de 1 colisión es decir 2 hashes chocaron en la misma posición, son los puntitos rojos, los más numerosos ahora).
El propósito de esta imagen es verificar que aún las mismas colisiones también tienen una buena dispersión y que tampoco aparecen amontonadas en una zona específica...


En esta última, solo se dibujan las casillas que tienen colisión, se omiten las casillas no ocupadas, así como las que están ocupadas pero sin o con solo una colisión). El objetivo es ver cuantas posiciones se ven afectadas por más de una colisión... solo añadir que ninguna posición llega a tener más de 6 colisiones, y como se ve, la suma de todas éstas, tampoco son muy numerosas...


NOTA: No ajusto las imágenes para verlas a tamaño real, pués están sin comprimir, para no alterar el contenido, y que al achicarlas para hacerlas tangibles al foro, obviamente la interpolación falsearía, el contenido...