Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?            

Ans.

Hash Table is explained as follows:

A hash table is a data structure in which the location or address of a data item is determined straight as a function of data item itself rather than by a series of comparison. Under ideal condition, the time required to locate a data item in a hash table is 0(1) ie. It is stable and DOES not rely on the number of data items saved. When the set of K of keys stored is much less than the universe U of all possible keys, a hash table need much less storage spare than a direct address table.

Hash Functions are explained below

A hash function h is simply a mathematical formula which manipulates the key in some form to finish 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. Usually, 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 course  of  mapping  keys  to  appropriate slots  in  a  hash  table  is  termed  as hashing.

The major reconsideration for selecting hash function is :-

1)     It should be probable to compute it efficiently.

2)      It should distribute the keys uniformly across the hash table i.e. it should keep the number of collisions as small as possible.

Hashing Techniques are explained below:

There are number of hashing techniques. Some of them are given below:-

a) Division Method can be defined as:- In this method or technique, key K to be mapped into one of the m states in the hash table is spitted by m and the remainder of this spitted taken as index into the hash table. That is the hash function is

h(k) = k mod m

in which mod is the modules operation.

b)      Multiplication Method can be defined as: The multiplication method or techniques 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)]

where "K A mod 1" means the fractional part KA of KA-[KA].A A= (5-1/2)=0.6180334887

(c) Midsquare Method can be defined as:- this may operate in 2 steps. In the first step the square of the key value K is taken. In the 2nd step, the hash value is obtained by deleting digits from ends of the squared values ie. K2. The hash function is

h(k) = s

where s is obtained by deleting digits from both sides of K2.

Posted Date: 7/13/2012 1:22:28 AM | Location : United States

Ask an Expert

Related Discussions:- Hash tables, hash function and hashing techniques, Assignment Help, Ask Question on Hash tables, hash function and hashing techniques, Get Answer, Expert's Help, Hash tables, hash function and hashing techniques Discussions

Write discussion on Hash tables, hash function and hashing techniques
Your posts are moderated

Write your message here..

Related Questions

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

What are the languages which support assertions, What are the languages whi... What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Properties of asyptotic notations, what are the properties of asyptotic not... what are the properties of asyptotic notations

Representation of a polynomial with a singly linked list, List areutilized ... List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Degree of node, Q. The degree of a node is defined as the number of childre... Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

Determine the effect of ruby in implementation of string, Determine the eff... Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

Design a framework of a genetic algorithm, You have to design a framework o... You have to design a framework of a Genetic Algorithm (GA) with basic functionality. The basic functionality includes representation, recombination operators, tness function and se

A full binary tree with 2n+1 nodes, A full binary tree with 2n+1 nodes have... A full binary tree with 2n+1 nodes have n non-leaf nodes

Find longest repeat prefix of string - linear time algorithm, 1. A string s... 1. A string s is said to be periodic with a period α, if s is α k for some k > 2. (Note that α k is the string formed by concatenating k times.) A DNA sequence s is called a tand

Explain insertion procedure into a b-tree, Ans: I nsertion into the B... Ans: I nsertion into the B-tree: 1.  First search is made for the place where the new record must be positioned. As soon as the keys are inserted, they are sorted into th