При добавлении первого узла в связанный список в hashmap, почему новый узел должен быть назначен непосредственно индексированному указателю? - PullRequest
Новая
       25

При добавлении первого узла в связанный список в hashmap, почему новый узел должен быть назначен непосредственно индексированному указателю?

0 голосов
/ 01 октября 2019

Вот моя реализация hashmap в c, его инициализация и вставка кода. В структуре hashmap_t я использую массив указателей (таблица) на узлы, которые содержат пары ключ / значение. В hashmap_init я выделяю нужное количество узлов и перебираю массив, устанавливая каждый указатель в NULL.

Что меня смущает, так это функция hashmap_put. Я нахожу индекс, в список которого должен быть вставлен ключ, и на этот первый указатель ссылается hm-> table [i]. Для ясности я хочу убедиться, что очевидно, что hm-> table [i] является началом списка, поэтому я назначаю его hashnode_t * head.

Так что при вставке первого узла (head == NULL), Я изначально использовал head = new_node, но ни одна из моих вставок не работала. Это работает, только когда я использую hm-> table [i] = new_node.

Я не понимаю, почему это так. head указывает на то же самое, так почему установка head, равная new_node, не работает? Я также запутался позже в функции, когда last-> next = new_node работает. Последний указатель, как голова, но он работает там.

Спасибо за любые разъяснения. 

typedef struct hashnode {
  char key[128];                
  char val[128];                
  struct hashnode *next;        
} hashnode_t;

typedef struct {
  int item_count;             
  int table_size;              
  hashnode_t **table;          
} hashmap_t;

void hashmap_init(hashmap_t *hm, int table_size) {
  hm->table_size = table_size;
  hm->item_count = 0;
  hm->table = malloc(table_size * sizeof(hashnode_t)); 
  for (int i = 0; i < table_size; i++) { // loop through array of pointers to nodes
    hm->table[i] = NULL;
  }
}

int hashmap_put(hashmap_t *hm, char key[], char val[]) {
  hashnode_t *new_node = malloc(sizeof(hashnode_t)); // allocate new node
  strcpy(new_node->key, key);
  strcpy(new_node->val, val);
  new_node->next = NULL;

  int i = hashcode(key) % hm->table_size; // index of list hashed to
  hashnode_t *head = hm->table[i];
  hashnode_t *cur = head;
  hashnode_t *last;

  if (!head) { // list is empty
    new_node->next = head;
    hm->table[i] = new_node;
    //why does head = new_node not work?
    hm->item_count += 1;
    return  1;
  }

  while (cur) { // loop through nodes
    if (strcmp(cur->key, key) == 0) {
      strcpy(cur->val, val);
      free(new_node);
      return 0;
    }
    last = cur; // save pointer to node that points to NULL
    cur = cur->next;
  }
  last->next = new_node;
  //why does it work here?
  hm->item_count += 1;
  return 1;
}

1 Ответ

1 голос
/ 01 октября 2019

'head' указывает на hashnode_t, как и 'hm-> table [i]'. Итак, они оба указывают на один и тот же объект. Изменение «головы» просто указывает на «голову» в другом месте. Вы фактически не назначили указатель в hashmap_t для 'new_node'.

Причина, по которой работает «last», заключается в том, что вы меняете переменную-член на новое значение. И, так как 'last' указывает на объект уже в hashmap_t, назначение обновляет объект, на который указывает hastmap_t. Таким образом, обновление до 'last-> next = new_node' аналогично 'hm-> table [x] -> next = new_node' ('x' - произвольный индекс).

...