CODEWITHSUNDEEP
clinked-listhashmap
logLady
logLady

Reputation: 1

When adding first node to linked list in hashmap, why must the new node be assigned directly to the indexed pointer?

Here is my implementation of a hashmap in c and its initialization and insert code. In the hashmap_t structure, I use an array of pointers (table) to nodes which contain the key/value pairs. In hashmap_init, I allocate the desired amount of nodes and loop through the array setting each pointer to NULL.

What I'm confused about is in the hashmap_put function. I find the index of which list the key should be inserted in and that first pointer is referenced by hm->table[i]. For clarity, I want to make sure it's obvious that hm->table[i] is the start of the list so I assign it to hashnode_t *head.

So when inserting the first node (head == NULL), I originally used head = new_node, but none of my inserts worked. It only works when I use hm->table[i] = new_node.

I don't understand why that's the case. head points to the same thing so why does setting head equal to the new_node not work? I'm also confused later in the function when last->next = new_node does work. Last is a pointer just like head but it works there.

Thanks for any clarification.

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

Upvotes: 0

Views: 299

Answers (1)

Topher
Topher

Reputation: 461

'head' is pointing to a hashnode_t and so is 'hm->table[i]'. So, they are both pointing to the same object. Changing 'head' just makes 'head' point elsewhere. You have not actually assigned a pointer in the hashmap_t to the 'new_node'.

The reason that 'last' works is that you are changing a member variable to a new value. And, since 'last' is pointing to an object already in the hashmap_t, the assignment updates the object pointed to in the hastmap_t. So, an update to 'last->next = new_node' is the same as 'hm->table[x]->next = new_node' ('x' is some arbitrary index).

Upvotes: 1

Related Questions