Keeping up with Object-oriented Programming

Programming :))

Let’s face it, programming is not that easy. No, it was never easy for me.But, I think the practice and the training I got from the university made me who I am not–not yet an expert but I think I am knowledgeable enough. I am on the final hurdle of my student’s life. And guess what, I am on the edge of wanting to finish it sooner. Yes, if I have all the capability and the power I would have done it. I want to start facing the real world. And I think when a person graduates from the University or starts to have his or her job, you can have your freedom. This one is applicable only to me. 🙂

But before blabbering about everything that I want, there is one thing that I should say here. OOP is somewhat difficult. At first. Yes, my final system as my Special Problem is all about Object Oriented Programming. Yes, and I suck at this one. I mean, I was trained to do it in the traditional way. So relearning OOP is somewhat difficult. It means tracing the whole code when you want something to be changed. And tracing some more when you want to add a certain function. And messing up a lot of the functions when you add yours. Programming is really tedious.

And something that I learned from this one : “When it’s working, don’t mess it up.” 😉

And so, now after almost a month of reading and testing the codes I now know the basics. :)) yeah. Sorry, but my capability as a programmer is not yet that advance, so I learn things slowly. But, once on track, I want to learn more. And yes, I now know how to make objects, instances and call the get functions and inherit methods and so on. I don’t want to get too technical here, I am not yet an expert in this one.

I wish I could finish them all before the end of September, I still lack three modules. Wish me luck, hope I can squeeze those three in two days. 😀

Hashing with Linear Probing


To store data into the hash table, one must know that in order to do this, a certain value must be divided. For example if the data is consist of n integers and we have k number of cells. Then the address wherein the data would be stored is the function:

hash= n % k;

The above algorithm will only work if the given data is in integer. How about strings or character datas? For strings of integers this is done by splitting the string into equal numbers of substring, where each substring can be represented as an integer. In this way, the n in the hash function can be found by adding the value of each substring. While in the character scenario, this can be solved by assigning each letter to their corresponding place in the alphabet. For example, the letter A is 1 while Z is 26. In this manner, all letters has their own number correspondence. In the string of character problem, this problem can be solved by just adding the corresponding number of each letter, thus gaining a single number to be hashed.

The main problem that would occur is the collision, this is a scenario wherein, there will be a limited number of memory, and two or more data can collide in a single address. This problem can be solved by a rehashing algorithm


Linear Probing

The need to have a rehash function arises when a collision occurs. This happens when two or more information would collide on the same cell allocated for the hash table. Thus, a rehashing is needed.

Since we know that the hash function for storing the information or data into the allocated memory is done by getting the remainder of the data’s numerical equivalent divide by the number of space allocated. Then, the rehashing function is the method for finding the second or third or so on location for the information.

One rehashing technique is the Linear Probing, where the rehashing is done by looking for the next empty space that it can occupy. The function for the rehashing is the following:

rehash(key)=(n+1) % k;

This method works in such a way that if the first location is not free, then it will go to the next location and check if that location is free or not, and so on until it finds a free location or can’t find anyone at all.

For formality and familiarity’s sake, an empty space would be given a -1 value while a deleted data’s space would be -2. In this way, finding an empty space is easy and also the search for a stored item would be easier.

To test this algorithm, the use of the following example is needed.

For example, we have a hash table that could accommodate 9 information, and the data to be stored were integers. To input 27, we use hash(key)= 27 % 9=0. Therefore, 27 is stored at 0. If another input 18 occurs, and we know that 18 % 9= 0, then a collision would occur. In this event, the need to rehash is needed. Using linear probing, we have the rehash(key)= (18+1) % 9= 1. Since 1 is empty, 18 can be stored in it.

To retrieve data, the hash function and the rehash function were also useful. Using the example from above, retrieving 18 is done by using the hash function to find the key and check if the data would coincide to the data needed. If not, then the rehash would be needed. Until such time the correct location is found or an empty space is encountered(that is the value of that space is -1), which means that the data does not exist. This is authentic because, the path of the search function would be the same path that was used in storing the data. In this sense, if an empty space is encountered, it all means that the data does not exist, logical isn’t it?

The use of the -2 value for deleted items is useful in such a way that in traversing the hash table, encountering a deleted cell would not end the traversal.

MORE EXAMPLE(Linear Probing)

For example, 5 spaces for integers. Input: 1,5,27,25 21, 30. Delete 5. Look for 25, 29.



*To insert 1, 1 %5=1, therefore 1 is stored at array[1].

*To insert 5, 5%5=0, therefore 5 is stored at array[0].

*To insert 27, 27%5=2, therefore off to array[2].

*To insert 25, 25 % 5=0, since 0 is occupied, rehashing is done, 26%5=1, rehashing is done again, 27%5=2, then 28%5=3. Since 3 is -1, 25 can be stored here.

*30 cannot b e stored for insufficient number of memory allocation.


*Look for 5, using the hash, we found 5 at location 0. Then, we assign a new value -2 location 0 to indicate this value have been deleted.


  • To look for 25, we use the hash key, to find its location. And found 0, but then the value stored I n array[0] is not the same, therefore, the rehashing would be used. Then we traverse the hash table, until we found the right place.

  • To see if 29 does exist, we use the hash and rehash to find if they exist.


December 2019
« Apr