Comptage de clusters dans un ensemble de hachage

Question

J'essaie de déboguer une implémentation de hachage (pour une tâche d'école). Les collisions sont gérées via un sondage linéaire, et j'ai besoin de compter le nombre de clusters d'une taille donnée pour la routine de débogage. J'ai travaillé cette place:

// really just hoping that a 50+ cluster doesn't occur 
int clusters[50]; 
int count = 0; 
for (int i=0; i < hashset->dim; i++) { 
    if (hashset->array[i] != NULL) { 
     count++; 
    } else { 
     if (count == 0) continue; 
     if (clusters[count] == NULL) clusters[count] = 0; 
     clusters[count]++; 
     count = 0; 
    } 
} 
for (int i=1; i < 50; i++) { 
    if (clusters[i] != NULL && clusters[i] != 0) 
     printf("%d clusters of size %d\n", clusters[i], i); 
} 

semble logique, mais quand je le lance ... je reçois

25143 entries in hashset 
50286 dimension of the hash array 
4585 clusters of size 1 
2134 clusters of size 2 
1102 clusters of size 3 
696 clusters of size 4 
388 clusters of size 5 
264 clusters of size 6 
173 clusters of size 7 
104 clusters of size 8 
89 clusters of size 9 
51 clusters of size 10 
46 clusters of size 11 
35 clusters of size 12 
26 clusters of size 13 
22 clusters of size 14 
17 clusters of size 15 
134553327 clusters of size 16 
134634407 clusters of size 17 
112 clusters of size 18 
6 clusters of size 19 
134553324 clusters of size 20 
134634399 clusters of size 21 
107 clusters of size 22 
3 clusters of size 23 
2 clusters of size 24 
134634401 clusters of size 25 
107 clusters of size 26 
134107784 clusters of size 27 
134556210 clusters of size 28 
[... more nonsense] 

Donc, d'abord, il semble donner la production saine d'esprit .. beaucoup de grappes, mais peu importe . Je pense que les nombres trop grands devraient effectivement être 0 - ce sont des groupes qui n'existent pas mais qui, pour une raison ou une autre, sont encore imprimés. Je n'ai aucune idée pourquoi ...

Answer 1

Voici un programme court C:

#include <stdio.h> 
int main() { 
    char buf[20]; 
    for (int i = 0; i < 20; i++) { 
    printf("%d ", buf[i]); 
    } 
    printf("\n"); return 0; 
} 

Réfléchissez bien à ce qu'il doit imprimer lorsque vous l'exécutez.

• Imprime-t-il la même chose chaque fois que vous l'exécutez?
• Sur chaque machine vous l'exécutez?

Spoiler ci-dessous:

(spoiler padding) 













. 

Voici ce que je l'ai vu imprimer pour une course: 0 0 0 0 0 0 0 0 -128 5 64 0 0 0 0 0 -16 -60 -55 31

Le même bogue afflige nos deux programmes, mais il pourrait être plus facile de voir dans le mien.

Answer 2

Vous écrivez

ils sont des groupes qui ne sont pas réellement existent mais pour une raison encore s'imprimé

Vous êtes en supposant implicitement que l'élément clusters[i] ne exister si vous ne l'avez pas attribué. Mais c'est pas vrai. Chaque valeur de la matrice clusters existe en permanence, que vous lui assigniez ou non une valeur. Si vous n'attribuez pas de valeur connue, la valeur est imprévisible, peut-être 134634399. Donc, si vous voulez que tous les éléments de clusters soient prévisibles, que devez-vous faire?

Ce malentendu du modèle de mémoire C conduit au code suivant (extrait de votre question):

int clusters[50]; 
/* ... */ 
for (int i=1; i < 50; i++) { 
    if (clusters[i] != NULL && clusters[i] != 0) 
     printf("%d clusters of size %d\n", clusters[i], i); 
} 

Quel est le but du test clusters[i] != NULL? Vous essayez de décider si clusters[i] a déjà été défini par la boucle que j'ai omise, mais tester avec NULL ne peut pas le faire. Les éléments de clusters ne sont pas une sorte de pointeur, ce sont des valeurs entières brutes de 4 octets. Ils toujours ont une certaine valeur, mais à moins que vous les définissiez à quelque chose, cette valeur est imprévisible.