Most of the text books which I had read as a part of my ciruculum explain Hashing in a very abstract manner. Some text books wrongly interpret hashing as something only to do with files and searching in a file. A better way to project hashing would be as a data structure that allows faster and effcient data look-up.
Many programs that we write needs to store some temporary data which may have to be looked-up later during the execution for some purpose. The usual way one would approach this is to declare an array and search the array using a search algorithm like binary search or linear search. The problem with this method is obviously the cost pertaining to the time taken to search for the value. The time complexity of such methods are in the order of O(N) or O(N/2). This method is fine for programs which are done for an experimental or learning purpose.
So, is Hash Table some kind of a searching algorithm?
Well, not exactly. As I mentioned before, it is better called a data structure.
Consider this analogy:
Lets say that I go to a library and I am looking for “Windows CE.NET Programming by Doug Boling”.
Traditional Scenario
The conversation happnes this way in case of a traditional search algorithm, lets say, which is being used by the librarian.
Me: “Hi! I wanted Windows CE.NET Programming by Doug Boling.”
Librarian: “Ok. Give me 2 minutes. I will find out and tell you in which rack you can find the book.”
[Librarian opens up a register and looks thru page by page for the title of the book...]
[I am still waiting for an answer...]
Librarian: “Here it is. You can go to Rack 3 in the Technology section.”
Me: “Thank you.”
The hash table way...
Now lets say that the librarian is using hash tables to look-up the register.
Me: “Hi! I wanted Windows CE.NET Programming by Doug Boling.”
Librarian: “You can go to Rack 3 in the Technology section.”
Ok, so you saw how quick that was. How did the librarian manage to find out the location of the book so quickly. This brings us to a point wherein we need to know what *exactly* is a hash table and what is a hash function.
A hash table may contain objects that have keys, and values. The hash table is made of an array into which objects may be inserted, and a hashing function. The hashing function takes a key as an argument, and uses it to calculate some index in the range of the table's array. This function is used to map different elements to different arrays in the table. Hash Table approach is a more “predictable” way to look-up into a set of values.
When we want to insert an element in to the hash table, we calculate its hash value (the result of activating the hash function on the element's key). We then go to the location in the array whose index is equal to this hash value, and insert the item there. If this location in the table is already in use, we look for the nearest free location and place the element there (there are various other variations for how to handle such "collisions". the method we describe here is called "simple hashing").
When we want to locate an element in the array (given its key), we calculate its hash value, and then start scanning the table at the location whose index is equal to this hash value. If we find the element (by comparing the keys), we are done. If we find an element with a different key, we move to the next higher location (moving back to the beginning of the array if we are at the last element). We keep scanning until we either find the element, or find an empty cell. Such an empty cell indicates that the element was not found in the table, and thus the search fails.
The time complexity with hashing (in case of a perfect hash) would be O(1).
I know that if not the the concept of hash table, the actual implmentation would still be unclear. I will re-direct you to some links which graphically explain how hashing works.
1. Follow the images: http://www.sparknotes.com/cs/searching/hashtables/section1.html
2. Cool animation: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html Very lengthy explnation, but scroll down and you will find a “Run Animation” button. Its a real cool animation which explains Hashing in a very neat way.
I wonder if this is good news or bad news but its true that OpenNETCF.org is going to be acquired by Novell.
Miguel de Icaza on a press note -
"OpenNETCF.org is key to Novell's business strategy in the embedded space. We realise the potential benefits for our customers to be able write code in C# and run this under Mono not just on a server or desktop machine, but also on PDAs, smartphones, games consoles or even internet toasters. When it comes to .NET technologies and knowing the constraints that embedded devices have, the OpenNETCF.org folks really know their stuff. And we just had to have them."
Read more