tisdag 7 juni 2016

My first hashtable, part 2

Since the implementation of my first version of my hash table, I've discovered a few things:

Key Size - The implementation was really good for small keys (e.g. uint64_t), but much worse for larger ones.

Api - The "empty key" api didn't really sit well with me. Even though it was only exposed to the user in the class declaration.

So, I began reiterating my implementations, testing and benchmarking (which is a lot of fun), and after a while I came up with a result I'm quite satisfied with. Not only is the API nicer, but the performance is better; much more uniform, and in most cases faster than my previous implementation! And at ~270 lines of code, I think it's a pretty good alternative to the more common implementations out there :)

Code: https://github.com/JCash/containers

Here are some samples from the benchmarks:




söndag 27 mars 2016

My first hash table

Recently I realized I needed a hash table where I had complete control of the memory ownership.
Previously, as a placeholder, I just used a regular std::unordered_map, but now I had come to a point where it just needed to be replaced. I wanted to be able to reload my engine, while keeping the data intact in memory (Handmade Hero style).

Since I had never written one myself, I though this might be a fun exercise/challenge.
Even though the wheel is already invented, doesn't mean you can't have fun building a new one, learn something from it, or even try to improve on it. Right?

One common way to implement a hash table is to use "chaining", which means that you use a table to do the initial lookup, and then use a linked list to resolve hash collisions. Another way is to use "open addressing", where you use a "probing sequence" to find an empty slot, in case of hash collisions.

TL;DR: The code is available on GitHub

An example of the benchmarks found at the GitHub repo