Overview of this book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++. This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book. By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.
Free Chapter
1. Lists, Stacks, and Queues
2. Trees, Heaps, and Graphs
3. Hash Tables and Bloom Filters
4. Divide and Conquer
5. Greedy Algorithms
6. Graph Algorithms I
7. Graph Algorithms II
8. Dynamic Programming I
9. Dynamic Programming II

Hash Tables

Let's look at the very basic problem of searching in a dictionary. There are about 170,000 words in the Oxford English Dictionary. As we mentioned in the Introduction, a linear search will take O(n) time, where n is the number of words. A better way to store the data is to store it in a height-balanced tree that has similar properties to a BST. This makes it much faster than linear search as it has a time complexity of only O(log n). But for applications that require tons of such queries, this is still not a good enough improvement. Think about the time it will take for data containing millions or billions of records, such as neuroscientific data or genetic data. It would take days to find something in the data. For these situations, we need something much faster, such as a hash table.

One of the integral parts of hash tables is hashing. The idea behind this is to represent each value with a possibly unique key and, later on, use the same key to check for the presence of...