Check out the library if you're interested: book. It's not the best but it'll do for now. It looks something like this:

template<typename K> 

const u64 hash_key(const K& key) {

  u32 hash = 2166136261u;



  hash ^= key;

  hash *= 1677719;



  return hash;

}

I don't understand it. You don't understand it. Jared over there doesn't understand. But it doesn't matter. What matters is that it works.

And once we hash a specific key, we can %ed it with the capacity of the table (and yes tables are just arrays under the hood). That should produce the index with which we can retrieve our value. However, there's a problem here. You smell like shit. But there's another problem.

With hash tables, there's quite an infamous problem. When we hash a key and retrieve the index, we can potentially have two values that take up the same spot in the array. Meaning, they will produce the same index. This is called a collision. And it happens more times than you think, especially if you have a terrible hashing function. So a bunch of old white people cuddled together in a room and found a solution to this problem. Well, actually, multiple solutions but we'll look into two of them.

The first is called an "open table" solution. In this method, we can use a linked list to store all of the values that produce the same index. Anytime we want to retrieve a value, we just get the index and if that index doesn't match the key, then we'll walk the linked list until we find our key. While this approach might seem good, it's actually not the best. It does take up a lot of memory since every node in that linked list is a required allocation. And traversing a linked list is not constant time so it kind of defeats the purpose. However, it is still very much faster than a regular linked list and those lists won't be that long anyway.

The second solution to collisions is something called a "close table". Sometimes, this method, confusingly, is called "open addressing". In this method, something called "probing" is used. Essentially, whenever we encounter a collision, we just look for the next index. If that spot is empty, we'll just place the value there. But, if it's not empty, we just look to the next index and then the next index and then the next index and so on until we find an empty slot. Of course, if we do reach the end of the table we will wrap around to the beginning.

In my opinion, the second solution is better. However, it is much more headache-inducing to implement. Trust me, I tried. And so, even though I think it's an inferior solution, I used the open table method for resolving collisions. If you think that's stupid, then... I swear I'll break up with you. Like, I'm not even joking.

HashTable in action:

// Creating a table with a capacity of '12'

ishtar::HashTable<int, ishtar::String> names(12); 



names.set(32, "Buddy Guy Jones");

names.set(83, "Abigail Jack JR.");

names.set(128, "Salem Yunich Euler");

names.set(256, "Jackson Free Darnell");

names.set(512, "Ian Long Bundy");

names.set(1024, "Randall Axel Jones");



// Retrieve the name at index `1024`

ishtar::String randall = names.get(1024);



// Now that I think about it, using ints as keys wasn't the best idea. 

// But you can imagine the key being a string, for example. I'm dumb sometimes. On occasion. 

Conclusion

So what are you supposed to take away from all this? Well, let me ask you a counter-question. Why are you... why are you dumb? Like.

No, but seriously, the reason I made this library in the first place was to show you how simple and easy all of this is. I highly encourage you to try out this on your own. You'll be a better programmer overall. Trust me, dude. Like, come on.

Data structures are a crucial part of any application. Understanding them will be of benefit to you. Are you gonna make a library that is better than C++'s STL? Obviously no. Is it gonna be more efficient or performant? Well, you never know maybe. But that's not the point. The point is that you'll learn a ton of things. You'll appreciate these libraries more. You'll even have an idea of how things work under the hood so you can use them more efficiently in the future.

Now, as for me, I plan to use this library for some time. My plan is to grow it and expand upon it. Fix some of the bugs and make it more performant. I'll see how far I can go with this library without losing faith in humanity.

Well, actually, the joke's on you. I already lost faith in humanity.

But seriously though, tell your mom to call me back because like...