Hashtable: Segmentation fault when inserting - C

Question

I am trying to implement a hashtable, in which the table would be an array of "buckets" in which each one contained user information, my code:

#define tam_inicial 23

typedef struct user{
    char nick[6];
    char nome[26];
}user;

typedef struct hashtable{
    int tam;
    user **baldes;
}hashtable;

int tam = tam_inicial;

hashtable * create() {
    hashtable *htable = malloc(sizeof(htable));
    htable->tam = tam_inicial;
    htable->baldes = calloc(tam_inicial, sizeof(htable->baldes));

    return htable;
}

int hash(char *string) {
    int hashVal = 0;
    for( int i = 0; i < strlen(string);i++){
        hashVal += (int)string[i];
    }

    return hashVal % tam;
}

bool isPrime(int num){
    if(num==2){
        return true;
    }
    if(num % 2==0){
        return false;
    }
    for(int i=3; i*i<num; i+=2){
        if(num%i==0){
            return false;
        }
    }
    return true;
}

int Prime_num(int old_size){
    for(int i = old_size; i < old_size * 2 +10; i++){
        if(isPrime(i) && i >= 2*old_size){
            return i;
        }
    }
}

hashtable *resize_HashTable(hashtable *HashTable){
    if(load_factor()){
        int tmp = Prime_num(tam);
        HashTable = realloc(HashTable, tmp * sizeof(user));
        tam = tmp;
    }
    return HashTable;
}

void inserir(hashtable *HashTable, char *nome, char *nick){
    HashTable = resize_HashTable(HashTable);
    int hash_value = hash(nick);
    while(HashTable->baldes[hash_value] != 0 && hash_value < HashTable->tam){
        hash_value++;
    }
    strcpy(HashTable->baldes[hash_value]->nome, name);
    strcpy(HashTable->baldes[hash_value]->nick, nick);
    HashTable->tam = HashTable->tam++;
}

For some reason these 2 lines give error "Segmentation fault":

strcpy(HashTable->baldes[hash_value]->nome, name);
strcpy(HashTable->baldes[hash_value]->nick, nick);

It’s as if I can’t access the variable "name" and "nick" of the struct user to put the names/nicks there

Any reason for this to happen? Thanks in advance.

Answer 1

Watch this excerpt:

HashTable = resize_HashTable(HashTable);
int hash_value = hash(nick);
while(HashTable->baldes[hash_value] != 0 && hash_value < HashTable->tam){
    hash_value++;
}

Let’s assume that HashTable->tam is 23 and that the hash_value returned be -1904468. What will happen? Segmentation fault because you will be accessing HashTable->baldes[hash_value] out of the right size.

I think what you have to do is this:

HashTable = resize_HashTable(HashTable);
int hash_value = hash(nick);
int balde = hash_value % HashTable->tam;
if (balde < 0) balde += HashTable->tam;
while (HashTable->baldes[balde] != 0 && balde < HashTable->tam) {
    balde++;
}

But that only solves one part of the problem. For if that while get to the end of the array (especially if it has already started there) and not find a free place to put the name/nick, it will drop out of the array boundary and give a Segmentation fault instead of going back to the beginning. Therefore, you must do this:

HashTable = resize_HashTable(HashTable);
int hash_value = hash(nick);
int balde_inicial = hash_value % HashTable->tam;
if (balde_inicial < 0) balde_inicial += HashTable->tam;
int balde = balde_inicial;
while (HashTable->baldes[balde] != 0 && balde != balde_inicial - 1) {
    balde++;
    balde %= HashTable->tam;
}

If the HashTable be full, it will be an infinite loop. Therefore, it is important that the resize_HashTable ensures that a HashTable full will never be returned.

[EDITED]: Ok, the question has been edited and its function hash never returns values like this. However, its function hash should not be based on size initial table hash. If the table size changes with the resize_HashTable, the function hash does not change together. Also, you can have multiple tables in memory each with a different size.

Another problem is that if the string is large enough, the function hash will overflow and may return a negative value.

The solution is simply to take the % tam of function hash. Who has to worry about this to know in which bucket the dice will be placed is the hash table and not the function of hash that does not know in which table will be used. The function hash only cares about returning an arbitrary number (possibly negative) that represents the string.