Подсчет кластеров в хэш-наборе

Question

Я пытаюсь отладить реализацию хэш-набора (для школьного задания). Столкновения управляются с помощью линейного зондирования, и мне нужно подсчитать количество кластеров заданного размера для процедуры отладки. Я работал над этим:

// 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);
}

Кажется, имеет смысл, но когда я запускаю его, я получаю ...

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]

Так что изначально кажется, что он дает вменяемый результат ... много кластеров, но неважно. Я думаю, что слишком большие цифры на самом деле должны быть 0 - это кластеры, которые на самом деле не существуют, но по какой-то причине все еще печатаются. Я просто понятия не имею, почему ...

Answer 1

Вы пишете

это кластеры, которые на самом деле не существуют, но по какой-то причине до сих пор печатать

Вы неявно предполагаете, что элемент clusters[i] не существует, если вы ему не назначены. Но это не правда. Каждое значение в массиве clusters существует постоянно, независимо от того, назначаете ли вы ему значение или нет. Если вы не присваиваете известное значение, это значение непредсказуемо, возможно, 134634399. Итак, если вы хотите, чтобы все элементы в clusters были предсказуемыми, что вы должны сделать?

Это неправильное понимание модели памяти C приводит к следующему коду (выдержка из вашего вопроса):

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);
}

Какова цель теста clusters[i] != NULL? Вы пытаетесь решить, был ли когда-либо установлен clusters[i] по циклу, который я пропустил, но тестирование по NULL не может этого сделать. Элементы clusters не являются своего рода указателем, они представляют собой необработанные 4-байтовые целочисленные значения. Они всегда имеют какое-то значение, но если вы не установите их для чего-либо, это значение будет непредсказуемым.

Answer 2

Вот короткая программа на C:

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

Тщательно продумайте, что следует печатать при запуске.

• Будет ли печататься одно и то же при каждом запуске?
• На каждой машине, на которой вы ее запускаете?

Спойлер ниже:

(spoiler padding)













.

Вот то, что я видел, это напечатало за один прогон: 0 0 0 0 0 0 0 0 -128 5 64 0 0 0 0 0 -16 -60 -55 31

Одна и та же ошибка затрагивает обе наши программы, но, возможно, ее легче увидеть в моей.