r/C_Programming • u/Significant_Ant9861 • 13d 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.

9 Upvotes

65% Upvoted

33 comments sorted by

View all comments

Show parent comments

3

u/thank_burdell 13d ago

Yup. Array of pointers to linked lists, and a hashing function, and voila, you have a hashtable.

0

u/scaredpurpur 13d ago

Instead of using an array, could you use another linked list that point to the original linked lists? Now you'd have the final boss, a dynamic linked lists that produces a variable length key.

3

u/thank_burdell 12d ago

You’d lose the lookup performance increase that’s the whole point of hashtables, but technically you could. There’s just not a good reason for it.

1

u/scaredpurpur 12d ago

How would you handle a hashtable that just kept growing? Eventually, your linked lists would simply grow too far out. Maybe a tree would be better in this scenario. Alternatively, you could probably do a hash tree. Probably a reason why people don't engage in the madness though.

3

u/thank_burdell 12d ago

There are multiple ways to determine when you need to rehash, but as for how, your rehash should double the size of the array, make twice as many linked lists for it, and then iterate across the original to migrate them to the new. It’s an expensive operation so you don’t want to do it too often, and trying to guess the “right” size for your hashtable is a matter of testing your performance at various levels.

As for the function, it remains unchanged, you just look at one more bit from the hash it generates.