Implementación de tabla hash

Question

Acabo de comprar un libro "C Interfaces e implementaciones". en el capítulo uno, se ha implementado una estructura de "Atom", código de ejemplo de la siguiente manera:

#define NELEMS(x) ((sizeof (x))/(sizeof ((x)[0]))) 
static struct atom { 
    struct atom *link; 
    int len; 
    char *str; 
} *buckets[2048]; 
static unsigned long scatter[] = { 
2078917053, 143302914, 1027100827,302, 755253631, 2002600785, 
1405390230, 45248011, 1099951567, 433832350, 2018585307, 438263339, 
813528929, 1703199216, 618906479, 573714703, 766270699, 275680090, 
1510320440, 1583583926, 1723401032, 1965443329, 1098183682, 1636505764, 
980071615, 1011597961, 643279273, 1315461275, 157584038, 1069844923, 
471560540, 89017443, 1213147837, 1498661368, 2042227746, 1968401469, 
1353778505, 1300134328, 2013649480, 306246424, 1733966678, 1884751139, 
744509763, 400011959, 1440466707, 1363416242, 973726663, 59253759, 
1639096332, 336563455, 1642837685, 1215013716, 154523136, 593537720, 
704035832, 1134594751, 1605135681, 1347315106, 302572379, 1762719719, 
269676381, 774132919, 1851737163, 1482824219, 125310639, 1746481261, 
1303742040, 1479089144, 899131941, 1169907872, 1785335569, 485614972, 
907175364, 382361684, 885626931, 200158423, 1745777927, 1859353594, 
259412182, 1237390611, 48433401, 1902249868, 304920680, 202956538, 
348303940, 1008956512, 1337551289, 1953439621, 208787970, 164, 
1568675693, 478464352, 266772940, 1272929208, 1961288571, 392083579, 
871926821, 1117546963, 1871172724, 1771058762, 139971187, 1509024645, 
109190086, 1047146551, 1891386329, 994817018, 1247304975, 1489680608, 
706686964, 1506717157, 579587572, 755120366, 1261483377, 884508252, 
958076904, 1609787317, 1893464764, 148144545, 1415743291, 2102252735, 
1788268214, 836935336, 433233439, 2055041154, 2109864544, 247038362, 
299641085, 834307717, 1364585325, 23330161, 457882831, 1504556512, 
1532354806, 567072918, 404219416, 1276257488, 1561889936, 1651524391, 
618454448, 121093252, 1010757900, 1198042020, 876213618, 124757630, 
2082550272, 1834290522, 1734544947, 1828531389, 1982435068, 1002804590, 
1783300476, 1623219634, 1839739926, 69050267, 1530777140, 1802120822, 
316088629, 1830418225, 488944891, 1680673954, 1853748387, 946827723, 
1037746818, 1238619545, 1513900641, 1441966234, 367393385, 928306929, 
946006977, 985847834, 1049400181, 1956764878, 36406206, 1925613800, 
2081522508, 2118956479, 1612420674, 1668583807, 1800004220, 1447372094, 
523904750, 1435821048, 923108080, 216161028, 1504871315, 306401572, 
2018281851, 1820959944, 2136819798, 359743094, 1354150250, 1843084537, 
1306570817, 244413420, 934220434, 672987810, 1686379655, 1301613820, 
1601294739, 484902984, 139978006, 503211273, 294184214, 176384212, 
281341425, 228223074, 147857043, 1893762099, 1896806882, 1947861263, 
1193650546, 273227984, 1236198663, 2116758626, 489389012, 593586330, 
275676551, 360187215, 267062626, 265012701, 719930310, 1621212876, 
2108097238, 2026501127, 1865626297, 894834024, 552005290, 1404522304, 
48964196, 5816381, 1889425288, 188942202, 509027654, 36125855, 
365326415, 790369079, 264348929, 513183458, 536647531, 13672163, 
313561074, 1730298077, 286900147, 1549759737, 1699573055, 776289160, 
2143346068, 1975249606, 1136476375, 262925046, 92778659, 1856406685, 
1884137923, 53392249, 1735424165, 1602280572 
}; 
const char *Atom_new(const char *str, int len) { 
    unsigned long h; 
    int i; 
    struct atom *p; 
    assert(str); 
    assert(len >= 0); 
    for (h = 0, i = 0; i < len; i++) 
     h = (h<<1) + scatter[(unsigned char)str[i]]; 
    h &= NELEMS(buckets)-1; 
    for (p = buckets[h]; p; p = p->link) 
     if (len == p->len) { 
      for (i = 0; i < len && p->str[i] == str[i];) 
       i++; 
      if (i == len) 
       return p->str; 
     } 
    p = ALLOC(sizeof (*p) + len + 1); 
    p->len = len; 
    p->str = (char *)(p + 1); 
    if (len > 0) 
     memcpy(p->str, str, len); 
    p->str[len] = '\0'; 
    p->link = buckets[h]; 
    buckets[h] = p;//insert atom in front of list 
    return p->str; 
} 

al final del capítulo, en los ejercicios 3.1, el autor del libro, dijo "mayoría de los textos recomiendan el uso de un número primo de del tamaño de las cubetas . Usar una función de hash primo y bueno generalmente da una mejor distribución de las longitudes de las listas que cuelgan de cubos Atom usa una potencia de dos, que a veces se cita explícitamente como como una mala elección. Escriba un programa para generar o lea, digamos, 10,000 cadenas típicas y mida la velocidad de Atom_new y la distribución ution de las longitudes de las listas. A continuación, cambie los intervalos para que tenga 2.039 entradas (la primicia más grande menos de 2.048), y repita las medidas . ¿Usa una ayuda excelente? ¿Cuánto depende su conclusión de en su máquina específica? "

así lo hice modificados que tamaño de la tabla hash para 2039, pero parece un número primo en realidad hizo una mala distribución de las longitudes de las listas, he tratado de 64, 61, 61 hacen realmente una mala distribución demasiado .

estoy sólo quiero saber por qué un tamaño de la tabla primer hacer una mala distribución, es porque la función hash se utiliza con Atom_new una función hash malo?

estoy usando esta función para imprimir las longitudes de el átomo enumera

#define B_SIZE 2048 
void Atom_print(void) 
{ 
    int i,t; 
    struct atom *atom; 
    for(i= 0;i<B_SIZE;i++) { 
     t = 0; 
     for(atom=buckets[i];atom;atom=atom->link) { 
      ++t; 
     } 
     printf("%d ",t); 
    } 
} 

Answer 1

Bueno, a lo largo Hace tiempo que tenía que poner en práctica una tabla hash (en el desarrollo de controladores), y sobre el mismo. ¿Por qué diablos debería usar un número primo? La potencia OTOH de 2 es incluso mejor: en lugar de calcular el módulo en caso de potencia de 2, puede usar AND a nivel de bit.

Así que he implementado una tabla hash. La clave era un puntero (devuelto por alguna función de terceros). Luego, finalmente noté que en mi tabla hash solo se llena 1/4 de todas las entradas. Debido a que la función hash que utilicé fue la función identidad, y si acaso resultó que todos los punteros devueltos son múltiplos de 4.

La idea de utilizar los números primos para el tamaño de la tabla hash es la siguiente: bienes -world hash functions no producen valores distribuidos equitativamente. Usualmente hay (o al menos puede haber) alguna dependencia. Por lo tanto, para difuso esta distribución se recomienda utilizar números primos.

BTW, teóricamente puede suceder que ocasionalmente la función hash produzca los números que son múltiplos de su número primo elegido. Pero la probabilidad de esto es menor que si no fuera un número primo.

Answer 2

Creo que es el código para seleccionar el cubo. En el código que ha pegado que dice:

h &= NELEMS(buckets)-1; 

Eso funciona bien para los tamaños que son potencias de dos, ya que su efecto final es la elección de los bits más bajos de h. Para otros tamaños, NELEMS(buckets)-1 tendrá bits en 0 y el operador bit-wise & descartará esos bits, dejando efectivamente "agujeros" en la lista de depósitos.

La fórmula general de selección de cuchara es:

h = h % NELEMS(buckets); 

Answer 3

Esto es lo que Julienne Walker de Eternally Confuzzled tiene que decir acerca de los tamaños de la tabla de hash:

cuando se trata de tablas hash, el tamaño de la tabla recomendada más es cualquier número primo. Esta recomendación se hace porque hash en general es mal entendido, y pobres funciones hash requieren una etapa de mezcla adicional de división por un número primo que se asemejan a una distribución uniforme . Otra razón por la cual se recomienda un tamaño de tabla principal es porque varios de los métodos de resolución de colisión requieren que funcione. En realidad, esto es una generalización y en realidad es falsa (una potencia de dos con tamaños de paso impares típicamente funcionan igual de bien para la mayoría de las estrategias de resolución de colisiones ), pero no muchos personas consideran las alternativas y en el mundo de las tablas hash, prime reglas.

Answer 4

Hay otro factor en juego aquí y es que los valores de la mezcla constante todos deben ser impar/Prime y muy dispersos. Si tiene un número par de unidades (por ejemplo, caracteres) en la clave que se va a procesar, entonces tener todas las constantes impares le dará un valor inicial de hash inicial. Para un número impar de unidades obtendrías un número impar. He hecho algunos experimentos con esto y solo la división del 50/50% valió mucho en la distribución. Por supuesto, si todas las teclas son igualmente largas, esto no importa.

El hash también debe garantizar que no obtendrá el mismo valor hash inicial para "AAB" que para "ABA" o "BAA".