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)

Posted Date: 7/13/2012 3:03:03 AM | Location : United States

Ask an Expert

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

Write discussion on Hashing and hash functions
Your posts are moderated

Write your message here..

Related Questions

Insertion of a key into a b-tree, Example: Insertion of a key 33 into a B-... Example: Insertion of a key 33 into a B-Tree (w/split) Step 1: Search first node for key closet to 33. Key 30 was determined. Step 2: Node pointed through key 30, is se

Explain in detail about the ruby arrays, Explain in detail about the Ruby a... Explain in detail about the Ruby arrays Ruby arrays have many interesting and powerful methods. Besides indexing operations which go well beyond those discussed above, arrays h

Circularly linked lists implementation, CIRCULARLY LINKED LISTS IMPLEMENTAT... CIRCULARLY LINKED LISTS IMPLEMENTATION A linked list wherein the last element points to the first element is called as CIRCULAR linked list. The chains do not specified first o

Search engines - applications of linear and binary search, Search engines e... Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

Bayesian statistics question, Suppose that there is a Beta(2,2) prior distr... Suppose that there is a Beta(2,2) prior distribution on the probability theta that a coin will yield a "head" when spun in a specified manner. The coin is independently spun 10 tim

Stack and queue, write a algorithsm in c to perform push and pop operation... write a algorithsm in c to perform push and pop operations stastic implementation using array ?

Applications of the queue, Write down any four applications of the queues. ... Write down any four applications of the queues.                                                            Ans. A pp li cation of Queue is given below (i)  Queue is

Graph, explain the prims''s algorithm with suitable example? explain the prims''s algorithm with suitable example?

Nested for loop, nested for loop for (i = 0; i for (j = 0; j seq... nested for loop for (i = 0; i for (j = 0; j sequence of statements } } Here, we observe that, the outer loop executes n times. Every time the outer loop execute

Define data model, Define data model?  A data model is a collection of ... Define data model?  A data model is a collection of conceptual tools for explaning data, data relationships, data semantics and consistency constraints.