hashMap.h File Reference

Detailed Description

A generic map for storing arbitrary key-value pairs.

Date

2024-03-10

Author

Dylan Whichard

Design Philosophy

This is a generic hash map data structure, which supports the basic put, get, and remove operations, as well as iteration. By default, keys are assumed to be nul-terminated strings, but any type can be used if alternate hash and equality functions are supplied. The hash map will automatically resize itself once it becomes about 75% full, but setting a sufficiently large initial capacity will improve efficiency overall.

Keys inserted into the map must remain valid for the duration they are in the map, as the map maintains a reference rather than copying them. This also means that modifying the key itself after it has been inserted into the map will cause it to become inaccessible, so using immutable data as pointers is also recommended. To change the key of an entry in the map, remove it and add it with the new key instead.

Basic operations against the hash map have O(1) time in the average case, with O(n) time in the worst case. Hash collisions are handled by storing multiple items within the same bucket in a linked list. Resizing is O(k), where k is the number of buckets in the hash map, and should occur once in every k put operations.

Iteration over the map is O(k) best case, O(k+n) worst case, and O(k) average case, as we do not know ahead of time which buckets or keys are in use. This could theoretically be improved to O(n) worst case if keys were also kept in a separate array, but this would be a marginal improvement with a lot of added complexity.

Caveats

It's important to note that, even though the hash map is a reasonably efficient data structure, its main use case is really for convenience. Due to the added overhead of the hashing operation and traversal of the relatively complex hash map structure, in most cases its real-world performance will be worse than a simple linear search through an array, up to a surprisingly large number of items. With that said, this is unlikely to be a real concern in almost all situations. So unless a massive number of hash map operations is actually causing performance issues, it's best to avoid premature optimization and instead just use whatever is the most convenient and results in the simplest code.

Usage

hashInit() allocates a new hash map for use with string keys.

hashPut() adds a new entry to the map or updates the value of an existing one.

hashGet() retrieves a value from the map.

hashRemove() removes an entry from the map by its key.

hashDeinit() deallocates a hash map and all its entries.

hashIterate() can be used to loop over a hash map's entries.

hashIterReset() is used to reset an iterator if iteration stopped before hashIterate() returned false.

hashIterRemove() can be used to safely remove entries during iteration.

hashPutBin(), hashGetBin(), and hashRemoveBin() are variants of the normal hash map functions which accept a void pointer in the key argument, rather than a char pointer. You must provide hash and equality functions to hashInitBin() in order to safely use keys which are not nul-terminated strings.

hashString() and strEq() are the default hash and comparison functions respectively, and will be used when the hash map is initialized with hashInit().

hashInt() and intsEq() are alternative hash and comparison functions that operate directly on a pointer address without dereferencing it. They can also be used when the key is any int or enum type that is not wider than a void* .

hashBytes(), and bytesEq() are helper functions useful when implementing custom hash and comparison functions, particularly when the key is a struct pointer, with fields or data that must be included in the hash. Default implementations can't be supplied for a struct, since their length is not known to the hash map and the user implementer may wish to exclude some fields from the comparison or traverse nested values.

Examples

Create a hash map, add and retrieve some values:

// Declare a hash map
hashMap_t map;
// Initialize it with an initial capacity of 16
hashInit(&map, 16);
 
hashPut(&map, "greeting", "Hello");
hashPut(&map, "name", "King Donut");
// Prints 'Hello! Your name is King Donut!'
printf("%s! Your name is %s!\n", (const char*)hashGet(&map, "greeting"), (const char*)hashGet(&map, "name"));
 
// Update the value associated with the key 'name'
hashPut(&map, "name", (const char*)"Swadgeman");
 
// Now prints 'Hello! Your name is Swadgeman!'
printf("%s! Your name is %s!\n", (const char*)hashGet(&map, "greeting"), (const char*)hashGet(&map, "name"));
 
hashPut(&map, "greeting", "Goodbye");
// Prints 'Goodbye, Swadgeman.'
printf("%s, %s.", (const char*)hashGet(&map, "greeting"), (const char*)hashGet(&map, "name"));
 
// Clean up the hash map
hashDeinit(&map);

Iteration

Iterate over items in the map:

hashMap_t map = {0};
hashInit(&map, 16);
 
hashPut(&map, "title", "HashMap");
hashPut(&map, "description", "A cool new data structure");
hashPut(&map, "filename", "hashMap.h");
hashPut(&map, "directory", "utils");
hashPut(&map, "somethingElse", "donut");
hashPut(&map, "tag-0", "data-structure");
hashPut(&map, "tag-1", "map");
hashPut(&map, "tag-2", "dictionary");
 
// Initialize the iterator with 0
hashIterator_t iter = {0};
while (hashIterate(&map, &iter))
{
    printf("%s: %s\n", (const char*)iter.key, (const char*)iter.value);
}
// No need to use hashIterReset() here as the loop finished normally
hashDeinit(&map);

Remove items while iterating:

while (hashIterate(&map, &iter))
{
    // Remove any items with a key starting with "tag-"
    if (!strncmp(iter.key, "tag-", 4))
    {
        printf("Removing tag %s\n", iter.value);
        if (!hashIterRemove(&map, &iter))
        {
            // The item removed was the last one! Iteration must be stopped
            break;
        }
    }
}
// Still no need to use hashIterReset(), as it will be handled
// automatically by either hashIterate() or hashIterRemove()

Breaking iteration early:

// Find and print any tag, then stop
while (hashIterate(&map, &iter))
{
    if (!strncmp(iter.key, "tag-", 4))
    {
        printf("Found a tag: %s\n", iter.key);
        break;
    }
}
 
// This time, hashIterReset() is necessary!
// We might not have reached the end of iteration, so the iterator might not have reset automatically
// If we did happen to reach the end anyway, resetting it again won't hurt anything
hashIterReset(&iter);

Non-string Keys

The hash map also supports using structs or even primitives as key types, instead of strings. This can be done using hashInitBin() to supply custom hashing and comparison functions appropriate for the type of key being used.

Enum and Integer keys

This example shows how to use a hash map where the keys are enum values. This method will work with any numeric type, as long as sizeof(type) is less than or equal to sizeof(void*) – that is, as long as its value fits inside a pointer. In practice this means an int32_t can be used as a key in a hash map in this way, but an int64_t cannot.

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include "swadge2024.h"
#include "hashMap.h"
 
// Just a simple struct to hold a WSG and its rotation for the values
typedef struct
{
    int16_t rot;
    wsg_t wsg;
} wsgRot_t;
 
hashmap_t map = {0};
wsgRot_t* wsgs = NULL;
 
void setupButtonIconMap(void)
{
    hashInitBin(&map, 16, hashInt, intEq);
 
    wsgs = calloc(8, sizeof(wsgRot_t));
    wsgRot_t* wsg = wsgs;
 
    // Load up a bunch of WSGs
    loadWsg("button_up.wsg", &wsg->wsg, false);
    hashPutBin(&map, (const void*)PB_UP, (void*)wsg++);
 
    loadWsg("button_up.wsg", &wsg->wsg, false);
    wsg->rot = 180;
    hashPutBin(&map, (const void*)PB_DOWN, (void*)wsg++);
 
    loadWsg("button_up.wsg", &wsg->wsg, false);
    wsg->rot = 90;
    hashPutBin(&map, (const void*)PB_LEFT, (void*)wsg++);
 
    loadWsg("button_up.wsg", &wsg->wsg, false);
    wsg->rot = 270;
    hashPutBin(&map, (const void*)PB_RIGHT, (void*)wsg++);
 
    loadWsg("button_a.wsg", &wsg->wsg, false);
    hashPutBin(&map, (const void*)PB_A, (void*)wsg++);
 
    loadWsg("button_b.wsg", &wsg->wsg, false);
    hashPutBin(&map, (const void*)PB_B, (void*)wsg++);
 
    loadWsg("button_menu.wsg", &wsg->wsg, false);
    hashPutBin(&map, (const void*)PB_MENU, (void*)wsg++);
 
    loadWsg("button_pause.wsg", &wsg->wsg, false);
    hashPutBin(&map, (const void*)PB_PAUSE, (void*)wsg++);
}
 
void runButtonIconMap(void)
{
    // Use the WSGs
    buttonEvt_t evt = {0};
    while (checkButtonQueueWrapper(&evt))
    {
        if (evt.down)
        {
            wsgRot_t* draw = (wsgRot_t*)hashGetBin(&map, (const void*)evt.button);
            drawWsg(&draw->wsg, (TFT_WIDTH - draw->w) / 2, (TFT_HEIGHT - draw->h) / 2, false, false, draw->rot);
        }
    }
}
 
void cleanupButtonIconMap(void)
{
    // Clean up the WSGs using the hash map
    hashIterator_t iter = {0};
    while (hashIterate(&map, &iter))
    {
        wsgRot_t* value = (wsgRot_t*)iter.value;
        freeWsg(&value->wsg);
        // Unset the pixels so the arrow icon isn't freed twice
        value->wsg.px = NULL;
    }
 
    // Clean up the hash map and WSG struct
    hashDeinit(&map);
 
    // Clean up the values
    free(wsgs);
}

Struct keys

This example shows how to use an entire structure as a key for the hash map, using the hashBytes() and bytesEq() helper functions.

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include "swadge2024.h"
#include "hashMap.h"
 
// A struct to use for the key
typedef struct
{
    int32_t x, y;
} keyStruct_t;
 
uint32_t hashStruct(const void* data)
{
    // Helper function provided with hash map
    return hashBytes((const uint8_t*)data, sizeof(keyStruct_t));
}
 
bool structEq(const void* a, const void* b)
{
    // Another hash map helper function
    return bytesEq((const uint8_t*)a, sizeof(keyStruct_t), (const uint8_t*)b, sizeof(keyStruct_t));
}
 
hashMap_t map = {0};
keyStruct_t keys[5] = {0};
 
void setupStructKeyExample(void)
{
    hashInitBin(&map, 10, hashStruct, structEq);
 
    keys[0].x = 10;
    keys[0].y = 16;
 
    keys[1].x = 5;
    keys[1].y = 5;
 
    keys[2].x = 7;
    keys[2].y = 12;
 
    keys[3].x = 1;
    keys[3].y = 3;
 
    keys[4].x = 16;
    keys[4].y = 4;
 
    hashPutBin(&map, (const void*)&keys[0], (void*)"Star");
    hashPutBin(&map, (const void*)&keys[1], (void*)"Square");
    hashPutBin(&map, (const void*)&keys[2], (void*)"Circle");
    hashPutBin(&map, (const void*)&keys[3], (void*)"Diamond");
    hashPutBin(&map, (const void*)&keys[4], (void*)"Triangle");
}
 
void runStructKeyExample(void)
{
    static int x = 0;
    static int y = 0;
 
    buttonEvt_t evt;
    while (checkButtonQueueWrapper(&evt))
    {
        if (evt.down)
        {
            if (evt.button == PB_UP)
            {
                y++;
            }
            else if (evt.button == PB_DOWN)
            {
                y--;
            }
            else if (evt.button == PB_LEFT)
            {
                x--;
            }
            else if (evt.button == PB_RIGHT)
            {
                x++;
            }
            else if (evt.button == PB_A)
            {
                keyStruct_t key;
                key.x = x;
                key.y = y;
                const char* found = (const char*)hashGetBin(&map, (const void*)&key);
                if (found)
                {
                    printf("Found a %s at %d, %d!\n", found, x, y);
                }
                else
                {
                    printf("Didn't find anything at %d, %d :(\n", x, y);
                }
            }
        }
    }
}
 
void cleanupStructKeyExample()
{
    hashDeinit(&map);
}

Go to the source code of this file.

Data Structures
struct	hashIterator_t
	Struct used for iterating through a hash map efficiently. More...
struct	hashMap_t
	A hash map for storing key-value pairs. More...

Typedefs
typedef uint32_t(*	hashFunction_t) (const void *data)
	A function that takes a pointer to key data and returns its hash value.
typedef bool(*	eqFunction_t) (const void *a, const void *b)
	A function that takes two pointers to keys and returns true if the values they point to are equal.
typedef struct hashBucket	hashBucket_t
typedef struct hashIterState	hashIterState_t

Functions
uint32_t	hashString (const void *str)
	Convert a NULL-terminated string to a hash value.
bool	strEq (const void *a, const void *b)
	Compare two NUL-terminated strings.
uint32_t	hashBytes (const uint8_t *bytes, size_t length)
	Convert an arbitrary byte sequence to a hash value.
bool	bytesEq (const uint8_t *a, size_t aLength, const uint8_t *b, size_t bLength)
	Compare two byte arrays.
uint32_t	hashInt (const void *intKey)
	Convert a pointer address or integral value to a hash value.
bool	intsEq (const void *keyA, const void *keyB)
	Compare two void pointers based on their address, or two integer types cast to a void pointer.
void	hashPut (hashMap_t *map, const char *key, void *value)
	Create or update a key-value pair in the hash map with a string key.
void *	hashGet (hashMap_t *map, const char *key)
	Return the value in the hash map associated with the given string key.
void *	hashRemove (hashMap_t *map, const char *key)
	Remove the value with a given string key from the hash map.
void	hashPutBin (hashMap_t *map, const void *key, void *value)
	Create or update a key-value pair in the hash map with a non-string key.
void *	hashGetBin (hashMap_t *map, const void *key)
	Return the value in the hash map associated with the given key.
void *	hashRemoveBin (hashMap_t *map, const void *key)
	Remove the value with a given non-string key from the hash map.
void	hashInit (hashMap_t *map, int initialSize)
	Initialize a hash map for string keys.
void	hashInitBin (hashMap_t *map, int initialSize, hashFunction_t hashFunc, eqFunction_t eqFunc)
	Initialize a hash map for non-string keys, using the given functions for hashing and comparison.
void	hashDeinit (hashMap_t *map)
	Deinitialize and free all memory associated with the given hash map.
bool	hashIterate (const hashMap_t *map, hashIterator_t *iterator)
	Advance the given iterator to the next item, or return false if there is no next item.
bool	hashIterRemove (hashMap_t *map, hashIterator_t *iter)
	Remove the last item returned by the iterator from the hash map.
void	hashIterReset (hashIterator_t *iterator)
	Reset the given iterator struct, freeing any memory associated with it.
void	hashReport (const hashMap_t *map)
	Prints out a detailed report on the hash map state.

---

Data Structure Documentation

hashIterator_t

struct hashIterator_t

Data Fields
const void *	key	The key of the current key-value pair.
void *	value	The value of the current key-value pair.
hashIterState_t *	_state

hashMap_t

struct hashMap_t

Data Fields
int	size	The total number of allocated buckets in the hash map.
int	count	The actual number of items stored in the hash map.
hashBucket_t *	values	The array of bucket values.
hashFunction_t	hashFunc	The key hash function to use, or NULL to use hashString()
eqFunction_t	eqFunc	The key equality function to use, or NULL to use strEq()

Typedef Documentation

hashFunction_t

typedef uint32_t(* hashFunction_t) (const void *data)

A function that takes a pointer to key data and returns its hash value.

Parameters

data	The data to hash

Returns

An int32_t representing the hash of this data

eqFunction_t

typedef bool(* eqFunction_t) (const void *a, const void *b)

A function that takes two pointers to keys and returns true if the values they point to are equal.

hashBucket_t

typedef struct hashBucket hashBucket_t

hashIterState_t

typedef struct hashIterState hashIterState_t

Function Documentation

hashString()

uint32_t hashString

(

const void *

str

)

Convert a NULL-terminated string to a hash value.

Uses the 'djb2' algorithm, described at http://www.cse.yorku.ca/~oz/hash.html

Parameters

str	The string to hash

Returns

uint32_t The hash value

strEq()

bool strEq	(	const void *	a,
		const void *	b )

Compare two NUL-terminated strings.

Parameters

a	The first string to compare
b	The second string to compare

Returns

true when the two strings are equal or the same pointer

false when the two strings differ

hashBytes()

uint32_t hashBytes	(	const uint8_t *	bytes,
		size_t	length )

Convert an arbitrary byte sequence to a hash value.

Uses the 'djb2' algorithm, described at http://www.cse.yorku.ca/~oz/hash.html

Parameters

bytes	A pointer to a byte array to hash
length	The length of the byte array

Returns

uint32_t The hash value

bytesEq()

bool bytesEq	(	const uint8_t *	a,
		size_t	aLength,
		const uint8_t *	b,
		size_t	bLength )

Compare two byte arrays.

Parameters

a	A pointer to the first byte array
aLength	The length of the first byte array
b	A pointer to the second byte array
bLength	The length of the second byte array

Returns

true when the byte arrays are equal or the same pointer

false when the byte arrays differ

hashInt()

uint32_t hashInt

(

const void *

intKey

)

Convert a pointer address or integral value to a hash value.

The pointer is not dereferenced.

Parameters

intKey

A void pointer whose address will be hashed, or any integral type cast to a void pointer

Returns

uint32_t The hash value

intsEq()

bool intsEq	(	const void *	keyA,
		const void *	keyB )

Compare two void pointers based on their address, or two integer types cast to a void pointer.

The pointers are not dereferenced.

Parameters

keyA	The first pointer value
keyB	The second pointer value

Returns

true If both pointers are the same value

false If the pointers are differ

hashPut()

void hashPut	(	hashMap_t *	map,
		const char *	key,
		void *	value )

Create or update a key-value pair in the hash map with a string key.

Warning

A reference to the key will be stored in the map until the entry is removed

Parameters

map	The hash map to update
key	The string key to associate the value with
value	The value to add to the map

hashGet()

void * hashGet	(	hashMap_t *	map,
		const char *	key )

Return the value in the hash map associated with the given string key.

Parameters

map	The hash map to search
key	The string key to retrieve the value for

Returns

void* A pointer to the mapped value, or NULL if it was not found

hashRemove()

void * hashRemove	(	hashMap_t *	map,
		const char *	key )

Remove the value with a given string key from the hash map.

Parameters

map	The hash map to remove from
key	The string key to remove the value for

Returns

void* The item that was removed, or NULL if no item was found for the given key

hashPutBin()

void hashPutBin	(	hashMap_t *	map,
		const void *	key,
		void *	value )

Create or update a key-value pair in the hash map with a non-string key.

Parameters

map	The hash map to update
key	The key to associate the value with
value	The value to add to the map

hashGetBin()

void * hashGetBin	(	hashMap_t *	map,
		const void *	key )

Return the value in the hash map associated with the given key.

Parameters

map	The hash map to search
key	The key to retrieve the value for

Returns

void* A pointer to the mapped value, or NULL if it was not found

hashRemoveBin()

void * hashRemoveBin	(	hashMap_t *	map,
		const void *	key )

Remove the value with a given non-string key from the hash map.

Parameters

map	The hash map to remove from
key	The non-string key to remove the value for

Returns

void* The item that was removed, or NULL if no item was found for the given key

hashInit()

void hashInit	(	hashMap_t *	map,
		int	initialSize )

Initialize a hash map for string keys.

Parameters

map	A pointer to a hashMap_t struct to be initialized
initialSize	The initial size of the hash map

hashInitBin()

void hashInitBin	(	hashMap_t *	map,
		int	initialSize,
		hashFunction_t	hashFunc,
		eqFunction_t	eqFunc )

Initialize a hash map for non-string keys, using the given functions for hashing and comparison.

Parameters

map	A pointer to a hashMap_t struct to be initialized
initialSize	The initial size of the hash map
hashFunc	The hash function to use for the key datatype
eqFunc	The comparison function to use for the key datatype

hashDeinit()

void hashDeinit

(

hashMap_t *

map

)

Deinitialize and free all memory associated with the given hash map.

Parameters

map	The map to deinitialize

hashIterate()

bool hashIterate	(	const hashMap_t *	map,
		hashIterator_t *	iterator )

Advance the given iterator to the next item, or return false if there is no next item.

The iterator should point to a zero-initialized struct at the start of iteration. Once iteration completes and this function returns false, iterator will be reset. If iteration is stopped before this function returns false, the iterator must be reset with hashIterReset() to prevent memory leaks.

Items in the hash map are not returned in any particular order.

It is possible to remove items during iteration, but this must be done with hashIterRemove(). Using hashRemove() or hashRemoveBin() during iteration is not allowed and will cause undefined behavior.

Adding or udpating items during iteration is permitted, with the caveat that a new item inserted during iteration may or may not later be returned by the iterator.

Parameters

[in]	map	The map to iterate over
[in,out]	iterator	A pointer to a hashIterator_t struct

Returns

true if the iterator returned an item

false if iteration is complete and no item was returned

hashIterRemove()

bool hashIterRemove	(	hashMap_t *	map,
		hashIterator_t *	iter )

Remove the last item returned by the iterator from the hash map.

This function does not need to search and so it always runs in constant time.

If you want to remove an item from the hash map while iterating over it, this function is the only safe way to do it.

Warning

If this function returns false, iteration is complete.

Parameters

map	The hash map to remove the item from
iter	The iterator whose current item to remove from the hash map

Returns

true if there are still items remaining in the iterator

false if there are no more items remaining in the iterator

hashIterReset()

void hashIterReset

(

hashIterator_t *

iterator

)

Reset the given iterator struct, freeing any memory associated with it.

Parameters

iterator

A pointer to the iterator struct to be reset

hashReport()

void hashReport

(

const hashMap_t *

map

)

Prints out a detailed report on the hash map state.

This can be useful when testing to determine the effectiveness of a hash function.

Parameters

map	The hash map to print the state of