Hashing in C Language Posted Date: 31 Oct 2009     Resource Type: Articles/Knowledge Sharing     Category: Computer & Technology Author: Dhananjoy Chakraborty Member Level: Gold     Rating: Points: 16 (Rs 10)

The search time of this algorithm is independent of the size of elements.In binary and sequential searching a number of comparisons are required to find out a value.In searching best algorithms are those that minimize these comparisons.In hashing there is no unnecessary searching.In one single attempt the value may be retrieved from the array.When the value is retrieved in one chance ,this means there is some relation between the value and the location where the value is stored.The values themselves can serve as indices to the array. Let us consider that a company with an inventory file where each part has a part number of 5 digits and the part numbers are to be stored in an array.Suppose the company has 100 such parts.If we set the part numbers as the array index then for 100 part numbers we need an array of huge size where most of the memory cells will be left vacant.Here we will use the last two digits of the part numbers as the array index , so the lower bound of such array will be 0 and upper bound will be 99. A function that converts the part number into an array index is called hash function.If HAS is the hash function and VALUE is the part number , then HAS(VALUE) is called the hash of key and is the index where the value should be set in the array.If K is the value returned by hash function then K is called the hash key of VALUE.The hash function of the above example is HAS(VALUE)=VALUE % 100.This function can produce a number between 0 and 99 and this will be the index value. So if the part number is 11111 then it's position in the array is 11th index.For part number 78988 , the number will be set at 88th index. This method has one flaw.If hash key of two different part numbers becomes same.Suppose the numbers are 78988 and 23188.Here in both the cases hash key is 88.If 78988 is set in the 88th position of the array then we can not set 23188 in the same location.Such a situation is called hash collision or hash clash . There are two basic methods of dealing with a hash collision.The first process is known as rehashing where another hash function is used on the hash key to find the next available empty space in the array where the value will be positioned. The second method is called chaining where a separate linked list is created and all the values with same hash key are set .

Responses

No responses found. Be the first to respond and make money from revenue sharing program.

Feedbacks

Popular Tags   What are tags ?   Search Tags   Sign In to add tags. Searching  .

Post Feedback This is a strictly moderated forum. Only approved messages will appear in the site. Please use 'Spell Check' in Google toolbar before you submit. You must Sign In to post a response.

Next Resource: Data Structure in C Previous Resource: Merge Sort Return to Discussion Resource Index Post New Resource Category: Computer & Technology Post resources and earn money!   More Resources Array in C Language Abstract Data Type (C Language) Using Pen Drive For Data Transfer. How to hide a Drive in your computer? How To Use PSoC IDE - A Detailed Description Why Download Skins For Your Web Browser