Hash Table

You are an absolute star!

We have finished with the linked list data structure, but we will meet this structure again a little bit later. Now it is teatime for the Hash Tables.

We have learned lists. Knowing the element's index makes it easy to receive an element from the list. But one of the main disadvantages is that if we want to add more elements to the simple list, we need to borrow more memory.

Because of that problem, we learned about a linked list. The linked list solves this problem as elements of the linked list can be placed at different memory blocks.

But another problem occurs, unfortunately:(

If we want to find any element, we must waste O(n) time.

Hash tables will cope with this problem!!!

Hash tables are used when it is needed to look for, insert or delete elements very quickly.

A Hash table is an array that works with the hash function.

How can we set data to the hash table?

• The hash function receives data that is called key;
• From the hash function, we receive the hash value - an index that shows the position of the hash value in the hash table;
• Hash value connects our key with one index in the hash table. Super! The hash table is formed!

How can we receive data from the hash table?

For example, we want to find the dog in the hash table:

• The dog goes through the hash function;
• Hash function produces a hash value;
• And then we go to the 'row' with the hash value we received.

So, the hash table is a quick way to work with the data.

Unfortunately, nothing is ideal, so we can meet one problem while working with the hash tables - collision.