[ecaradec]

One trick I learned from https://craftinginterpreters.com/hash-tables.html is that you don't need an extra linked list for each bucket... But how do you handle collisions then ?

The trick is that you make sure that your table is large enough to not have a lot of collisions, then if you have a collision instead of storing exactly in the bucket given by the hash, you store it in the next available bucket. When you look for a key, you get the hash, then the index from the hash, and you start searching at this point. If you reach an empty value, then there is no value. If you find the value then you return that. So everything is stored in a single array, no need for extra allocations and it is better for cache locality.

The same principle is used here for very minimal hash table (13 lines): https://nullprogram.com/blog/2020/10/19/

This video also talk about how to optimize hash table and look into several implementations: https://www.youtube.com/watch?v=DMQ_HcNSOAI&t=1690s&ab_chann... . It talks about techniques used by advanced hash table. There was a lot more that I didn't know.

[masklinn]

That’s not really a trick?

It’s an open addressing hash table (https://en.wikipedia.org/wiki/Open_addressing), with a linear probing collision resolution (https://en.wikipedia.org/wiki/Linear_probing).

[scrozart]

Yup. This is how they're taught in CS undergrad (as of 10 years ago, anyway).