Hashing and hash functions, Data Structure & Algorithms

Assignment Help:

Q. Describe the term hashing. Explain any two usually used hash functions. Explain one method of collision resolution.                                                                                                     

Ans.

A hash table is a data structure in which the location or address of a data item is determined directly as a function of data item itself instead of by a sequence of comparison. Under ideal condition, the time needed to find a data item in a hash table is

0(1) ie. it is constant and documents does  not depend on the number of data items stored in it.

When the set of K of keys saved is much smaller than the universe U of all the probable keys, a hash table need much less storage spare than a direct address table.

Hash Function is described as follows

A hash function h is simply a mathematical or calculative formula that manipulates the key in some form to compute or calculate the index for this key in the hash table. Eg a hash function can split the key by some number, generally the size of the hash table and return remainder as the index for the key. Commonly, we say that a hash function h maps the universe U of keys into the slots of a hash table T[0....n-1]. This process of mapping keys to appropriate slots in a hash table is called as hashing.

A hash function h is generally a mathematical or calculative formula that manipulates the key in some form to compute or calculate the index for this key in the hash table. Eg a hash function can split the key by some number, generally the size of the hash table and return remainder as the index for the key. Commonly, we say that a hash function h maps the universe U of keys into slots of a hash table T[0....n-1]. This process of mapping keys to appropriate slots in a hash table is called as hashing.

 (a) Division Method is given as follows:- In this process, key K to be mapped into one of the m states in the hash table is separated by m state in the hash table is divided by m and the remainder of this separation taken as index into the hash table. The hash function is as follows

h(k) = k mod m

where mod is the modules operations performed.

(b)    Multiplication Methodis described as: The multiplication method or technique operates in 2 steps. In the 1st step the key value K is multiplied by a constant A in the range O

h(k) = [m (K A mod 1)]

Methods of Collision Resolution are stated below

1)      Collision Resolution by the separate chaining

2)      Collision Resolution by an open addressing

 

1)      In this scheme all elements whose key hash to same hash table slot are put in a related list. Thus the slot in the hash table comprises a pointer to the head of the related list of all the elements that hash to value i. If there is no such element that hash to value I , the slot I comprises the NULL value ( pictures as X)

1889_collision resolution.png


Related Discussions:- Hashing and hash functions

Explain the different types of traversal on binary tree, Question 1 What i...

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

Time converstion, how to convert 12 hour format into 24 hour format using c...

how to convert 12 hour format into 24 hour format using c program

What are expression trees, What are expression trees?  The leaves of an...

What are expression trees?  The leaves of an expression tree are operands, like as constants or variable names, and the other nodes have operators. This certain tree happens to

Prime''z algorithem, Ask question #explain it beriflyMinimum 100 words acce...

Ask question #explain it beriflyMinimum 100 words accepted#

Explain first - fit method, First - Fit Method: -    The free list is trave...

First - Fit Method: -    The free list is traversed sequentially to search the 1st free block whose size is larger than or equal to the amount requested. Once the block is found it

Data structure for representing numbers, Your first task will be to come up...

Your first task will be to come up with an appropriate data structure for representing numbers of arbitrary potential length in base 215. You will have to deal with large negative

Write an algorithm inputs speed of cars using pseudocode, Write an algorith...

Write an algorithm by using pseudocode which: Inputs top speeds of 5000 cars Outputs fastest speed and the slowest speed Outputs average speed of all the 5000 cars

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Tree, application of threaded binary treee

application of threaded binary treee

Process of accessing data stored in a serial access memory, The process of ...

The process of accessing data stored in a serial access memory is same to manipulating data on a By using stack  method.

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