Fundamentals of Computer Programming with C# HTML version

Chapter 18. Dictionaries,
Hash-Tables and Sets
In This Chapter
In this chapter we will analyze more complex data structures like
dictionaries and sets, and their implementations with hash-tables and
balanced trees. We will explain in more details what hashing and hash-
tables mean and why they are such an important part of programming. We
will discuss the concept of "collisions" and how they might happen when
implementing hash-tables. Also we will offer you different types of approaches
for solving this type of issues. We will look at the abstract data structure set
and explain how it can be implemented with the ADTs dictionary and
balanced search tree. Also we will provide you with examples that illustrate
the behavior of these data structures with real world examples.
Dictionary Data Structure
In the last few chapters we got familiar with some classic and very important
data structures – arrays, lists, trees and graphs. In this chapter we will get
familiar with the so called "dictionaries", which are extremely useful and
widely used in the programming.
The dictionaries are also known as associative arrays or maps. In this book
we are going to use the terminology "dictionary". Every element in the
dictionary has a key and an associated value for this key. Both the key and
the value represent a pair. The analogy with the real world dictionary comes
from the fact, that in every dictionary, for every for word (key), we also have
a description related to this word (value).
As well as the data (values), that the dictionary holds, there
is also a key that is used for searching and finding the
required values. The elements of the dictionary are
represented by pairs (key, value), where the key is used for
Dictionary Data Structure – Example
We are going to illustrate what exactly the data structure dictionary means
using an everyday, real world example.