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í