DEV Community: Neo Sahadeo

Hashmap in C

Neo Sahadeo — Tue, 02 Sep 2025 06:25:24 +0000

The full block of code is listed below.

Introduction

This is a short post on how to write a simple hashmap in C. Hashmaps generally have 3 components

Hash array
Hasher function
A data-structure

The hasher function

The purpose of the hasher is to take in an input and generate a fixed-size number.

In our case we will use the djb2 (Dan J. Bernstein) algorithm because it does 2 things for us,

It generates a hashed value
It distributes values well

long hash(char *str) {
  unsigned long hash = 5381;
  int c;

  while ((c = *str++))
    hash = ((hash << 5) + hash) + c;

  return hash;
};

The hash array (table)

We then need to allocate some memory for the array; this can be done however you want.

I went with

void *bucket_array[1024] = {NULL};

A 'bucket' refers to an element within a hashmap, this because the element is another data-structure.

The Data-Structure

An easy to implement data-structure is a linked-list.

typedef struct Node {
  char *key;
  char *data;
  struct Node *next;
} Node;

The add function

Now, we can implement a system to:

hash our value
store it

The code itself is quite self-explanatory. We first get an index value by hashing our string and taking the modulus with the size of our buffer.

Then we check if there is already a value at that index, if no, create a new node, set the data and key and update the index position.
If yes, then scan through the index to see which node matches our key, if we find a match, update that value with our new data.

int add(char *str, char *data, int size, void **buffer) {
  int index = (hash(str) % (long)size);
  if (buffer[index] == NULL) {
    // no bucket exists
    Node *node = malloc(sizeof(Node));
    node->key = str;
    node->data = data;
    buffer[index] = node;
  } else {
    // bucket exists
    Node *linked_list = buffer[index];
    bool exists = false;

    if (strcmp(str, linked_list->key)) {
      exists = true;
    } else {
      while (linked_list->next != NULL) {
        if (strcmp(str, linked_list->key)) {
          exists = true;
        } else {
          linked_list = linked_list->next;
        }
      }
    }
    if (exists) {
      Node *new_node = malloc(sizeof(Node));
      new_node->key = str;
      new_node->data = data;
      linked_list->next = new_node;
    } else {
      linked_list->data = data;
    }
  }
  return index;
}

Code

As for the other functions, I'll leave it as a exercise to the reader.

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

typedef struct Node {
  char *key;
  char *data;
  struct Node *next;
} Node;

Node *head = NULL;
Node *current = NULL;

long hash(char *str) {
  unsigned long hash = 5381;
  int c;

  while ((c = *str++))
    hash = ((hash << 5) + hash) + c;

  return hash;
};

int add(char *str, char *data, int size, void **buffer) {
  int index = (hash(str) % (long)size);
  if (buffer[index] == NULL) {
    // no bucket exists
    Node *node = malloc(sizeof(Node));
    node->key = str;
    node->data = data;
    buffer[index] = node;
  } else {
    // bucket exists
    Node *linked_list = buffer[index];
    bool exists = false;

    if (strcmp(str, linked_list->key)) {
      exists = true;
    } else {
      while (linked_list->next != NULL) {
        if (strcmp(str, linked_list->key)) {
          exists = true;
        } else {
          linked_list = linked_list->next;
        }
      }
    }
    if (exists) {
      Node *new_node = malloc(sizeof(Node));
      new_node->key = str;
      new_node->data = data;
      linked_list->next = new_node;
    } else {
      linked_list->data = data;
    }
  }
  return index;
}

int main(void) {
  // create buckets
  void *bucket_array[1024] = {NULL};

  int x = add("Neo", "bing-bong", 1024, bucket_array);
  printf("%s\n", ((Node *)bucket_array[x])->data);
  add("Neo", "ching-chong", 1024, bucket_array);
  printf("%s\n", ((Node *)bucket_array[x])->data);
  add("Neo", "ding-dong", 1024, bucket_array);
  printf("%s\n", ((Node *)bucket_array[x])->data);

  return 0;
};

Fix missing headerfile

Neo Sahadeo — Mon, 12 May 2025 00:48:24 +0000

This is an updated version from the legacy journal that will hopefully help you solve the problem shown below [screenshot]

The following assumes you're using clangd as the LSP server and have already installed GTK.

A missing header file usually means that the LSP does not know the path of the file(s). This can be fixed using pkg-config to get the paths needed to allow the LSP to work correctly.

Run `pkg-config --cflags gtk[n]`

The above command will create long list of includes that you should copy. Replace n with your GTK version, for example, I have gtk4 installed so I would run pkg-config --cflags gtk4

Create a .clangd file

This will be the file the clangd LSP will use to resolve paths. Paste the code in and format it to look like below (you're paths will be different to mine). If you're using Vim here are the commands to quickly do this %s/ /\r/g and %s/\(.*\)/"\1",/g

CompileFlags:
    Add: [
        "-I/usr/include/gtk-4.0",
        "-I/usr/include/pango-1.0",
        "-I/usr/include/fribidi",
        "-I/usr/include/harfbuzz",
        "-I/usr/include/gdk-pixbuf-2.0",
        "-I/usr/include/cairo",
        "-I/usr/include/freetype2",
        "-I/usr/include/libpng16",
        "-I/usr/include/pixman-1",
        "-I/usr/include/graphene-1.0",
        "-I/usr/lib/graphene-1.0/include",
        "-mfpmath=sse",
        "-msse",
        "-msse2",
        "-I/usr/include/glib-2.0",
        "-I/usr/lib/glib-2.0/include",
        "-I/usr/include/libmount",
        "-I/usr/include/blkid",
        "-I/usr/include/sysprof-6",
        "-pthread"
    ]

Restart your editor / LSP

After creating the file your LSP should recognize the GTK header file.

Salting & Hashing🍳

Neo Sahadeo — Thu, 11 Jul 2024 13:07:32 +0000

What is salting 🧂?

Salting is the process of adding data into a value before hashing.

What is hashing #️⃣?

Hashing is the process of converting data into a fixed-length string.

fixed-length: all hashes will have the same length

⚠️Something important to highlight is that hashing is not encrypting; Hashing or encryption depends on what the ultimate goal of that obfuscation is (orginisation regulations are a factor).

Here's an example:

User 1

(~🐧): echo password | sha256sum
6b3a55e0261b0304143f805a24924d0c1c44524821305f31d9277843b8a10f4e>

User 2

(~🐧): echo password | sha256sum
6b3a55e0261b0304143f805a24924d0c1c44524821305f31d9277843b8a10f4e>

The hashed passwords are identical; and that makes sense, they're the same password passed through the same algorithm. The problem arises when two separate users have the same hashed password and a bad actor gets a hold of these password and they can draw similarities.

Hypothetical scenario of compromised data:

User 1 uses the same password for every-site (not an uncommon thing). One of the sites gets their user-data leaked (also not an uncommon thing) which happens to have User 1's raw password stored. Then another site gets leaked that has User 1 and User 2's passwords that are hashed (but not salted). It's as easy as running a grep search and comparing hashes.

Adding a random SALT: