Hashing and five popular hashing functions, Data Structure & Algorithms

Q. Explain the term hashing? Explain any five well known hash functions.                        

Ans:

Hashing method provides us the direct access of record from the file dosent matter where the record is in the file. This is made possible with the help of a hashing function H which map the key with the corresponding key address. It provides us with the key- to-address transformation.

Five well known hashing functions are as follows:

The Division Method: An integer key x is divided by the table size m and the remainder is occupied as the hash value. This may be defined as

H(x)=x%m+1

Take an example, x=42 and m=13, H(42)=45%13+1=3+1=4

The Midsquare Method: In this a key is multiplied by itself and the hash value is obtained by selecting an suitable number of digits from the middle of the square. The identical positions in the square must be used for all keys. Taking an example, if the key is 12345, square of this key is given by value 152399025. If 2 digit addresses is needed then position 4th and 5th can be chosen, giving address 39.

The Folding Method: In this a key is broken into several parts. Each part has the same length similar to that of the required address apart from the last part. The parts are added together, ignoring the last carry, we get the hash address for key K.
The multiplicative method:  In this technique a real number c  such  that  0

H(x)=[m(cx%1)]+1

In this,cx%1 is the fractional part of cx and [] denotes the greatest integer less than or equal to its own contents.

The Digit Analysis: In this method the addresses is formed by selecting and shifting digits of the original key. For a given set of key, the same positions in the key and same rearrangement of the pattern must be used. By taking an example a key 7654321 is transformed to the address 1247 by selecting the digits in the position 1,2,4 and 7 then by reversing the order.

Posted Date: 7/10/2012 6:32:27 AM | Location : United States







Related Discussions:- Hashing and five popular hashing functions, Assignment Help, Ask Question on Hashing and five popular hashing functions, Get Answer, Expert's Help, Hashing and five popular hashing functions Discussions

Write discussion on Hashing and five popular hashing functions
Your posts are moderated
Related Questions
An unsorted array is searched through linear search that scans the array elements one by one until the wanted element is found. The cause for sorting an array is that we search

Linked List  A linked list is a linear collection of data elements called nodes. The linear order is given by pointer. Every node is divided into 2 or more parts.

How memory is freed using Boundary tag method in the context of Dynamic memory management? Boundary Tag Method to free Memory To delete an arbitrary block from the free li

Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's

A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

Merge sort: Merge sort is a sorting algorithm that uses the idea of split and conquers. This algorithm splits the array into two halves, sorts them separately and then merges t

N = number of rows of the graph D[i[j] = C[i][j] For k from 1 to n Do for i = 1 to n Do for j = 1 to n D[i[j]= minimum( d ij (k-1) ,d ik (k-1) +d kj (k-1)

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

Define Strictly Binary Tree Strictly Binary Tree: - If each non leaf node in binary tree has non empty left and right sub-trees , then the tree is known as a strictly binary t

Write a program to create a hashed file that stores the records currently in the file " data_2013 ". Records should use the same fixed-length schema given previously, and should ag