Thread: implementing a hashmap

Hello,

I want to implement a hashmap and get a segfault again when testing my program. It seems that I cannot access

Code:

test->hash

as it throws the segmentation fault error. I suspect that I should use

Code:

 Entry* test = (Entry*) malloc(sizeof(Entry));

instead. Why does it not work without malloc()?

Code:

#include <stdio.h>


#define TABLE_SIZE 16


typedef int Data;
typedef struct entry Entry;


struct entry {
  Data value;
  unsigned int hash;
  Entry* next;
};


void insert_into(Entry* table[], Data data){
  Entry entry = {data, 0, NULL};
  entry.hash = ((unsigned int) &entry) % TABLE_SIZE;
  if (table[entry.hash] == NULL){
    table[entry.hash] = &entry;
  }
}


int main(){
  Entry* test = {1,0,NULL};
  printf("%p\n", test);
  test->hash = (unsigned int) test;
  printf("%d\n", test->hash);


  Data data_points[5] = {3,5,2,12,9};
  Entry* lookup_table[TABLE_SIZE];


  for (int i = 0; i < 5; i++){
    insert_into(lookup_table, data_points[i]);
  }


  for (int i = 0; i < TABLE_SIZE; i++)
    printf("%i = %s\n", i, lookup_table[i]->value);
  return 0;
}

> table[entry->hash] = entry;
This should be
table[entry->hash % TABLE_SIZE] = entry;

And then you need to deal with duplicates.

Also, don't cast the return result of malloc. There is no need to do that in C.

So now I have corrected my mistakes. For some reason I get a segfault when trying to print the contents of the lookup table. Can anyone tell me why?

Code:

#include <stdio.h>
#include <stdlib.h>


#define TABLE_SIZE 16


typedef int Data;
typedef struct entry Entry;


struct entry {
  Data value;
  unsigned int hash;
  Entry* next;
};


void insert_into(Entry* table[], Data data){
  Entry* entry = malloc(sizeof(Entry));
  entry->hash = data;
  entry->value = data;
  entry->next = NULL;
  if (table[entry->hash % TABLE_SIZE] == NULL) {
    table[entry->hash % TABLE_SIZE] = entry;
    return;
  }
  Entry* it = table[entry->hash % TABLE_SIZE];
  for (; it != NULL; it = it->next)
    ;
  it->next = entry;
}


int main(){

  Data data_points[5] = {3,5,2,12,9};
  Entry* lookup_table[TABLE_SIZE];


  for (int i = 0; i < TABLE_SIZE; i++){
    lookup_table[i] = NULL;
  }


  for (int i = 0; i < 5; i++){
    insert_into(lookup_table, data_points[i]);
  }

// a segmentation fault occurs here, why?
  for (int i = 0; i < TABLE_SIZE; i++)
    printf("%d = %d\n", i, lookup_table[i]->value);
  return 0;
}

Because not every table entry has an entry.
And some have more than one.

Code:

if ( lookup_table[i] ) {
    printf("%d = %d\n", i, lookup_table[i]->value);
    // this is now a list, traverse it.
}