Hashmap

uint64_t no_hash(void *pointer) {
  return 0;
}

Our first hash function is more of a nice to have during testing as opposed to an actually useful hashing function. It is quite fast however 🤓. We will later use this to test how our hashmap handles the case where multiple elements produce the same hash, and since they will all produce 0 this is a great way to test that.

uint64_t basic_hash(void *pointer) {
  return (uint64_t)pointer ^ ((uint64_t)pointer >> 32);
}

Our first real hash function is relatively simple, it XORs the bottom half and the lower half together and returns the result. Not the best hash function, but with only 2 instructions it is about as quick as we can get without returning a constant value.

uint64_t fnv_hash(void *pointer) {
  if (!pointer) { return 0; }
  // Prime and offset basis values for 64-bit values
  uint64_t hash = 14695981039346656037ull;
  uint64_t byte_pointer = (uint64_t)pointer;
  for (int i = 0; i < 8; i++) {
    hash *= 1099511628211;
    hash ^= byte_pointer & 0xFF;
    byte_pointer >>= 8;
  }
  return hash;
}

The second hash function is much more complex, and we should expect a lower rate of collisions because of this. Even with added complexity the actual function should still be fairly quick to compute. This is something we will be able to measure once our hashmap is fully implemented.

Basic Hash
Original: 0x5589081942a0  |  Hashed: 0x558908191729
Original: 0x5589081942c0  |  Hashed: 0x558908191749
Original: 0x5589081942e0  |  Hashed: 0x558908191769
FNV Hash
Original: 0x5589081942a0  |  Hashed: 0x6fb6159253d2b95a
Original: 0x5589081942c0  |  Hashed: 0x63c1db2f83d3da3a
Original: 0x5589081942e0  |  Hashed: 0xe114c79be4e359a

For a first test I made 3 pointers just like you might when making 3 C-style strings. These values are on the stack, so they are all just a few bytes apart, which is a great test for our hash functions. There is a term called the avalanche effect in which a single bit change in the value to be hashed produces a very large change in the resulting hash. In order for our hash function to minimize collisions we should choose a function that has a very high avalanche effect.

Our more basic hash function does nothing to the upper 32 bits, and the lower 32 bits only differ by their second hexadecimal digit. This may not be that big of an issue with a large table, but a smaller table may expose some issues.

Our last hash is called an FNV hash, which produces vastly different has values from small differences in input values. It works by starting with a base seed, then apply 2 transformations to this seed per byte in our input number.

We also have a string hashing function that is based on the original FNV hash, just adapted to using the bytes of a string as opposed to the bytes of a number.

How does a hashmap actually store the data we want to retrieve?

At first, it seems like it would make sense to just store the value, since we know that its key will only ever map to one index. However, this quickly falls apart when collisions come into the picture. If all of our “boxes” just stored the values we would have no way to tell them apart in case of a collision. Instead, we store elements as a pair of their key and value.

The structure of this pair is not as important to our implementation, and may vary from language to language. We will use a struct here, python may use a tuple, others may use a class. The point here is that we need our elements to be either a fixed size, or something we can point to in memory. Our struct will contain two 8-byte values, totaling to a 16-byte struct.

typedef struct {
  void *key;
  uint64_t value;
} pair;

With each element wrapped up in a struct we can easily probe along and find when our key matches, or with separate chaining we will walk the linked list until we find our desired key. Due to our hash being a pure function, we know that our resulting index and probing order will always be the same for any given key. This means if we do not find a match, we know with 100% certainity that the key is not present in our map.

// Returns TOMBSTONE if element is not found (marker element)
// returns value if found
uint64_t hashmap_get(hashmap *h, void *key) {
  if (!h) {
    fprintf(stderr, "Not a valid hashmap, did you init it?");
    exit(EXIT_FAILURE);
  }
  if (!key) {
    fprintf(stderr, "Attempting to get with a NULL key");
    exit(EXIT_FAILURE);
  }
  pair pair_ptr;
  uint64_t index = h->hash_func(key) % h->capacity;
  for (int i = 0; i < h->capacity/2 + 1; i++) {
    uint64_t new_index = (index + (i * i)) % h->capacity;
    pair p = h->array[new_index];
    switch ((uint64_t)p.key) {
      case 0:
        return TOMBSTONE;
    default:
      if (p.key == key) {
        return h->array[new_index].value;
      }
    }
  }
}

This is our introduction to the main strategy we will use throughout the hashmap to find an element. Our first step is to rehash the key, then we follow the a quadratic probing sequence, which we will cover in more depth soon. At each step in our check we look for equality on our keys, which just compares 2 void* values, not the values they may or may not point to.

Lets now look at how we can initialize our hashmap, and eventually clean up the memory is uses.

// `hash` is any hash function that takes a `void*` and returns a `uint64_t`
// Set `load_factor` to `0` for default value
// Set `size` to `0` for default value
hashmap hashmap_init(hash_function hash, equals_function eq, float load_factor, int capacity) {
  if (!hash) {
    fprintf(stderr, "Please specify a valid hash function\n");
    exit(EXIT_FAILURE);
  }
  if (!equals_function) {
    fprintf(stderr, "Please specify a valid equald function\n");
    exit(EXIT_FAILURE);
  }
  if (!load_factor) {
    load_factor = 0.5;
  }
  if (!capacity) {
    capacity = 11;
  }

  pair *array = calloc(capacity, sizeof(pair));
  if (!array) {
    perror("calloc failed");
    exit(EXIT_FAILURE);
  }
  return (hashmap){load_factor, capacity, 0, 0, hash, eq, array};
}

// Frees all dynamically associated memory with a hashmap
// the hashmap becomes invalid after calling free
void hashmap_free(hashmap *h) {
  if (!h) {
    return;
  }
  free(h->array);
  h = NULL;
}

Don’t worry too much about the ability to pass in a hashing function, or an equals function for now. We will discuss those later. For now let’s focus on the memory allocation, for which I prefer to use calloc. I find working with zereod our memory to not only be safer, but faster to catch any errors in my algorithms. If the user passes a specific capacity we use that, otherwise we set it to a reasonable prime number.

Once the user is done with the hash map we need some way to clean up all the memory that it occupies. Since we are focusing on an open addressing implementation we only need to free the memory allocated for our array. The last thing here is to set the hashmap itself to NULL, this is a good idea when cleaning up our hashmap, as the rest of our user facing API will be setup to fail if the hashmap is NULL.

One of the main characteristics of a hashmap is its O(1) insertion and retrieval time. If you’re familiar with an array we know that insertion and lookup with a known index is constant time, but forcing our users to keep track of every last index would be quite a pain. This is where a hashmap comes in. Instead of having users keep track of specific indexes, or performing a search to find a specific element, we will combine the backing storage of an array and a hashing function to figure out where each item should be placed.

This is great because adding an item to an array is as simple as adding an offset to a pointer and writing to some memory, which runs at a constant time, no matter the amount of elements. We load a value into a register, and store it with a known offset into the array. Even in RISC-V assembly we only have 2 instructions to store our value.

In order to get the index for each element, we have to somehow reduce its value down to our array size. The hash functions return uint64_t values, which are much larger than our table indexes allow. The easiest way to “clamp” this hash value to our array is with a modulo operation. This allows us to take a value in the billions, and reduce it down to any table size. If our array has a size of 14 let’s see what indexs our different hash functions product.

Basic Hash
Hashed: 0x55e8f951e748  |  [14]Array Index 6
Hashed: 0x55e8f951e728  |  [14]Array Index 2
Hashed: 0x55e8f951e708  |  [14]Array Index 12
FNV Hash
Hashed: 0xa7130ebc6001a9f8  |  [14]Array Index 4
Hashed: 0x5c21814efdd7ab98  |  [14]Array Index 12
Hashed: 0x9eb867d5a95e6e38  |  [14]Array Index 4

Huh. Even our more advanced hash function, with vastly different values, ends up producing the same index twice. Well that’s not good for our users, if they try to store 2 different values we would end up overwriting the first value. We can continue to increase our array size to limit the amount of collisions, but we reach a point where we end up with numerous empty spaces.

We will cover 2 different groups of strategies when it comes to resolving collisions in a hashmap.

At this point we would have a nearly complete hashmap, with the ability set and get any arbitrary pair. The last thing we need to implement for our user facing API is the removal of an element.

Separate Chaining

In the case of separate chaining this is no different from a removal of an element in our linked list. Nothing too complicated to handle, other than checking our position in the list and updating the head if necessary.

Open Addressing

Our implementation with open addressing will be more complicated to handle. At first, it may seem like we could just zero out the memory at that array index and call it a day. Which we could easily do, but this would make our probing very inefficient. Instead of stopping our probe when we hit an empty index, we would need to continue probing until we loop back around to an element we have already checked. On a small scale this probably isn’t too bad, but once we get into the 1000s of elements we would be looking for ways to optimize lookups.

Instead, we can use a concept called a “tombstone”.

The basis of our entire open addressing hashmap will have to change with the introduction of tombstones. Insertion, retrieval, and deletion will all have to take this into account when probing along. Without introducing the complications of deletion they first 2 seemed simple, but our probing algorithm will be taking these into consideration. A tombstone essentially tells us that an element used to be here, so we should continue on searching.

// Returns a pointer to the pair if found,
// otherwise returns NULL
uint64_t hashmap_delete(hashmap *h, void *key) {
  if (!h) {
    fprintf(stderr, "Not a valid hashmap, did you forget to init it?");
    exit(EXIT_FAILURE);
  }
  if (!key) {
    fprintf(stderr, "Attempting to delete a NULL key");
    exit(EXIT_FAILURE);
  }
  uint64_t index = h->hash_func(key) % h->capacity;
  for (int i = 0; i < h->capacity/2 + 1; i++) {
    uint64_t new_index = (index + (i * i)) % h->capacity;
    pair p = h->array[new_index];
    switch ((uint64_t)p.key) {
      case 0:
        return TOMBSTONE;
    case TOMBSTONE:
      continue;
    default:
      if (p.key == key) {
        uint64_t temp_val = p->value;
        h->size--;
        p->key = (void*)TOMBSTONE;
        p->value = 0;
        return temp_val;
      }
    }
  }
  return NULL;
}

This also slightly complicates the concept of insertion. We can no longer find the first “free” space to insert our element. We may run into the case where we find a tombstone space while we probe along, but if we were to instantly insert the new element into this space we run the risk of having a duplicate key in the map. For this reason we have to run our entire probing sequence on an insert before deciding to insert ourselves at the first available spot. Of course if we do happen to run into a truly empty space before any tombstones we are safe to insert ourselves there instead.

void hashmap_insert(hashmap *h, void *key, uint64_t value) {
  if (!h) {
    fprintf(stderr, "Not a valid hashmap, did you forget to init it?");
    exit(EXIT_FAILURE);
  }
  if (!key) {
    fprintf(stderr, "Attempting to insert a NULL key");
    exit(EXIT_FAILURE);
  }
  pair new_pair = {key, value};

  // Find if the pair already exists
  pair *pair_ptr; // Set to NULL if it doesn't exist
  uint64_t index = h->hash_func(key) % h->capacity;
  for (int i = 0; i < h->capacity/2 + 1; i++) {
    uint64_t new_index = (index + (i * i)) % h->capacity;
    pair p = h->array[new_index];
    switch ((uint64_t)p.key) {
    case 0:
      pair_ptr = NULL;
    case TOMBSTONE:
      continue;
    default:
      if (p.key == key) {
        pair_ptr = &h->array[new_index];
      }
    }
  }

  // Pair already exists
  if (pair_ptr) {
    *pair_ptr = new_pair;
    return;
  }

  // Pair does not yet exist
  if (((float)h->size + 1) / (float)h->capacity > h->load_factor) {
    // We are over capacity
    hashmap_resize(h, 0);
    hashmap_insert(h, key, value);
    return;
  }

  pair *first_avail;
  index = h->hash_func(key) % h->capacity;
  for (int i = 0; i < h->capacity/2 + 1; i++) {
    uint64_t new_index = (index + (i * i)) % h->capacity;
    pair p = h->array[new_index];
    switch ((uint64_t)p.key) {
    case 0:
      first_avail = &h->array[new_index];
      break;
    case TOMBSTONE:
      first_avail = &h->array[new_index];
      break;
    default:
      continue;
    }
  }

  h->size++;
  *first_avail = new_pair;
}

This also complicates are retrieval logic slightly. Instead of either finding the element or not we now have to consider a TOMBSTONE, which just tells our function to continue searching becuase the element may be past this point.

// Returns TOMBSTONE if element is not found (marker element)
// returns value if found
uint64_t hashmap_get(hashmap *h, void *key) {
  if (!h) {
    fprintf(stderr, "Not a valid hashmap, did you forget to init it?");
    exit(EXIT_FAILURE);
  }
  if (!key) {
    fprintf(stderr, "Attempting to get a NULL key");
    exit(EXIT_FAILURE);
  }
  pair pair_ptr;
  uint64_t index = h->hash_func(key) % h->capacity;
  for (int i = 0; i < h->capacity/2 + 1; i++) {
    uint64_t new_index = (index + (i * i)) % h->capacity;
    pair p = h->array[new_index];
    switch ((uint64_t)p.key) {
      case 0:
        return TOMBSTONE;
    case TOMBSTONE:
      continue;
    default:
      if (p.key == key) {
        return h->array[new_index].value;
      }
    }
  }
}

You may have noticed at this point that we are repeating a lot of code. Now, I am not exactly a fan of hard rules in coding like number of lines in a function, or overly descriptive variable names, but breaking out common logic into a function that has many benefits. In our use case we want to avoid having to change our searching logic in 3 places at once. Let do exactly that, create a function that returns a pointer to the element we are searching for.

// Returns a pointer to the pair if found,
// otherwise returns NULL
pair *hashmap_find(hashmap *h, void *key) {
  if (!h) {
    fprintf(stderr, "Not a valid hashmap, did you forget to init it?");
    exit(EXIT_FAILURE);
  }
  if (!key) {
    fprintf(stderr, "Attempting to find a NULL key");
    exit(EXIT_FAILURE);
  }
  uint64_t index = h->hash_func(key) % h->capacity;
  for (int i = 0; i < h->capacity/2 + 1; i++) {
    uint64_t new_index = (index + (i * i)) % h->capacity;
    pair p = h->array[new_index];
    switch ((uint64_t)p.key) {
      case 0:
        return NULL;
    case TOMBSTONE:
      continue;
    default:
      if (p.key == key) {
        return &h->array[new_index];
      }
    }
  }
  return NULL;
}

There we go, just a more generic version of the logic we have used in finding, insertion, and removal. Let’s see how this fits into the functions we have already written.

// Returns TOMBSTONE if element is not found
// returns value if found
uint64_t hashmap_get(hashmap *h, void *key) {
  pair *p = hashmap_find(h, key);
  if (!p) {
    return TOMBSTONE;
  } else {
    return p->value;
  }
}

// Returns TOMBSTONE if element is not found
// returns value if found
uint64_t hashmap_delete(hashmap *h, void *key) {
  pair *p = hashmap_find(h, key);
  if (!p) {
    return TOMBSTONE;
  } else {
    uint64_t tmp_val = p->value;
    h->size--;
    p->key = (void*)TOMBSTONE;
    p->value = 0;
    return tmp_val;
  }
}

The logic doesn’t change, but both functions get much shorter. You may also notice that we were able to consolidate our error checking into the hashmap_find() function. Our insertion function won’t be quite as easy to change. We can reuse the finding logic for the first half, but we also need a way to scan for the first available element, as we discussed above with the addition of tombstones. We will also break this out into a function, and make our insertion function much easier to understand.

// Returns a pointer to the first available spot,
// empty or TOMBSTONE
pair *hashmap_first_avail(hashmap *h, void *key, int *collisions) {
  uint64_t index = h->hash_func(key) % h->capacity;
  for (int i = 0; i < h->capacity/2 + 1; i++) {
    uint64_t new_index = (index + (i * i)) % h->capacity;
    pair p = h->array[new_index];
    switch ((uint64_t)p.key) {
      case 0:
        *collisions = i;
        return &h->array[new_index];
    case TOMBSTONE:
        *collisions = i;
        return &h->array[new_index];
    default:
      continue;
    }
  }
  return NULL;
}

Instead of returning a pointer to a match or NULL, we return the first spot available for this element. Let’s now implement this in our insert function.

void hashmap_insert(hashmap *h, void *key, uint64_t value) {
  pair *p = hashmap_find(h, key);
  pair new = {key, value};

  // Key already exists
  if (p) {
    *p = new;
    return;
  }

  if (((float)h->size + 1) / (float)h->capacity > h->load_factor) {
    // We are over capacity
    hashmap_resize(h, 0);
    hashmap_insert(h, key, value);
    return;
  }

  int collisions;
  pair *first_avail = hashmap_first_avail(h, key, &collisions);

  h->size++;
  h->collisions += collisions;

  *first_avail = new;
}

Great, our insert function is reusing the find logic that we extracted out into a function, meaning our code now only has to change in one place!

You may have been asking about the hashmap_resize() function at this point. How does that work?

With our user facing API covered now we have to talk about the management of all this data.

Earlier we discussed the concept of load factor, and we would ideally like to keep this as low as possible (and below 50% in the case of quadratic probing). We wouldn’t be able to accomplish this without dynamically allocating memory, so that is exactly what we have to do. However, we should probably keep a few things in mind when decided how our hashmap should behave.

The C programming language doesn’t support generics, some people like this, others don’t. I don’t really have a side in the argument, but from a library author perspective, especially when writing a data structure, we would like our users to be able to use any datatype. So, how can we achieve this? Function pointers.

We already saw these earlier when we allowed for our hashing function to be changed out, so let’s start there. Our hashmap currently takes a void* key and a uint64_t value, with our hash function using the 8-byte value of the key directly. How could we change this to support strings? Well, our hash function takes in an 8-byte value, what else is 8-bytes? That’s right, pointers on a 64-bit machine. So we have 2 categories of hash functions, those that directly compare the values, and those that compare what those 8-bytes point to. Can we take advantage of this to allow our hashmap to support string keys?

uint64_t fnv_string_hash(void *pointer) {
  if (!pointer) {
    return 0;
  }
  uint64_t hash = 14695981039346656037ull;
  const char *str = (const char*)pointer;
  while (*str) {
    hash *= 1099511628211;
    hash ^= *str++;
  }
  return hash;
}

With a few small changes to our original fnv_hash it now supports C-style strings. Instead of iterating through the 8 individual bytes of a void*, we walk through the bytes of a string until we find a null terminator. That wasn’t bad at all, let’s see how this works in our hashmap.

int main() {
  hashmap h = hashmap_init(&fnv_string_hash, &value_equals, 0, 0);

  char *b = (char*)malloc(64);
  strcpy(b, "Billy");
  hashmap_insert(&h, "Billy", 25);
  printf("Key %s has the value %d\n", b, hashmap_get(&h, b));

  hashmap_free(&h);
}

Key Billy has the value -1

Uh oh. Why didn’t that work?

It has to do with how we are comparing the keys. If we instead directly compared the string literal "Billy" both times this would have worked. This is because of how C stores string literals under the hood.

#include <stdio.h>

int main() {
  char *a = "Billy";
  char *b = "Billy";
  if (a == b) {
    puts("Equal");
  } else {
    puts("Not Equal");
  }
  printf("a: %p\n", a);
  printf("b: %p\n", b);
}

When we write "Billy" in our code twice the compiler realizes that we are referencing the same string twice. So it will insert the string once in the binary, and then just reference its memory address with a and b. What does this mean for us when we compare keys?

In a higher level language the = operator is often overloaded for the primative types present in the language. This holds true for numbers in C, but strings in C are treated differently. Instead of referencing a string directly we only have its memory address, and we have to choose how to handle that, usually by continuing until we find a null terminator.

If we want our hashmap to be able to handle string keys we should write our own function to perform this comparison. You may have noticed earlier that our hashmap_init() function took in an equals function. This is another example of generic programming, where we allow the user to define custom behavior for their use case.

// Compares 2 null terminated C-style strings
bool str_equals(void *a, void *b) {
  return strcmp((const char*)a, (const char*)b) == 0;
}

The code itself is just running strcmp, but a user could override this functionality to handle any type, as simple as an integer, or as complicated as a struct.

With this in place our previous example should now work.

int main() {
  hashmap h = hashmap_init(&fnv_string_hash, &value_equals, 0, 0);

  char *b = (char*)malloc(64);
  strcpy(b, "Billy");
  hashmap_insert(&h, "Billy", 25);
  printf("Key %s has the value %d\n", b, hashmap_get(&h, b));

  hashmap_free(&h);
}

Key Billy has the value 25

There we go! Our hashmap is now able to handle keys directly by value, and by the strings they may reference.