A better hash table (in C)

---
A better hash table (in C) // I've been meaning to revisit hash tables for a few years. Well, today's the day, we look at making our original hash table (circa 2020) into a general one that we can store just about anything in.

Related Videos:

***

Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.

About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.

More about me and what I do:

To Support the Channel:
+ like, subscribe, spread the word

[Aaron-tlzy]

i like the way you insert the new entry at the top on the bucket instead of walking to the end

[ahmadhadwan]

Very interesting video dr. Jacob, I'm glad you decided to expand on the last video.

[Nohope__]

I'm going to have to watch this 10 times.
(TYSM for the amazing material < 3)

[CodePagesNet]

Thank you for the helpful video and C videos in general. I encourage and promote the understanding that C has advantages over OO, even though people may not understand that yet (OO is merely a code format, and an inflexible one at that).

[SimGunther]

strager had a whole video on hash tables and it turns out that a better hash function based on the understanding of the keys going into the table equals a MUCH faster hash table! 🎉

[adambishop]

wow thank you for strcspn, i've been looping through my character arrays for a long time to try and format them into null-terminated strings without any return or newlines. Sweet function

[surters]

If you want to make a generic hash table, you need a lot of helper functions that knows the type that you would need to pass along, that gives a lot of extra parameter. Or you could just pass along a point to a struct with all those extra functions, each of them function pointers for that type.
Some of the extra pointers could be print_obj, destroy_obj, initialize_obj, copy_obj, assign_obj etc.

[sanderbos]

What I really enjoyed programming and found incredibly useful during my 1.5 years of C assignments was to write my own vector implementation. A basic one is only about 50 lines of code. Because my uni also requires us to free() *all* allocated memory manually, I was then able to write void *my_malloc(size_t count, size_t size, char *description): a malloc() wrapper that stores the new address in one of those vectors. I could then call print_allocations() and free_allocations() at the end of my main()! Very nice during debugging.

[sortof]

I thought you stopped syaing without further ado. hahah. very good video. The reason I am good at c is because I have all your videos I can reference. :D

[mr.erikchun]

Thank you Jacob for making these videos.

[tiramihai]

A 41 minute Jacob Sorber video? I'm in for a ride

[TheSulross]

Just had to implement an open addressing hash table using linear probing and and double hading to reduce clustering - and I validated that, yes, double hasing does reduce clustering and the second has function can be very cheap and practically no cost.

In my case the has table is allicated up front to some size and does not have to be increased in size over operational life time.

Only keys are stored in the has table so a lookup returns an index. So the data resolved to is kept in a separate array that is of the same max entries size as the hash table itself. So the very same hash table can be used to lookup different data structure values depending on context - something that is the case in my domain.

[zxuiji]

10:25, you already typedef'd it, you don't need another typedef, rather that's just asking for compile time errors

[k_gold]

Please make a video about terminal (termios.h) and different terminal modes etc

[svenvandevelde]

Just know that malloc and calloc are implemented using a heap structure, which is much more complex than a hash table. Why not creating this case study without malloc and calloc. Through static memory allocation. The usage of malloc and calloc slow down the logic dramatically. Also, if your hash table size and the structure size can be binary calculated through bit shifts, the key calculation can be made using a rotating random binary calculation. Which will result in blazingly fast key calculation.

[Aaron-tlzy]

at 26:11 I believe you need to free(tmp->key) too

[austinraney]

Is the calloc call at 13:16 not incorrect? I thought it was number of elements then size of t. Right, it still will allocate the same amount of memory, I just would have expected that you would need to cast to make the compiler happy. What am I missing?

[FelixNielsen]

I have a question may be relevant or entirely unrelated. I'm not actually sure.
In short, I have a problem, the solution to which could well be a hash table. My keys are known to be unique and equal length, that is to say in terms of bytes no more than a few, or not strings, but rather integers, if you so desire.
The question the becomes, is there a special category of hash functions (or other method), which can convert these keys into values in a given range, naturally ranging from 0-(n-1) for n items?

Mind you I can think of other solutions for doing what I need to do, which is basically a runtime defined and/or modified switch case like functionality, but none I can think of are entirely well suited.


Thanks for your efforts.

[aniritri]

Have you checked Zig yet ? Seems like a nice language to overview and compare to C.

[Ido-Levy]

Hey, thank you for putting out these videos! I'm learning a lot from you :) Why aren't you checking for memory allocation failures?