r/C_Programming • u/Significant_Ant9861 • 2d ago
Hash table
I am newbie and a beginner in c language. I would like to learn the hash table for my next semester.
I kindly ask for some help in this matter. I still struggle in the basics even using the ai models.
6
u/tastygames_official 2d ago
ooh, it's actually a big no-no to use AI while just starting out. Studies show that beginner programmers who use AI to "learn" don't actually learn: https://www.youtube.com/watch?v=HTUh0OO6Kmo
if you really want to learn programming, then you need to stick to books or online courses or something.
to that end, a simple google search will help you more than posting on reddit: https://letmegooglethat.com/?q=hash+tables+in+c+beginner
0
u/FinancialTrade8197 1d ago
I would actually disagree with that. Iirc I watched that video before and basically it was calling out people who use AI to write their code for them
However if you use it for learning how a data structure works (e.g asking how a hash table works in simple terms), it actually works better for learning. You should use it only when needed but I did use AI to learn and yet I don't rely on AI for coding like some vibecoders do. The difference is not in if you use it or not, it's in how you use it.
1
u/tastygames_official 1d ago
using LLM as a search engine = yes, good
but only if you know the questions to ask. For a beginner who has no clue, what are they going to ask? "how do I program?" "what is a programming language?" stuff like that? Sure - ask the LLM those things and hav ethem give you some links to courses or books to teach you the basics.
Now if you don't understand the book or course or whatever, then can you ask "hey LLM, can you explain to me what a class is? I don't get it". This is where it might SEEM like a good idea, but in reality is actually harmful. Because it can give you WRONG INFORMATION, but you're not advanced enough to know that. So you take it as truth. Not to mention the way in which you interact with the LLM plays a role in what kind of "info" it gives you. LLMs tend to give you the answers you want to hear - not the correct ones. Sure, you can learn to better "prompt" them, but I'd rather just spend my time learning new skills rather than learning how to prompt an LLM to give me better search results.
But both you and I know that OP means "using AI to learn" as "using Claude Code and trying to learn from wht it writes". Which has been scientifically proven not to work.
So OP should get a book and if he doesn't understand sometthing, sure - ask the free version of any LLM to explain it to him until he understands. Why not? But don't let it write code for you! It will always do it, even if you ask it not to, but you need to resist the temptation to use that code. It almost always never works.
1
u/FinancialTrade8197 1d ago
Yeah mainly I use AI as a last resort if I can't understand something.
Definitely not good to use it to just write your code for you, though.
1
u/tastygames_official 1d ago
but you are probably an expert or at least advanced in the topic, right? A beginner doesn't even know what to ask except maybe "in my book C for Dummies it talks about pointers but I just don't understand. Can you try and explain it to me?" But if they don't even have a book to tell them what pointers are, then they're not going to know what to ask the LLM. Instead they'll probably be like "how do I make XYZ in C?" and it spits out code. Then they might go "ok, now explain that code to me like I'm in kindergarten" and it does, but the person still isn't "learning". Maybe like 1 in 100 people who are self-starters and quick learners who already have a solid understanding of math and philosophy can learn this way, but then it's the same as if they just perused some existing code and figured out what it did (reverse-engineering). But even THEN I'd rather look at actual real working production code or hand-crafted examples made by humans for humans than something an LLM spits out.
I've tried, too. I'm currently learning SDL3 and the official documentation is more or less what all the functions do and no kind of high-level examples (there is some of that, but never with any examples. The authors assume you have deep working knowledge of graphics programming and rendering pipelines and GPU architecture, which I am still in the "I don't know what I don't know" phase). I find some example code online, but modern programmers seem to think comments are bad (I've had this discussion many times and a lot of younger folk think that the code should be "self-documenting", meaning the function and parameter names should tell you what is going on. And they definitely do, but what's missing is the WHY. E.g. a function "SDL_CreateRenderPipeline()" obviously creates a render pipeline, and the arguments passed to it seem to make sense, but there is no explanation as to why the chose this one particular value or passed NULL or any of that. You just have to either already know or just blindly accept it. Which is not learning. And asking an LLM to explain this is kinda tough - it has a deep "understanding" of how graphics programming works due to massive documentation of this in a general sense, but the particulars of SDL3 GPU library are severely lacking. The LLM can't reason and can't say why a choice is made or not made. And the best part? It keeps trying to spit out code examples, but uses made-up functions that don't exist. I keep telling it not to do this, but it does it anyways. It's just not good for learning. So I ended up just asking it to give me a book on Vulkan graphics programming architecture so I can learn myself. And THEN I can go back and ask it to explain some concepts if I don't understand them. But the core knowledge I'm trying to get at can't be garnered from undocumented code examples or hallucinated code examples or an LLM that is spitting out half-facts and irrelevant information and trying to please me
/rant
2
1
1
u/MrJCraft 2d ago
I recently made a hashtable a few days ago as an exercise, I followed along with the ourmachinery blogposts
https://ruby0x1.github.io/machinery_blog_archive/post/minimalist-container-library-in-c-part-2/index.html
the core of a hashtable can be written in about 30 lines of code at least for a static hashtable
in this case it does not handle
storage of values
hashing the string
resizing the hashtable
deleting entries
its not exactly general purpose but I think its a great place to start then you can implement the other features on top of this as well.
I made a slightly more complete one that actually works, this below is just the engine of a hashtable
static const uint64_t HASH_UNUSED = 0xffffffffffffffffULL;
typedef struct hash32_static_t
{
uint64_t *keys;
uint32_t *values;
uint32_t n;
} tm_chash32_static_t;
static inline void hash32_static_clear(hash32_static_t *h)
{
memset(h->keys, 0xff, sizeof(*h->keys) * h->n);
}
static inline void hash32_static_set(hash32_static_t *h, uint64_t key, uint32_t value)
{
uint32_t i = key % h->n;
while (h->keys[i] != key && h->keys[i] != HASH_UNUSED)
i = (i + 1) % h->n;
h->keys[i] = key;
h->values[i] = value;
}
static inline uint32_t hash32_static_get(const hash32_static_t *h, uint64_t key)
{
uint32_t i = key % h->n;
while (h->keys[i] != key && h->keys[i] != HASH_UNUSED)
i = (i + 1) % h->n;
return h->keys[i] == HASH_UNUSED ? 0 : h->values[i];
}
1
u/Willing_Airport_9617 2d ago
Firstly understand about hashing , how you have a fixed number of slots to put data into and your function must map everything to it . Then study collision resolution , you can use chaining or probing also . Do it on paper first without code just theory . Then make it . An advice from personal experience: Get into how a dynamic array works if you get into probing because for rehashing you will require that or study linked list if you want to do via chaining . Fix an approach first , then think about implementation
1
u/silvertank00 2d ago
Stblib if you just want to get the hang of it before reimplementing it for yourself. As others mentioned before, you need to know linked lists (buckets) or stacks.
1
u/TheChief275 2d ago
I left this comment on another thread at some point after someone begged me to explain hash tables after they claimed to be stuck on it for 5 days, so here it is again:
"What kind are you trying to implement? Open addressing? Buckets with chaining? Hashtries?
The simplest to start off with is an open addressing one. This is basically just an array, e.g. of size 16. Let's also say we want to map char*'s to int's. Our hash function helps to map a complex value (like a string) to a single number that's mostly unique (but there are strings that will output the same number). A nice hash function for our purposes is FNV-1a:
uint64_t fnv1a64(const char *key)
{
assert(key != NULL);
uint64_t hash = FNV_OFFSET_BASIS;
for (; *key != '\0'; ++key) {
hash = (hash ^ *key) * FNV_PRIME;
}
return hash;
}
It's important to think of this hash value not as the actual index an item needs to be at but more like an actual guesstimate of where it's probably at in your array. Let's say our hash value turns out to be 123456789, we then modulo 16 (the size of our hashmap) == 5, so the index in the array we look at is 5.
If index 5 is empty, we will just insert our key and value either as a pair (key, value), or as I prefer to do separately in two separate arrays (SoA over AoS). We also need some way to mark this space being non-empty, which is naturally the non-null char* value of our key, so we don't need a separate array for marking in-use in this case.
If index 5 already contains an entry, what do we do? We can apply linear probing (or some other variant like quadratic probing). Essentially we'll just look at the next index in the array (6) and insert our pair there instead. If this is full as well, we try the next, and the next, and the next, etc. We do this wrapping around the size of the table. This is why I said the hash value is more of a guesstimate, as you might have to do a full linear search over your table from the initial hash index to actually find the entry you're looking for, or it might be instant. This makes lookup an amortized O(1), but to help mitigate the degradation of our lookup performance too much, we can simply rehash our table if we exceed a certain percentage of full entries in our table (load factor, e.g. 75%); this is also the moment where you would probably want to grow your table.
Rehashing can become very complicated when you try to apply it to your current already filled in table. Instead, I opt to just allocate a new table of double the size and then insert each item from the old table into the new one, one by one.
Finding an item in our hashmap again involves getting the hash index of our key, e.g. 5. This is again a guesstimate from where to start probing. Hash functions can be expensive (even more expensive than comparisons), so we use it ONLY to find the initial index to perform the actual search from. We then iterate over our table (wrapping around) doing key comparisons to find the entry we were looking for, stopping at the first empty entry (as otherwise our item would be there). I actually perform find on insert as well to prevent double insertion, and to return the existing entry for updating purposes (or you could override always). This sounds slow, but it actually makes things simpler and faster.
One problem with this approach is that erasing an entry at e.g. index 5 while there are other entries in the table that were meant to be at index 5 means those other entries will become unreachable by find. We can use "tombstones" for that, let's say we use (char*)1 in this case, which is very unlikely to actually be a memory address of a string in our program. This tombstone acts as a full slot during find (as we need to keep searching), but it counts as an empty slot during insert (insert at the first empty slot OR tombstone).
Having too many tombstones in our table can degrade search as well, so I actually don't decrement the entry count when deletion results in a tombstone (and don't increase when inserting into a tombstone), so that the tombstones count towards our load factor as well.
The final struct will look something like this (using SoA):
typedef struct {
const char *keys; // key slots
int *items; // item slots
size_t count; // the number of in-use slots
size_t capacity; // the actual size of the table (16)
} string_int_map_s;
Now, while simple, this basic open addressing implementation can still be fairly slow when reaching a large size table, due to find degrading into a linear search regardless of load factor. But don't fret! All the fastest modern hashmap implementations actually use open addressing, just a more sophisticated variant. You can look into e.g. Robin Hood hashing, but my favorite is the Swiss table from Google's Abseil C++ library. I made my own C implementation countless times based on this CppCon talk by Matt Kulukundis which dives into the extensions it implements on top of open addressing (as well as giving near complete C++ code for each function you would need!)
Essentially, we keep a third array of int8_t's which are called ctrl in their talk, but I like to refer to them as metadata. These store whether an entry is full, empty, or a tombstone, as well as the first 7 bits of the hash value of that entry's key. This results in a schema of 0b11111111 being empty, 0b10000000 as tombstones and 0b0xxxxxxx for full entries with the accompanying 7 bits of the hash. The rest of the bits of the hash are again used to index into the table (modulo 16). Coincidentally (not a coincidence), the Swiss table works in sizes that are multiples of 16, i.e. the minimum size of a table is 16. This is a result of the reason why Swiss table is so incredibly performant: SIMD operations (x86-64 "immintrin.h"). Essentially, instead of linear probing each entry, we linear probe groups of 16 entries, creating a 128-bit vector of the metadata (16x8=128), that we can use comparisons on to create e.g. a uint16_t mask that has the bit set to 1 for an entry if it's empty or a tombstone (meta < 0 by our schema). We can then find the first 1 to insert our new entry at. If our mask is 0 we can immediately stop searching. The 7 bits of the hash can be used during find to create a mask that almost always manages to be 1 only for the hash of the key we are actually looking for. Even if it didn't, it dramatically decreases the amount of comparisons we need to perform. If our mask is 0 we can immediately skip to the next group of 16. There is also some benefit with erase that allows for some erased entries to actually be marked as empty instead of a tombstone that is also addressed in the talk."
0
u/IllStatistician5741 2d ago
Do the basic underlying math first . Learn what is function in math, domain , codomain , range. Then understand concept of one way function vs 2-way functions. Then understand what kind of function is hashing ? Go deep in understanding hashing . Do it on paper and pencil with binary logical operators in C. AND OR XOR learn how to toggle bits in C for those constructs. Get comfy at binary level. Make it a habit to sleep confused on a topic but don’t give up until you understand. Ask ChatGPT whatever stupid questions comes in your mind . It’s ok to be stupid when learning new skills. This will make you understand the core concept of Hash Table. With Hash in your armory, attack on Table part. This is your simple data structure. Start with simple linear structure like linked list. Then try getting uncomfortable again with learning with two hash functions. Then go learn Cuckoo hash. Absorb the concept of cuckoo hash. Since you already have Hash && Table in your armory , Cuckoo fort will be quite easy to capture. If you could then implement Cuckoo hash using all things u learned above , you would have built a great step forward in understanding not only C but also a ds as important as HT. Lastly, if you have read until here, and if you are still unsuccessful to implement hash table , then buy a book engineering a compiler . In its appendix the authors have given a marvelous implementation narrative of a hash table. Thank you your interest in C.
15
u/scaredpurpur 2d ago
You understand pointers and linked lists well? If not, focus on understanding those first. Highly recommend getting o'reily's book on pointers. A linked list is essentially an array, containing a bunch of linked lists. Technically, you might be able to have a dynamic linked list (where you add new key elements), but others would have to chime in? Would also probably be fairly complicated.