ecaradec
Joined 17 years ago
Joined 17 years ago
I absolutly recommend it. There is also a comics that tell his grand father, his father story and himself that tells a lot of what a war is and also tells a little bit of the making of PoP.
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.
We need energy, but people as dismissing every source of energy because they are looking at each source one at a time. We should have taught people years ago that there is no perfect choice.