The hash tables!
What is a hash table?The hash table is a tricky one. It's basically a relation between a certain number, string or identifier, called the key, and the information itself, the content, element, etc. This is done in hopes of achieving better access times, without having to iterate through the structure; rather, using the key as the identifier of where the desired information is.
|Image courtesy of Wikipedia's entry on Hash Tables|
The hash functionTo achieve better efficiency at times, the key must be a very simple piece of information, normally obtained directly from the content. In order to obtain a key to an element, one needs a hash function, which essentially calculates said key.
It is imperative that the key not only be unique, or as unique as possible, but also to be calculated with speed. Achieving both is not straight forward at all.
|A simple example on how to translate a monster's alphanumerical (numbers and letters) name into a key usable by a hash table. It is by no means the only way to do this.|
As you may see, two elements can give out the same key, which may lead to trouble later on. More on that afterwards.
What can you do with a hash table?
- Create: begin the hash table data structure, reserve the space we ask for.
- Add: put a new element.
- Delete: remove the specified element.
- Alter: change the value in the element.
- Value: get the value of the element.
- First: get the first element.
- Size: gives the number of listed objects
- Empty: checks whether the list has no elements.
How do we add things?This is probably the most particular part of the hash table. Once an object's key is calculated, we simply put said object in the index shown by the key! Theoretically, this would mean we could insert an element at once, without any more calculations.
Collisions!But what if we couldn't? Take a look at the next example.
|Key functions aren't perfect. here, we gave the character '0' value 0, so a name "Ogre" and another name "Ogre0" will return the exact same key!|
How to prepare for collisions? Obviously, "Ogre" may get in position 45 without problem, but "Ogre1" needs a place to stay. Preparing for collisions means implementing a method of reallocating the latter element so that it is still easy to reallocate, check for, alter and delete, even if it's not in its ideal key position.
One way is to have a secondary hash function, to find the latter elements a new position in the table, or keep searching for one that is empty. Once that element is allocated there, the first element must have a pointer that leads to the latter, and the same will happen if another collision is in place. The disadvantage is of course that this will occupy free keys that posterior elements may need for themselves. If so, one may reserve extra space in a hash table to store collision results so as to not interfere with the prime hashing.
Another way to do it is: instead of having elements in each position of the hash table, have a list! A list of pairs key-element. That way, whenever an element must get stored in a certain position, we simply put it at the end of the list in that position. If the collisions are few the lists do not grow excessively. Still, that means to access an element we may have to go through a whole list to get it.
There are many other ways to manage collisions, of course: instead of a list, using a tree, for instance. My intention was only to show you the simpler ways to do that. There are many tutorials that show many approaches to this issue and I urge you to search the Internet for them.
- Best case scenarios are instantaneous
- Direct relationship between an element's attribute and its key, which brings us closer to DataBase managing (like SQL, Oracle...)
- Scaling can be better controlled with Hash tables
- Resizing the hash table is not trivial
- Must think a hash function
- Must think of collision managing.
- Worst case scenarios are not bad, but still frustrating for the work a hash table needs
Finally, I must apologize to you all for not updating for the longest time. I just want to assure you I have not become uninterested with the blog at all.
Thanks for reading and keep rocking!