urtevolution.com.ar

Para comprobar el funcionamiento tanto del porcentaje mencionado anteriormente y la el generador de keys realicé la siguiente prueba.

Generé 500000 strings con el siguiente algoritmo:

Lo que genera strings del tipo:
" 4152 4155 4163 4169"

Los siguientes gráficos muestran la distribución de celdas (posibles claves) que contienen n elementos.

Tamaño del Hash: 250000 (50% de los elementos)
Cantidad maxima de colisiones: 12
Promedio: 2.000000
Desviación Standard: 1.410260
Distribución:
0 elementos en 33441.000000 celdas
1 elementos en 67834.000000 celdas
2 elementos en 68164.000000 celdas
3 elementos en 45089.000000 celdas
4 elementos en 22454.000000 celdas
5 elementos en 8849.000000 celdas
6 elementos en 3025.000000 celdas
7 elementos en 866.000000 celdas
8 elementos en 221.000000 celdas
9 elementos en 44.000000 celdas
10 elementos en 10.000000 celdas
11 elementos en 2.000000 celdas
12 elementos en 1.000000 celdas

Tamaño del Hash: 500000 (100% de los elementos)
Cantidad maxima de colisiones: 8
Promedio: 1.000000
Distribución Standard: 0.998519
Distribución:
0 elementos en 183723.000000 celdas
1 elementos en 184042.000000 celdas
2 elementos en 92218.000000 celdas
3 elementos en 30734.000000 celdas
4 elementos en 7438.000000 celdas
5 elementos en 1543.000000 celdas
6 elementos en 267.000000 celdas
7 elementos en 29.000000 celdas
8 elementos en 6.000000 celdas

Tamaño del Hash: 1000000 (200% de los elementos)
Cantidad maxima de colisiones: 7
Promedio: 0.500000
Distribución Standard: 0.706421
Distribución:
0 elementos en 606248.000000 celdas
1 elementos en 303590.000000 celdas
2 elementos en 76036.000000 celdas
3 elementos en 12368.000000 celdas
4 elementos en 1573.000000 celdas
5 elementos en 170.000000 celdas
6 elementos en 13.000000 celdas
7 elementos en 2.000000 celdas

Tamaño del Hash: 2000000 (400% de los elementos)
Cantidad maxima de colisiones: 5
Promedio: 0.250000
Desviación Standard: 0.499238
Distribución:
0 elementos en 1557088.000000 celdas
1 elementos en 390190.000000 celdas
2 elementos en 48628.000000 celdas
3 elementos en 3835.000000 celdas
4 elementos en 246.000000 celdas
5 elementos en 13.000000 celdas

Puedes ver la introducción de este artículo aquí o puedes ver la implementación que corresponde a este análisis aquí

Bien, aquí la implementación que he puesto en el servidor. Si bien se que hay muchas dando vueltas, eran o muy complejas y extensibles o muy simples y poco rehusables mas allá del entorno en el que fue creado. O peor aún para este caso, usar librerias externas al proyecto original, creando aún más dependencias. No olvidemos que el objetivo del proyecto es extender las funcionalidades del urt solamente cambiando el ejecutable y nada más. Creo que esta es un punto medio, esta “inspirada” en esta implementación de un arbol rojo-negro.

.

Aquí un ejemplo de implementación:
.
.

Puedes ver la introducción de este artículo aquí o ver el análisis de la implementación aquí

Nota: Lo puesto aquí es solamente ilustrativo, no pretendo hacer de esto una teoría ni mucho menos.  Las pruebas realizadas y puestas aquí pueden no serte de utilidad alguna.  Pero si necesitas una guia de como analizar una tabla hash y la función generadora de claves, puede ser un buen comienzo.

Al iniciar el proyecto, lo primero que uno se pregunta, es que estructura es la mas adecuada. Para contestarla correctamente debemos tener en cuenta tres factores. Velocidad de búsqueda, uso de la memoria y si la información debe estar ordenada o no.

Quizas el que menos importe para aplicaciones no-embebidas es el punto de la memoria. En general cualquier estructura que tenga un orden de búsqueda decente no utiliza memoria a mansalva.

Por lo que nos quedan dos pesos pesados bien claros, velocidad de búsqueda y si la información debe o no estar ordenada.

Las dos estructuras obvias que uno piensa en estos casos son: arboles binarios balanceados (AVL o rojo-negro por ejemplo) y la sencilla pero ingeniosa tabla hash.

Recordemos que el órden de búsqueda de los arboles binarios balanceados es O(log₂(n)) siendo n la cantidad de elementos insertados. El orden de inserción y eliminación de elementos a pesar de que tiene que realizar operaciones para balancear el arbol, también tienden al mismo orden que el de búsqueda. Pueden ver un análisis mas detallado aquí

Por otro lado, la tabla hash teórica tiende a un orden mínimo tanto en búsqueda como inserción y eliminación, que sería O(1). Esto en la práctica dificilmente se cumpla, ya que generar una clave hash unica e irrepetible para cada elemento es una tarea casi imposible para una cantidad grande de elementos. Hablamos del orden de 10000 elementos o mas. Si querés ver mas sobre tablas hash podes verlo aquí

Incluso una buena función generadora de hash como puede ser esta:

nos sigue devolviendo valores repetidos ante distintas entradas. Incluso aunque la cantidad de entradas en la tabla supere ampliamente la cantidad de elementos a insertar. Lo que nos ocasiona una tabla muy grande (3 o 4 veces la cantidad de items a insertar) y que nunca la podamos llenar correctamente. Al ser algo inevitable la repetición de entradas podemos aprovechar esto como un fuerte para disminuir el uso de los lugares no utilizados, un buen número para la longitud de la tabla es entre un 30% y un 60% del total de los items que tenemos (o planeamos tener). Por lo tanto, para 10.000 elementos deberiamos tener una tabla de 3.000 a 6.000 elementos. De esta forma tenemos un acceso promedio de 2 o 3 elementos por clave, distribuido normalmente con una baja desviación estándard. El algoritmo para sacar una desviación standard de valores acumulados es este:
.

Puedes ver la implementación aquí y el análisis de la tabla aquí