Hashing and five popular hashing functions, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Hashing and five popular hashing functions

Explain the rgb model, RGB Model The RGB model is based on the assumpti...

RGB Model The RGB model is based on the assumption that any desired shade of colour can be obtained by mixing the correct amounts of red, green, and blue light. The exact hues

Sparse matrix, Q. Define a sparse matrix. Explain different types of sparse...

Q. Define a sparse matrix. Explain different types of sparse matrices? Show how a triangular array is stored in memory. Evaluate the method to calculate address of any element ajk

Infix expression into the postfix expression, Q. Write down an algorithm to...

Q. Write down an algorithm to convert an infix expression into the postfix expression.     Ans. Algo rithm to convert infix expression to post fix expression is given as

Determine the class invariants- ruby, Determine the class invariants- Ruby ...

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

Sort list of distinct numbers in ascending order - quicksort, (1) Sort a li...

(1) Sort a list of distinct numbers in ascending order, using the following divide- and-conquer strategy (Quicksort): divide the list of numbers into two lists: one that contains a

Row major representation, Row Major Representation In memory the primar...

Row Major Representation In memory the primary method of representing two-dimensional array is the row major representation. Under this representation, the primary row of the a

State an algorithm which inputs 3 - digit code for 280 items, A small shop ...

A small shop sells 280 different items. Every item is identified by a 3 - digit code. All items which start with a zero (0) are cards, all items which start with a one (1) are swee

Advantages of first in first out method, Advantages of First in First out (...

Advantages of First in First out (FIFO) Costing Advantages claimed for first in first  out (FIFO)  costing method are: 1. Materials used are drawn from the cost record in

Balance theorem, Question 1 Discuss the following theorems with respect to...

Question 1 Discuss the following theorems with respect to Splay Trees- Balance Theorem Dynamic Finger Theorem   Question 2 Write a C program for implementation

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd