Daniel Daniel - 1 year ago 77
C Question

Segfault in simple hash table

I am trying to write a simple hash table in C and I am getting a very strange segfault when testing it with the code shown my


The Design: I have a hash table with an underlying array of size 10,000. I hold a double pointer to the start of an array of
struct node_t
) pointers. When I want to
something into the hash table, I check if the
element at the appropriate location is
. If it is, I create a new node to fill the spot, otherwise, if there are collisions, I build a linked list off of the colliding node.

The Scenario: In
, I am trying to
the number 3328 into the hash table. Instead, the program segfaults. This makes no sense to me as the previous
works fine and you can clearly see that I set all the initial pointers to NULL. As far as I know, the pointer that refers to hash table location 3328 is not getting set to NULL because when I dereference it in the
function, that's when it segfaults. My main function looks like it should set all the pointers to NULL just fine though...

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

int TABLE_SIZE = 10000;

typedef struct node_t {
int key;
int value;
struct node_t* next;
} node;

node** table;

inline node** get_node_address(int key) {
key = (key > -key ? key : -key) % TABLE_SIZE;
return (node**) (table + key * sizeof(node*));

inline node* new_node(int key, int value) {
node* n = malloc(sizeof(node));
n->key = key;
n->value = value;
n->next = NULL;
return n;

void put(int key, int value) {
node** n = (node**) get_node_address(key);
node* iterator = (node*) *n;

if (*n == NULL) {
*n = new_node(key, value);
} else {
while (iterator->next != NULL)
iterator = iterator->next;

iterator->next = new_node(key, value);

int* get(int key) {
node* iterator = (node*) *get_node_address(key);

while (iterator != NULL && iterator->key != key) {
iterator = iterator->next;

if (iterator == NULL)
return NULL;
return &(iterator->value);

int main() {

int i;
table = malloc(sizeof(node*) * TABLE_SIZE);
memset(table, 0, sizeof(node*) * TABLE_SIZE);

for (i = 0; i < TABLE_SIZE; i++) {
table[i] = NULL;
printf("setting %x\n", &table[i]);

printf("before bad: %x\n", *get_node_address(3327));
printf("bad address: %x\n", *get_node_address(3328));
printf("last address: %x\n", table + sizeof(node*) * TABLE_SIZE);


put(3328, 3338);
printf("%d", *get(3328));

return 0;

Answer Source

There's at least one problem:

inline node** get_node_address(int key) {
      key = (key > -key ? key : -key) % TABLE_SIZE;
      return (node**) (table + key * sizeof(node*)); /* <---- */

You mustn't multiply key. Because of the way pointer arithmetic works in C, table + key yields the key-th element.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download