В разделе 6.6 K&R обсуждается хеш-таблица с использованием связанного списка.
Короче говоря, хеш-таблица - это массив указателей. Указатели указывают на связанный список. Связанный список - это структура, которая выглядит так:
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
Имя хешируется, и этот хеш определяет индекс в таблице. Затем в главе показан код для добавления пары name / defn в таблицу:
struct nlist *install(char *name, char *defn) {
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { /* not found */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free((void *) np->defn); /*free previous defn */
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
Все имеет смысл, кроме следующих двух строк:
np->next = hashtab[hashval];
hashtab[hashval] = np;
Когда я пытаюсь понять это, я все время прихожу к выводу, что список теперь содержит ссылки обратно к себе, и если вы попытаетесь пройти по связанному списку, это будет похоже на собаку, преследующую собственный хвост. Я ожидаю, что код установит np-> рядом с NULL.
Что я не понимаю? Почему этот код работает?