Implementing hash table

Question

I am implementing a program to interact with hash table, the data to be hashed is just number. It works but I want to know if there is any error like: memory leak,... in my code and how to improve my code.

Any help would be appreciated.

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

typedef struct node
{
    int val;
    struct node *next;
}node;

int hash(int val, int n);
node **create_hash_table(int n);
node *allocate_new_node(int val, node *next);
void add_new_node(node **hash_table, int n, int val);
void destroy_hash_table(node **hash_table, int n);
bool find(node **hash_table, int n, int val);

int main(){
    //some operation to test the program

    int n=3;    // n is length of hash table
    node **htable=create_hash_table(n);

    add_new_node(htable, n, 1);
    add_new_node(htable, n, -2);
    add_new_node(htable, n, 3);
    add_new_node(htable, n, 4);
    add_new_node(htable, n, 5);

    printf("%d", find(htable, n, -2));

    destroy_hash_table(htable, n);

    return 0;
}

int hash(int val, int n){
    return abs(val) % n;
}

node **create_hash_table(int n){
    node **tmp=calloc(n, sizeof *tmp);  // initialize all pointer to NULL
    if(!tmp){
        fprintf(stderr, "create hash table failed");
        exit(EXIT_FAILURE);
    }
    return tmp;
}

node *allocate_new_node(int val, node *next){
    node *tmp=malloc(sizeof *tmp);
    if (!tmp)
    {
        fprintf(stderr, "allocate new node failed");
        exit(EXIT_FAILURE);
    }
    tmp->val=val;
    tmp->next=next;
    return tmp;
}

void add_new_node(node **hash_table, int n, int val){
    // insert new node to the head of the linked list
    int hashNumber=hash(val, n);
    node *tmp=allocate_new_node(val, hash_table[hashNumber]);
    hash_table[hashNumber]=tmp;
}

void destroy_hash_table(node **hash_table, int n){
    for (size_t i = 0; i < n; i++)
    {
        node *head=hash_table[i];
        node *tmp=head;
        while (head)
        {
            tmp=head->next;
            free(head);
            head=tmp;
        }
        
    }
    
}

bool find(node **hash_table, int n, int val){
    int hashNumber=hash(val, n);
    node *tmp=hash_table[hashNumber];
    while (tmp)
    {
        if (tmp->val==val)
        {
            return true;
        }
        tmp=tmp->next;
    }
    return false;
}

Answer 1

You do leak memory because you forgot to free hash_table in destroy_hash_table(). To correct the issue, you need to free the allocated hash table after freeing all allocated nodes, e.g.

void destroy_hash_table(node **hash_table, int n){
    for (int i = 0; i < n; i++)
    {
        node *head=hash_table[i];
        node *tmp=head;
        while (head)
        {
            tmp=head->next;
            free(head);
            head=tmp;
        }
    }
    free (hash_table);
}

The other issue is just a "nit". Keep your types consistent to prevent comparison between signed and unsigned values in destroy_hash_table(). You pass in n as int, but then declare your loop variable as size_t. Change the size_t to int (or go back through your code and change all int to size_t since n is a counter and can't be negative). The immediate fix is:

    for (int i = 0; i < n; i++)

That seems to be the two I saw.

The final issue in your implementation is you completely omit the concept of load-factor. For efficient operation of the hash table, the number of buckets filled divided by the total buckets is the load-factor. It should never exceed 0.7. You should keep track of the number of buckets filled and available and reallocate/rehash when your load-factor exceeds the target.

You may find Coding up a Hash Table and Hash tables - eternally confuzzled useful in further implementing the load-factor test, and for hash tables generally. A working example of a load-factor implementation is Hashtable for Strings using LH_strhash() Hash Function.. That example hashes strings instead of numbers, but the load-factor handling is the same.

Answer 2

Your C code is not too bad, however you seem not to know much about hash-tables, and since you requested a performance review, I will focus on a brief (and incomplete) exploration of the various ways of designing hash-tables and their performance implications.

Performance

The performance of hash-tables is a widely discussed topic; various benchmarks will typically favor different implementations, with some better at look-ups and others better at rapidly adding/removing elements.

This doesn't mean there is no good guideline however:

1. Minimize the number of cache misses.
2. Don't use modulo.¹

The use of modulo is the relatively easy one. You can limit the table size to powers of 2 (and use a bitmask) or you can have a precomputed list of (typically prime) sizes to go for. I'll mention the trade-offs in the next section.

Avoiding cache misses is a much broader topic, involving various considerations which I'll detail in the following sections.

¹ A good hash-table can perform a look-up within 50 cycles, a modulo instruction on a 64-bits integer is anywhere between 30 and 90 cycles.

No Modulo.

As mentioned, integer modulo (and division) is the one most expensive arithmetic instruction that you can do. It can cost as much as 90 additions.

In general, the simplest way to avoid it is to use a power-of-2 table size.

Some hash-table developers prefer a more complex method using a table of nicely spaced prime numbers as a "safeguard" against poor hash algorithms.

It's up to you to decide whether to trust your users to provide a good hash algorithm, or not.

Static Memory Layout

Typically, a cache miss may occur anytime a pointer to a not-recently-accessed memory area is dereferenced. In turn, this means that:

1. Either pointers should be avoided, as much as possible.
2. Or they should all point within a few memory areas.

There are two types of hash-tables, and each espouses one of those guidelines:

• Open-Addresses Hash Tables will have a single table, without separate "nodes".
  • The best current implementation are Abseil's Swiss Table and Facebook's F14 (for a C++ reference) or Hashbrown (for a Rust reference); they are fairly advanced, complex, and highly-tuned.
• Bucket-List Hash Tables, like yours, will have a table of pointers to nodes, and will cluster those nodes in pools or arenas rather than allocating them one at a time.
  • @skarupke has multiple repositories with very good implementations of many variants.

Hash Caching

Another aspect to discuss is whether to cache the hash, or not.

There are 2 benefits to caching the hash:

• It need not be recomputed when the table is grown.
• It can be used as a quick check before checking for element equality.

In general, hash caching is only interesting for complex hash algorithms and complex elements.

I would not recommend it for a simple integer and an int.

Dynamic Access Pattern

A good layout cannot save you from a poor access pattern, however.

A typical issues of hash-tables are the so-called hash-collisions. The Birthday Paradox is that with 23 students born in the same year (365 days), there's 50% chance of at least 2 of them being born on the same day, despite 23 being an order of magnitude smaller than 365!

The same applies to hashes, and the more elements you have compared to the number of "slots" in your table, the more likely you are to have collisions in the hashes.

Depending on whether you use open-addressing or a bucket-list, things change a bit from here.

Dynamic Access Pattern: Bucket-List

The Bucket-List is the easiest to follow: all elements whose hash%size end up being equal fall into a single bucket, which is a linked-list.

The problem there is that while accessing the bucket itself is O(1), iterating over the linked-list is O(N) where N is the number of elements in the bucket.

This is problematic from both an algorithmic point of view (N elements to check in the worst case), but also from an access pattern point of view as N elements mean N nodes and therefore N+1 memory accesses (and thus N+1 potential cache misses).

A good hash-table will therefore seek to keep the maximum "depth" of a bucket low, ideally equal to 1.

Dynamic Access Pattern: Open-Addressed

Open-Addresses work a bit differently -- I'll let you read up on the differences -- but essentially end up in the same "N elements to check" situation.

Since buckets are typically not materialized, the literature uses the term "probe sequence" to describe the sequence of elements probed in turn when looking up a particular element. A probe sequence is at least as long as the bucket count, but tends to be a little longer as unrelated elements are iterated too.

A Robin-Hood Hash Table with Backshifting Deletion can maintain probe sequences as short as 6 to 7 elements even with a load factor of 90% (that is, 90% of the capacity is filled) which is actually fairly impressive. I invite you to read the algorithm.

How to structure the probe sequence is actually a challenge:

• Linear probing: starting at index hash % size then going with a simple offset increase to (hash + 1) % size, (hash + 2) % size, ... is good for memory access -- CPUs love pre-fetching -- but tend to create clusters with long probe sequences.
• Quadratic probing: squaring the offset at every step is good to avoid clusters -- typically avoiding long probe sequences -- but at the cost of foiling the prefetcher and therefore leading to more cache misses.

The innovation of Swiss Table, F14, etc... is in mixing the two approaches in the same way that a B-Tree improves upon a Binary Tree: they use a table of groups of 16 (or 14, respectively) elements, with linear probing within a group (SIMD accelerated) and quadratic probing across groups.

Dynamic Access Pattern: Conclusion

In general, whether buckets or probe sequences, a good hash table (and hashing algorithm) will want to minimize the number of elements scanned to find the right one, trying to stick to O(1) as much as possible. This is typically achieved by periodically growing the hash table (exponentially), which is accompanied by rehashing its elements (with the new size).

Historically, this is "tuned" using a load-factor, and you may find recommendations for "random" numbers such as 50% or 70%:

• The good thing about a load-factor is that it's easy for the caller to predict when rehashing occurs.
• The bad thing is that it's only losely related to the actual metric of interest: the count of elements in a bucket, or the length of a probe sequence.

I would advise skipping it entirely, and instead allow the user to configure the number of interest: the maximum number of elements which may be inspected when doing a look-up. And any time an insert would cause a bucket or probe-sequence to exceed that number, before inserting the element you first grow and re-hash.

(Caution: you may need to grow and re-hash multiple times)

Applying this knowledge

I personally favor open-addressed hash-tables for personal implementations:

• There's a single memory allocation (the table itself) so there's much less room for memory accidents.
• They're more space efficient: a singly-linked list bucket requires 8 bytes per element (1 pointer) plus padding, more complex buckets add more, whereas a single bit (occupied/free) is necessary for open-addressed hash tables.

In terms of difficulty of implementation, Robin Hood is quite a bit harder than the Swiss Table or F14 (surprisingly) especially with Backshifting Deletion.

So... I'd recommend to just go with the basic layout of Swiss Table, without any of the fancy SIMD stuff (to start, at least).

Example (incomplete) implementation on godbolt:

#define HT_GROUP_SIZE 16

typedef uint32_t(*hash_algorithm_t)(int);

typedef struct {
    uint16_t presence_bits;    /* 1 bit per element in values */
    uint16_t overflow;         /* number of elements that should have
                                  been inserted here, but were displaced
                                  to later groups */
    int values[HT_GROUP_SIZE];
} Group;

typedef struct {
    uint8_t log_number_groups;
    uint16_t max_probe_length;
    uint32_t number_elements;
    hash_algorithm_t hash;
    Group* table;
} HashTable;

Note how compact those are:

• The Group only has 32 bits of overhead, or 2 bits per element.
• The HashTable is only 3 pointers wide on 64-bits architecture, and 4 pointers wide on 32-bits architectures.

The mysterious overflow field is incremented when an element overflows, and decremented when overflowed element is removed. During look-up, it's used to know whether to probe the next group (or not) in case the element is not found. If it were to overflow (!) during insertion, the hash table would be grown and rehashed.

And with that, the interface looks like (I'll let you pick prefixes/suffixes as you wish):

void construct(
    HashTable* hash_table,
    hash_algorithm_t hash,
    uint32_t initial_size,
    uint16_t max_probe_length);

/*  Returns true if contained, false otherwise. */
bool contains(HashTable const* hash_table, int value);

/*  Returns true if inserted, false if the element already is present. */
bool insert(HashTable* hash_table, int value);

/*  Returns true if deleted, false if the element was not present. */
bool remove(HashTable* hash_table, int value);

And internally a void find(HashTable* hash_table, int value, Group** group, uint32_t* index) is defined as helper, defined as:

/*  Finds the group, and index of the element in the group.
 *
 *  - On success: group is not NULL.
 *  - On failure: group is NULL.
 *
 *  Returns the number of elements probed.
 */
uint16_t find(HashTable* hash_table, int value, Group** group, uint32_t* index) {
    uint32_t const mask = (1 << hash_table->log_number_groups) - 1;
    uint32_t const max_probed = hash_table->max_probe_length;

    uint32_t const hash = (*hash_table->hash)(value);

    uint32_t offset = 1;
    uint32_t probed = 0;

    Group* current = hash_table->table + (hash & mask);

    while (true) {
        //  Check current group
        for (uint32_t i = 0;
             i < HT_GROUP_SIZE && probed < max_probed;
             ++i, ++probed)
        {
            bool is_present = current->presence_bits & (1 << i);

            if (!is_present) {
                continue;
            }

            if (current->values[i] != value) {
                continue;
            }

            *group = current;
            *index = i;
            return probed;
        }

        if (current->overflow == 0) {
            break;
        }

        if (offset > UINT32_MAX / 2) {
            break;
        }

        current = hash_table->table + ((hash + offset) & mask);

        /* There are other probing sequences, such as *= 1.5, but honestly
           if offset overflows, the probing sequence is way too long... */
        offset *= 2;
    }

    *group = NULL;
    *index = HT_GROUP_SIZE;
    return probed;
}

And based on that, implementing the other functions is relatively easy.