C# Data Structures and Algorithms

Hash tables

Let's start with the first data structure, which is a hash table, also known as a hash map. It allows mapping keys to particular values, as shown in the following diagram:

One of the most important assumptions of the hash table is the possibility of very fast lookup for a Value based on the Key, which should be the O(1) operation. To achieve this goal, the Hash function is used. It takes the Key to generate an index of a bucket, where the Value can be found.

For this reason, if you need to find a value of the key, you do not need to iterate through all items in the collection, because you can just use the hash function to easily ...