Important data structures (Part I — Hash Tables)
One of the key tools for programmers to know is what data structures exist and how to use them. I’m going to give a quick overview of some key data structures that I have definitely found useful.
Hash tables: Hash tables are look up tables that allow for fast access. In the programming world (and in general) we want things to be as efficient as possible and since hash tables only take constant time O(1) for look-up, they are a good option!
We create a table with a ‘key’ and a ‘value’ for each element in the table. The key is used for indexing purposes and the value is what you actually want to store/retrieve/delete.

Let’s go through an example:
Example:
Suppose I have a large amount of data that I want to access quickly. Normally I could use an array to store the data and simply search through it if I had a reasonable size of data. But recall, searching through all elements of an array is quite time consuming.
So, we use a hashing function to index elements where we can easily access them later on.
Say we have the elements:

And for example we have the following hash equation:

So we accordingly plug in each number into the hash equation and we get:

Working backwards from the values, we can see which keys the values should get assigned to in the table. Using the keys as indices we can fill in our table:

We can see that each element now gets its own spot in the table according to the hash function. And we know for example if someone wanted to add the value 1049 to the table, it would go at index 6.

This way we can access/add/change/delete any element.
Now the obvious question is what if we land on the same index more than once? This is what happened above when both values 400 and 567 ended up being hashed to index 3. This is called a collision.
One way to deal with collisions is called chaining. Chaining is where you simply add each element to a linked list at that index and keep growing the list each time a value ends up there.
How to choose the hash function?
Aim to reduce the number of collisions and choose a function that can allow for fast computation.
Common structure in C++: Unordered maps from STL are the hash tables of C++. Documentation can be found here: https://en.cppreference.com/w/cpp/container/unordered_map.
Common structure in Python: Dictionaries are a wonderful feature of python. They are essentially hash tables and have a key,value system for storing elements, where the key and value don’t necessarily have to be integers!
