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...