Over the course of the past few months, I’ve noticed one trait about each new concept that I learn in computer science: everything has its drawbacks. In fact, I’d guess that this is actually a trait of software in general and, to be honest, any creative and technical craft. Whether we’re writing just a little bit of code, or architecting a large, complex system, we always have many tools to choose from. The trick, of course, is knowing which tool is the right one for the job. And in order to really get good at the decision-making process of choosing the right tool, we have know what its benefits and drawbacks are in order to make a fair assessment.
Hash tables, we recently discovered, are really great options for storing and retrieving specific data, quickly. They’re not always the best tool for the job — for example, they’re not great for finding ordered data — but sometimes, they can make our lives a lot easier. We already know that a hash table is made up of two parts: an array that stores all of the data that we’re hashing, and the hash function that decides where all of that data will go. However, hash tables do intrinsically have some issues of their own, and the usefulness of a hash table is tied directly to its hash function. Hash functions can be somewhat complicated, particularly if you don’t know the different types of functions that are out there. So, let’s find out more about hash functions, how they work, and their strengths and weakness. Hopefully, this will help us understand when exactly they can help us out!
Collision resolution tactics
There are a handful of ways to handle collisions in a hash function, and the important thing to remember that none of them is necessarily the “right tactic” to use. It all depends on your dataset, the size of your hash table, and what operations you know you’ll want to perform on the table later on.
Let’s take a look at two of the most common collisions resolution tactics used in hashing functions. Linear Probing
One way of handling a collisions in a hash function is by just looking for the next empty hash bucket nearby! If this sounds simple…well, that’s because it is! Don’t worry, I’m going to complicate it a little more in a minute.
The idea here is that if a collision occurs, and two elements are determined to live at the same spot in a hash table, a hash function can simply go to the next empty bucket over, and add the element there. This is a kind of rehashing, and this technique is known as linear probing.
The interesting thing about linear probing is that if the next hash bucket is also filled by an element, the hash function will just continue to probe through the hash table until it finds an empty bucket, cycling back if necessary.
This means that if we’re at the end of the hash table and no buckets are empty, the function will just loop back around to the beginning of the table, effectively probing through the table until it finds an available bucket for the element!
Source : Here