Personalmente, creo que sería mejor leer los cuatro bytes IP como un largo sin signo que le daría un número aproximadamente en el rango 0 - 2^32-1. Luego calcula cuántos flujos desea tener activos en un momento dado y ese sería su tamaño de tabla de índice.
Tome 2000 por ejemplo. Eso significa que desea mapear 2^32 números en aproximadamente 2^11 indeces (para fluir información). Eso no funcionará porque hashing casi nunca funciona si está lleno al 100% e incluso el 90% puede ser difícil. Usar una tabla de índice que solo llene al 50% (4000 indeces) o incluso al 25% (8000) no es gran cosa con los recuerdos de hoy.
El tamaño exacto de la tabla de índice debe ser un número impar de ubicaciones y preferiblemente un número primo. Esto se debe a que lo más probable es que necesite tener algún control de desbordamiento para manejar las colisiones (dos o más números de IP que después del hash apuntan a la misma ubicación en la tabla de índice), lo que obtendrá. El manejo de desbordamiento debe ser otro número primo menor que el tamaño de la tabla de índice. Todos estos números primos! ¿Qué pasa con ellos de todos modos?
voy a ilustrar con un ejemplo (en C):
idxsiz = prime(2000 * 2); // 50% loading
ovfjmp = prime(idxsiz/3);
...
llenar inicialmente la tabla de posiciones idxjmp con un marcado INUSITADO (-1). Tenga una marca SUPRIMIDA lista (-2).
Su número IP entra en el sistema y que busque su historial de flujo (puede o no existir):
stoppos = ip % idxsiz; /* modulo (division) just this once */
i = stoppos;
do
{
if (index[i] == UNUSED) return NULL;
if (index[i] != DELETED)
{
flowrecptr = &flow_record[index[i]];
if (!flowrecptr->in_use) {/* hash table is broken */}
if (flowrecptr->ip == ip) return flowrecptr;
}
i += ovfjmp;
if (i >= idxsiz) i -= idxsiz;
}
while (i != stoppos);
return NULL;
El INUSITADO sirve como un marcador que este índice no se ha utilizado y que la búsqueda debe parar . El DELETED sirve como marcador de que este índice se ha utilizado pero ya no. Eso significa que la búsqueda debe continuar.
Esto fue cuando intentabas hacer un get. Obtuviste un NULL de get así que necesitas hacer un put que comienzas encontrando la primera posición de índice que contiene UNUSED o BORRADO. Reemplace este valor con un índice a la primera/siguiente fila libre en la tabla flow_record. Marque la fila como in_use. Coloque el número IP original en el miembro ip de la fila flow_record.
Esta es una forma muy simple, pero muy efectiva, de construir un mecanismo hash. Prácticamente todas las optimizaciones en forma de funciones especiales que se utilizarán después de que esta o aquella función hayan fallado mejorarán la eficacia del hash.
El uso de números primos garantizará que, en el peor de los casos donde todas las ubicaciones de índice estén ocupadas, el mecanismo probará cada ubicación individual. Para ilustrar esto: supongamos que idxsiz es uniformemente divisible por ovfjmp: no tendrá mucho manejo de desbordamiento para hablar de ello. 35 y 7 darán como resultado que las ubicaciones 0,7,14,21 y 28 se prueben antes de que el índice salte a 0, donde la prueba de tiempo hará que la búsqueda se detenga.
---------------------- ¡OOPS!
Me perdí que también quería el número de puerto. Suponiendo ip V4 que significa 6 bytes de dirección. Lea esto como un entero sin signo de 64 bits y borre los 16 bits/2 bytes superiores. Luego haces el cálculo del módulo.
Entonces, ¿por qué no multiplicar cada ip por la prima en lugar de solo la fuente? – creatiwit
La función hash volvería a asociarse porque '(a * P)^(b * P) = (b * P)^(a * P)'. Aunque es común ver dos números coprime trabajando en tándem para hacer algo similar. –