Constructing a HashMap in two (and a half) ways I can think of (”ʘ⌄ʘ”)

PART 1: Using a simple list but more importantly, understanding how it works.

HashMaps. Daunting? Most definitely. Yet, understanding it is a beautiful way of actually seeing how data structures encompass everything important to you, from your phones storing contacts to your usernames being valid or unique… everything!

Before you continue, you must have knowledge of a few basics in data structures. For example, arrays, Nodes and lists, and Trees (Binary Search Trees).

Let us begin

Think of it this way; You currently posses a bucket. The bucket is well, big enough for storing 3 rolls of cardboard, similar to the ones around which toilet papers are rolled. There’s a reason why Ive decided to keep the rolls empty, you'll see why. Now, assume that you can only write a single number one a roll. That means you are restricted to ONLY three numbers! That’s dumb and actually pretty useless. What a waste of buckets. Fortunately, that's not how real world engines and machines work.

you cant fit 3 million numbers in a bucket if it can only hold 3

To solve this problem, I have a solution. Take a roll of paper, write a fourth number on it. Simple enough, lick the other end of the paper and roll it over any one of the cardboard roll :)

You can proceed to store all your numbers in this fashion without anything going wrong yay! Psych, that's not enough. Why you may ask?

Evident enough, this is no way of searching through something that has to store millions of numbers

Its because when you wanna search for a number you may have entered a year and 3 months later, you wouldn’t even know which cardboard roll you have to unroll in the first place! You could proceed to open up all of the rolls one by one (I say one by one because a computer does not move on to the next “roll” until it has finished the “roll” its searching through). That’s too much work and highly impractical.

big brain time boys and girls

There's a way to solve this problem too. Scientists a few decades ago realized that entering a phone number into a system was easy, but when the time came to retrieve it, searching would take 4 to 7 whole minutes! That’s ew. So, they constructed a method to store the numbers on the rolls very efficiently so that searching them/removing them from the “Extended Bucket” would not last longer than a second.

This is the most important step in creating a hashmap. Mathematicians devised functions which would convert a number into a “hashed form”, so as to find a suitable place for it in the bucket (i say bucket but i actually mean array lol my bad).

Here comes some easy math;

Assuming we have the worlds best hashing function, H( ). This function converts a number a you want to put into the bucket, and gives you a very different number b.

NOTE: A hashing function will only give you b when you send it “a” and nothing else because the function doesn't change, and hence the result doesn't either. Its the same logic as how everything raised to the power 0 is equal to 1.

Once we get a weird result from the function, we proceed to divide it by the size of the bucket/array. In our case, its 3. There could either be a remainder or there could not. Depending on that we could see on which roll we must add our number. Lets say i sent the number 234, and from the hashing function H(), I got a number 6745. When we divide it by 3, we get a quotient of 2248 and a remainder of 2. We proceed to take the 3rd roll and stick the paper inscribed with 234 on the roll.

Now that I have explained what hashing does, we proceed. A few pointers for the reader though;

1. We use the remainder because when the number to be placed in the list is divided by the size of the array, the remainder will give us the position where the number has to be placed.

2. It is not necessary that the numbers will be divided equally among the rolls, albeit that would be convenient. Good hashing functions are designed in such a way that numbers/input from the user is divided equally among the rolls.

enough talk, lets code

Step 1: Make three classes

One class will be your driver, while the other two are responsible for making Nodes and Managing how those nodes function.

Class node to make spaces in the memory for your numbers

This “Node” class has three elements; key, prev and next. Yes, I am using a doubly linked list as it is much more convenient than a singly linked list for deletion etc.

Manager Class to direct the integer entered by the user into a node and also to check if it is in the structure we created or not

The DLL class here does what it does best, manage. It is responsible for handing the integers to class Node to make a node and save the integer entered by the user in the node. Then, the function “insertInList()” proceeds to create all the necessary links between the Nodes created so that the list maintains integrity.

This is the driver class (without the main function)

Sure enough, I didn't iterate. I used recursion because recursion is what makes any algorithm understandable for any language and compiler. Yes, it is heavier and i would not recommend using it if you have an astronomically large input size, but for a range between 10,000 and 1,000,000, it works just fine.

make sure you implement everything in recursion before you use loops

The two functions are pretty easy. What should stand out is that like I had mentioned before, the step which included the use of the remainder is used in both functions. This is because the results will always be the same for a number. This remainder will tell us which roll has to be unraveled to search for the number.

Step 2: Make your own main function.

Call the functions in your driver class from it and see the magic happen. If you’re experienced enough, use the debugger and you can write down how it works on a piece of a paper and chart the addresses on which the nodes are placed in the memory.

Part 2 will include me tweaking this implementation as well as using a Binary Search Tree to perfect the running times and make it easier to search through.

I’ll drop the file down below.

Bye now

Full code in my repository. Click the link . (︶.̮︶✽)