2
\$\begingroup\$

This is a (more or less) continuation of a previous post I made: Generic implementation of a hashtable with double-linked list. I got lots of valuable feedback, so I decided to rewrite the entire module from scratch to improve readability, performance and also to add new features.

Specifications:

  • The hashmap implementation is able to store any data (generic)
  • The hashmap provides collision handling using a single linked list.
  • The hashmap dynamically resizes, to allow for good performance
    • With many collisions (e.g. because of a small bucket count), access-time per element on average is not O(1)
    • Therefore, when a certain threshold is exceeded (150%), the hashmap is resized, to allow for a better distribution of entries, and hence for faster access times.

Review Request:

I'd like to get feedback for the following things:

  • Is the API of the hashmap intuitive/easy to use? Is it consistent (Parameters passed, values returned, Naming conventions etc)
    • I plan on re-using this module in future projects
  • Is there room for performance improvements? (E.g. are there any checks or loops that could be avoided?)
    • I am especially thinking about the functions that directly manipulate the buckets, such as hm_get, hm_set, hm_delete and hm_resize.
  • The test functions in main.c don't need to be reviewed, as they will be replaced with proper unit tests in the future.
  • Are there any bad practices I didn't catch? (e.g Redundant code etc)

hashmap.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <stddef.h>
#include <stdbool.h>

typedef struct entry {
    void *key;
    const void *value;
    struct entry *next;
} entry;

typedef struct hashmap {
    size_t buckets_count;
    size_t entries_count;
    struct entry **buckets;
} hashmap;


size_t hm_compute_hash(size_t key, size_t bucket_count);

/**
 * Initializes a new hashmap instance with the default size
 * @return The hashmap instance
 */
hashmap *hm_new();

/**
 * Returns a pointer to the value from the entry in the hashmap given the key, or NULL, if entry doesn't exist.
 * @param hm The hashmap instance
 * @param key The entry key
 * @return The pointer to the value of the matching entry, or NULL, if key is not valid.
 */
const void *hm_get(hashmap *hm, void *key);

/**
 * Adds a new entry to the hashmap
 * @param phm Pointer to the hashmap instance
 * @param key The entry key
 * @param value The value associated with the key
 * @return Returns 0 if element was added successfully, otherwise a negative value is returned.
 */
int hm_set(hashmap **phm, void *key, const void *value);

/**
 * Deletes an entry from the hashmap
 * @param hm The hashmap instance
 * @param key The key to the entry to delete
 */
void hm_delete(hashmap **phm, void *key);

/**
 * Prints the hashtable in a human readable format to stdout
 * @param hm The hashmap instance
 */
void hm_print(hashmap *hm);

/**
 * Searches an entry by key in a bucket
 * @param hm The hashmap instance
 * @param key The entry key
 * @return Pointer to the entry if found, otherwise NULL
 */
struct entry *hm_entry_search(struct hashmap *hm, void *key);

/**
 * Creates a new entry that is accepted by that hashmap
 * @param key The entry key
 * @param value The value of the entry
 * @return Returns a pointer to the created entry, or NULL, if an error occurred.
 */
struct entry *entry_create(void *key, const void *value);

/**
 * Checks if the hashmap should be expanded to remain efficient
 * @param hm The hashmap instance
 * @return Returns the new bucket size, if expanding is recommended, otherwise 0
 */
int hm_should_grow(struct hashmap *hm);

/**
 * Checks if the hashmap should be shrinked to remain efficient
 * @param hm The hashmap instance
 * @return Returns the new bucket size, if shrinking is recommended, otherwise 0
 */
int hm_should_shrink(struct hashmap *hm);

/**
 * Creates a new larger or smaller hashtable with the given size.
 * All entries get relinked, and the old hashtable instance gets replaced with the new one.
 * @param hm_old The hashmap instance that should be expanded
 * @param new_size The amount of buckets that the new hashmap instance should have
 * @return The new (expanded) hashmap instance
 */
hashmap *hm_resize(struct hashmap *hm_old, size_t new_size);

/**
 * Frees all memory allocated by the hashmap
 */
void hm_free(struct hashmap *hm);

#endif

hashmap.c

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

// Sources used as reference/learning material:
// http://pokristensson.com/code/strmap/strmap.c
// https://github.com/Encrylize/hashmap/blob/master/hashmap.c
// https://github.com/goldsborough/hashtable/blob/master/hashtable.c

hashmap *hm_new() {

    const size_t DEFAULT_HASHMAP_SIZE = 3;

    // Allocate a new hashmap
    hashmap *hm = malloc(sizeof(hashmap));
    if (hm == NULL)
        return NULL;

    // Allocate buckets
    hm->buckets = malloc(sizeof(entry) * DEFAULT_HASHMAP_SIZE);
    if (hm->buckets == NULL) {
        free(hm);
        return NULL;
    }

    // Set initial bucket count, preferably to a prime number
    hm->buckets_count = DEFAULT_HASHMAP_SIZE;
    hm->entries_count = 0;

    // Initialize the buckets, might be obsolete if calloc is used
    for (size_t i = 0; i < hm->buckets_count; ++i) {
        hm->buckets[i] = NULL;
    }

    return hm;
}

struct entry *hm_entry_search(struct hashmap *hm, void *key) {

    // Compute index from key
    size_t index = hm_compute_hash((size_t) key, hm->buckets_count);

    // Get bucket start
    entry *e_curr = hm->buckets[index];

    // Iterate bucket until entry is found, or bucket end was reached
    while (e_curr != NULL) {
        if (e_curr->key == key) {
            break;
        }
        e_curr = e_curr->next;
    }
    return e_curr;
}

const void *hm_get(hashmap *hm, void *key) {

    // Make sure the key is not null
    if (key == NULL) return NULL;

    // Find entry first
    entry *entry_ptr = hm_entry_search(hm, key);

    // Return value of entry, or NULL, if not present
    return entry_ptr == NULL ? NULL : entry_ptr->value;
}

int hm_set(hashmap **phm, void *key, const void *value) {

    struct hashmap *hm = *phm;

    // Make sure the key is not null
    if (key == NULL) return -1;

    /* Search for entry in bucket*/
    entry *entry_ptr = hm_entry_search(hm, key);

    // If entry is already present, overwrite old value with new one
    if (entry_ptr != NULL) {
        entry_ptr->value = value;
        return 0;
    }

    // If entry is not present, create a new one
    struct entry *new_entry_ptr = entry_create(key, value);
    if (new_entry_ptr == NULL)
        return -2;

    // Add newly created entry to the head of the bucket, and update next pointer, if necessary
    size_t index = hm_compute_hash((size_t) key, hm->buckets_count);
    struct entry *current_entry_ptr = hm->buckets[index];

    new_entry_ptr->key = key;
    new_entry_ptr->value = value;
    new_entry_ptr->next = current_entry_ptr != NULL ? current_entry_ptr : NULL;
    hm->buckets[index] = new_entry_ptr;

    hm->entries_count++;

    // Check if the hashmap should be resized
    int hm_size = hm_should_grow(hm);
    if (hm_size != 0) {
        *phm = hm_resize(hm, hm_size);
    }

    return 0;
}

void hm_delete(hashmap **phm, void *key) {

    struct hashmap *hm = *phm;

    // Make sure the key is not null
    if (key == NULL) return;

    // Compute index from key
    size_t index = hm_compute_hash((size_t) key, hm->buckets_count);

    // Iterate through bucket. When entry is found, remove it, and update neighbor entries
    entry *e_prev = NULL;
    entry *e_curr = hm->buckets[index];

    while (e_curr != NULL) {
        if (e_curr->key == key) {
            if (e_prev == NULL) {
                hm->buckets[index] = e_curr->next;
            } else {
                e_prev->next = e_curr->next;
            }
            hm->entries_count--;
            free(e_curr);
            break;
        }
        e_prev = e_curr;
        e_curr = e_curr->next;
    }

    int hm_size = hm_should_shrink(hm);
    if (hm_size != 0) {
        *phm = hm_resize(hm, hm_size);
    }

    return;
}

entry *entry_create(void *key, const void *value) {
    entry *e_new = malloc(sizeof(entry));

    // Check if malloc failed
    if (e_new == NULL) {
        return NULL;
    }

    // Set fields for newly created entry
    e_new->key = key;
    e_new->value = value;
    e_new->next = NULL;

    return e_new;
}

int hm_should_grow(struct hashmap *hm) {
    if (hm->entries_count >= 1.5 * hm->buckets_count) {
        // Double the table size
        return 2 * hm->buckets_count;
    }
    return 0;
}

int hm_should_shrink(struct hashmap *hm) {
    if (hm->entries_count <= 0.5 * hm->buckets_count) {
        // Half the table size
        return hm->buckets_count / 2;
    }
    return 0;
}

hashmap *hm_resize(struct hashmap *hm_old, size_t new_size) {

    // First, create a new hashtable which is bigger in size
    hashmap *hm = malloc(sizeof(hashmap));
    if (hm == NULL)
        return NULL;

    // Allocate new amount of buckets
    hm->buckets = malloc(sizeof(entry) * new_size);
    if (hm->buckets == NULL) {
        free(hm);
        return NULL;
    }

    // Set new bucket count and reset entries count to 0
    hm->buckets_count = new_size;
    hm->entries_count = 0;

    // Initialize the buckets, might be obsolete if calloc is used
    for (size_t i = 0; i < hm->buckets_count; ++i) {
        hm->buckets[i] = NULL;
    }

    // Traverse old and relink entries to new hashmap. This requires re-hashing
    for (size_t i = 0; i < hm_old->buckets_count; ++i) {
        struct entry *e_curr = hm_old->buckets[i];

        while (e_curr != NULL) {
            hm_set(&hm, e_curr->key, e_curr->value);
            e_curr = e_curr->next;
        }
    }

    hm_free(hm_old);

    return hm;
}


size_t hm_compute_hash(size_t key, size_t bucket_count) {
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = (key >> 16) ^ key;
    return key % bucket_count;
}

void hm_print(hashmap *hm) {
    for (size_t i = 0; i < hm->buckets_count; ++i) {
        printf("[%zu] ", i);
        struct entry *e_curr = hm->buckets[i];

        for (; e_curr != NULL; e_curr = e_curr->next) {
            printf("%zu -> ", (size_t)(e_curr->key));
        }
        printf("NULL\n");
    }
}

void hm_free(struct hashmap *hm) {

    // Free all buckets
    for (size_t i = 0; i < hm->buckets_count; ++i) {
        entry *e_curr = hm->buckets[i];
        entry *e_prev = NULL;

        while (e_curr != NULL) {
            e_prev = e_curr;
            e_curr = e_curr->next;
            free(e_prev);
        }
    }

    // Free hashmap struct
    free(hm->buckets);
    free(hm);
}

main.c

#include <stdio.h>
#include "hashmap.h"
#include <assert.h>

void test_hm_set_entry() {
    hashmap *hm = hm_new(3);
    hm_set(&hm, (void *) 1, (void *) 100);
    assert(hm_get(hm, (void *) 1) == (void *) 100);
    hm_free(hm);
}

void test_hm_get_entry() {
    hashmap *hm = hm_new(3);

    hm_set(&hm, (void *) 1, (void *) 100);
    hm_set(&hm, (void *) 2, (void *) 200);
    hm_set(&hm, (void *) 3, (void *) 300);
    hm_set(&hm, (void *) 4, (void *) 400);
    hm_set(&hm, (void *) 5, (void *) 500);
    hm_set(&hm, (void *) 6, (void *) 600);
    hm_set(&hm, (void *) 7, (void *) 700);

    assert(hm_get(hm, (void *) 1) == (void *) 100);
    assert(hm_get(hm, (void *) 2) == (void *) 200);
    assert(hm_get(hm, (void *) 3) == (void *) 300);
    assert(hm_get(hm, (void *) 4) == (void *) 400);
    assert(hm_get(hm, (void *) 5) == (void *) 500);
    assert(hm_get(hm, (void *) 6) == (void *) 600);
    assert(hm_get(hm, (void *) 7) == (void *) 700);

    hm_free(hm);
}

void test_hm_delete_entry() {
    hashmap *hm = hm_new(3);

    hm_set(&hm, (void *) 1, (void *) 100);
    hm_set(&hm, (void *) 2, (void *) 200);
    hm_set(&hm, (void *) 3, (void *) 300);

    hm_delete(&hm, (void *) 2);

    assert(hm_get(hm, (void *) 2) == NULL);
    hm_free(hm);
}

void test_hm_resize() {

    // Allocate new hashmap (3 buckets by default)
    hashmap *hm = hm_new();

    // Make sure 3 buckets are present
    assert(hm->buckets_count == 3);

    /* Add 5 items to trigger resize */
    hm_set(&hm, (void *) 1, (void *) 100);
    hm_set(&hm, (void *) 2, (void *) 200);
    hm_set(&hm, (void *) 3, (void *) 300);
    hm_set(&hm, (void *) 4, (void *) 400);
    hm_set(&hm, (void *) 5, (void *) 500);

    // Check if buckets size was doubled
    assert(hm->buckets_count == 6);

    // Check if elements can still be obtained correctly
    assert(hm_get(hm, (void *) 1) == (void *) 100);
    assert(hm_get(hm, (void *) 2) == (void *) 200);
    assert(hm_get(hm, (void *) 3) == (void *) 300);
    assert(hm_get(hm, (void *) 4) == (void *) 400);
    assert(hm_get(hm, (void *) 5) == (void *) 500);

    // Delete some entries
    hm_delete(&hm, (void *) 1);
    hm_delete(&hm, (void *) 2);

    // Check if table size shrinked again
    assert(hm->buckets_count == 3);

    // Fee hashmap
    hm_free(hm);
}

int main() {
    test_hm_get_entry();
    test_hm_set_entry();
    test_hm_delete_entry();
    test_hm_resize();

    return 0;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's a shame that you say "the test functions shouldn't be reviewed" - the interface usability is likely revealed by whether those test functions are simple or unwieldy. \$\endgroup\$ Dec 30 '20 at 12:42
  • 1
    \$\begingroup\$ @TobySpeight Fair point. I probably worded that poorly. I just meant to say they shouldn't be the main focus of the review. \$\endgroup\$
    – 766F6964
    Dec 30 '20 at 12:59
2
\$\begingroup\$

Interface

We're not consistent in using struct hashmap or the typedef hashmap in the interface. Choose one and use it consistently.

hashmap *hm_new();

Make this a prototype (hashmap *hm_new(void)).

const void *hm_get(hashmap *hm, void *key);
void hm_print(hashmap *hm);
int hm_should_grow(struct hashmap *hm);
int hm_should_shrink(struct hashmap *hm);

I think these should accept a const hashmap*.

void hm_print(hashmap *hm);

It seems limiting to support only stdout as destination. And we probably need to be able to pass functions that know how to print keys and values, or we'll only be able to write the pointer values, meaningless to most users.

typedef struct entry {
    void *key;
    // ...
} entry;

We don't need to be able to modify *key, so this should be a const void*. Otherwise, we can't use (e.g.) string literals as keys, and users will be left wondering how the hashmap might modify the objects they pass in as keys.

struct entry *hm_entry_search(struct hashmap *hm, void *key);
struct entry *entry_create(void *key, const void *value);
int hm_should_grow(struct hashmap *hm);
int hm_should_shrink(struct hashmap *hm);
hashmap *hm_resize(struct hashmap *hm_old, size_t new_size);

Should these (and struct entry) be exposed as the public interface? I think they would be better off inside the implementation, with static linkage. If you want to expose them for unit testing but not to normal user code, then consider using the preprocessor:

#ifndef HASHTABLE_H
#define HASHTABLE_H

/* public interface ... */

#ifdef HASHTABLE_IMPLEMENTATION

typedef struct entry {
    void *key;
    const void *value;
    struct entry *next;
} entry;

/* and the rest of the private interface ... */

#endif

#endif

In the implementation and the tests, you'll need

#define HASHTABLE_IMPLEMENTATION
#include "hashmap.h"

Implementation

hm_should_grow() and hm_should_shrink() return int, but then the result is used as input to hm_resize() which takes a size_t. I think these functions should both return size_t to avoid problems when int is too small (remember that bucket_count is a size_t).

The remaining conversion problems are in the implementation of these functions, where size_t is converted to double, with possible loss of precision:

if (hm->entries_count >= 1.5 * hm->buckets_count) {
if (hm->entries_count <= 0.5 * hm->buckets_count) {

We could simply use long double constants instead (1.5L and 0.5L), but I would favour converting to integer arithmetic (and checking we don't overflow the arithmetic - include <stdint.h>):

if (hm->buckets_count < SIZE_MAX / 2
    && hm->entries_count >= hm->buckets_count + hm->buckets_count / 2) {

As these functions are only used once each, consider inlining them into their call sites:

// Check if the hashmap should be resized
if (hm->buckets_count < SIZE_MAX / 2 && hm->entries_count >= hm->buckets_count * 3 / 2) {
    // Double the table size
    *phm = hm_resize(hm, 2 * hm->buckets_count);
}

Observe that we have the realloc() problem here. If we failed to resize, we got a null pointer back, and didn't free the memory we lost. Both of these are bad, but we can change hm_resize() to return the old pointer rather than a null pointer when it fails. We'll have an inefficient size of map, but that's better than losing data and leaking memory.

// Allocate a new hashmap
hashmap *hm = malloc(sizeof(hashmap));
if (hm == NULL)
    return NULL;

It's good that we take account of allocations here, and clean up correctly. I'd make a couple of small changes:

hashmap *hm = malloc(sizeof *hm);
if (!hm) {
    return hm;
}

It's always good to allocate the size of the dereferenced pointer, rather than writing its type again (it's more important when we're not also declaring the variable, but assigning to one whose definition is distant, and so harder to confirm it's consistent). Explicitly testing ==NULL is redundant; all non-null pointers evaluate true (I find that these explicit tests clutter C code and make it look like Java!). And always using the braces can avoid some errors during maintenance.

// Compute index from key
size_t index = hm_compute_hash((size_t) key, hm->buckets_count);

I don't think this is a good way to compute a hash. Firstly, size_t might not be big enough for a pointer (we should be using uintptr_t, I think). Secondly, it works on object identity, not equality - see below. We need a hash function and an equality function that are tailored for the actual types the user is storing. I think that we should keep two function pointers as part of struct hashmap, and ask the user to pass these in when constructing.

new_entry_ptr->next = current_entry_ptr != NULL ? current_entry_ptr : NULL;

It's equivalent, and much simpler, to write

new_entry_ptr->next = current_entry_ptr;
    struct entry *e_curr = hm_old->buckets[i];

    while (e_curr) {
        hm_set(&hm, e_curr->key, e_curr->value);
        e_curr = e_curr->next;
    }

This matches a for loop much better:

    for (struct entry *e_curr = hm_old->buckets[i];  e_curr;  e_curr = e_curr->next) {
        hm_set(&hm, e_curr->key, e_curr->value);
    }

I note that if hm_set() fails here, we carry on and give back an incomplete copy of the original, with no warning. Users aren't going to like that any more than the leak.

We really need to revisit hm_resize() and make it a lot more robust. Consider every action in it that might fail, and what we should do about that failure. The first two malloc() tests are a good start, once they are changed to return the old map instead of a null pointer. Actually, I think it's fairly simple to fix the call to hm_set(), too:

    for (struct entry *e_curr = hm_old->buckets[i];  e_curr;  e_curr = e_curr->next) {
        if (hm_set(&hm, e_curr->key, e_curr->value)) {
            /* abandon the resize */
            hm_free(hm);
            return hm_old;
        }
    }

Identity vs Equality

As mentioned above, our implementation considers keys to be equal only if they are the same object (i.e. their pointers compare equal). This is a problem for users because it's generally more useful to be able to compare keys by value. Consider this use-case:

int main(void)
{
    hashmap *hm = hm_new();
    if (!hm) { return EXIT_FAILURE; }
    hm_set(&hm, "one", "aon");
    hm_set(&hm, "two", "dà");
    hm_set(&hm, "three", "tri");
    hm_set(&hm, "four", "ceithir");

    char buf[20];
    if (scanf("%19s", buf) == 1) {
        const char *translation = hm_get(hm, buf);
        if (translation) {
            printf("%s → %s\n", buf, translation);
        } else {
            printf("No translation found for %s.\n", buf);
        }
    }

    hm_free(hm);
}

This program never finds the translation, regardless of the input. How are we supposed to retrieve values if we need to obtain the original pointer used to add the item?

We could use variables to retain the keys, but then it's equivalent and simpler to just replace those with variables pointing to the values!

Object ownership and lifetime

The pointers passed in to the map (both keys and values) are not owned by the map (the interface comments don't make this clear, which may leave users wondering). This means that it's the user's responsibility to remove the pointers from the map when destroying the pointed-to objects (either by free() for heap objecs or by the end of scope for local objects).

Users might prefer an interface that copies at least the keys into the map's ownership; perhaps also the values (but then they might have to do more work to store pointers to shared objects, and would benefit from separate functions for value types and reference types).

\$\endgroup\$
6
  • \$\begingroup\$ Thanks for the review - very valuable! I agree with almost everything suggested. As for the value == NULL vs !value comment, I am a bit undecided. I did it for all malloc checks now. Do you suggest using this convention everytime, apart from malloc checking? And yea, I'd love to get some more input on the resize function especially - I feel like there is still plenty of room for improvement. As for the hash-function comment, can you ellaborate on that a bit, I didn't quiet get that. \$\endgroup\$
    – 766F6964
    Dec 30 '20 at 17:03
  • \$\begingroup\$ Regarding cleaning up the interface, - I see why it makes sense to remove these functions from the header. Are you saying I should just add them as static prototypes in the .c file instead? I'd love to comment them, but it feels a bit odd when half of the documented functions are in the header and the other half of them is in the implementation. \$\endgroup\$
    – 766F6964
    Dec 30 '20 at 17:04
  • 1
    \$\begingroup\$ value == NULL vs !value is a personal preference; some prefer the Java style and some prefer the C style. You're consistent, and that's good. For the non-public functions, I would probably make the definitions be static declarations (no separate prototype) and comment them there - users of the functions don't need to know they even exist, and the implementer (you!) knows exactly where to find them. For the hash function, I'll edit (probably tomorrow: it's getting late here) to see if I can make that clearer. \$\endgroup\$ Dec 30 '20 at 19:42
  • \$\begingroup\$ Thanks for the additional feedback. I see the problem with the hashfunction/comparison now, and I'll try to work out a better solution for that. What else do you think can be improved in hm_resize(), since you said "We really need to revisit hm_resize() and make it a lot more robust." ? Also, I think it might be worth changing how parameters are passed to some of the public functions. For example, right now hm_set and hm_delete take a hashmap**, where as hm_get and hm_print take a hashmap* - maybe not the most intuitive API design ... \$\endgroup\$
    – 766F6964
    Dec 31 '20 at 11:01
  • \$\begingroup\$ Actually, it's just hm_set() that wasn't being checked; I've edited that section with a version that abandons the resize if that fails. There's a high likelihood of failing again next time it's called of course; I'm not sure of the best way to deal with that. \$\endgroup\$ Dec 31 '20 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.