-
Notifications
You must be signed in to change notification settings - Fork 149
Description
Writing this issue because I have been thinking that it would be nice if nob had a hash map implementation in a similar fashion as to how dynamic arrays are implemented.
Something that came to my mind was to do a definition of the Hash map like this:
typedef struct {
Nob_Hash_Index *indexes;
Type *items;
size_t count;
size_t capacity;
} My_Hash;Where we add the indexes field on the structure to indicate that this is a hash map.
Than add macros in the form of nob_hash_set and nob_hash_get to add a new value and get a value from the hash map.
But, here comes the problem I have wanted to discuss, the strategy to manage collisions. For what I have been thinking, I would like to implement the indexes array by chaining the colliding addresses with a linked list, and so defining the Nob_Hash_Index like this:
typedef struct index_type {
size_t value; // Place holder name
struct index_type *next_index;
} Nob_Hash_Index;I think this is a good way to manage it because we don't really need to think about changing the size of the indexes array in case the hash map is growing and potentially we could even think of the indexes array statically, and having this definition:
typedef struct {
Type *items;
size_t count;
size_t capacity;
Nob_Hash_Index indexes[MY_HASH_SIZE];
} My_Hash;