Book Image

C# Data Structures and Algorithms

By : Marcin Jamro
Book Image

C# Data Structures and Algorithms

By: Marcin Jamro

Overview of this book

Data structures allow organizing data efficiently. They are critical to various problems and their suitable implementation can provide a complete solution that acts like reusable code. In this book, you will learn how to use various data structures while developing in the C# language as well as how to implement some of the most common algorithms used with such data structures. At the beginning, you will get to know arrays, lists, dictionaries, and sets together with real-world examples of your application. Then, you will learn how to create and use stacks and queues. In the following part of the book, the more complex data structures will be introduced, namely trees and graphs, together with some algorithms for searching the shortest path in a graph. We will also discuss how to organize the code in a manageable, consistent, and extendable way. By the end of the book,you will learn how to build components that are easy to understand, debug, and use in different applications.
Table of Contents (14 chapters)

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 locate a proper bucket and get the value. Due to the great performance of the hash table, such a data structure is frequently used in many real-world applications, such as for associative arrays, database indices, or cache systems.

As you can see, the role of the hash function is critical and ideally it should generate a unique result for all keys. However...