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

Write down a module to merge two linked lists, Two linked lists are having ... Two linked lists are having information of the same type in ascending order. Write down a module to merge them to a single linked list that is sorted merge(struct node *p, stru

Explain principle of optimality, Explain principle of Optimality It ind... Explain principle of Optimality It indicates that an optimal solution to any instance of an optimization problem is composed of  optimal solutions to its subinstances.

Explain about the structured types - built-in types, Explain about the Stru... Explain about the Structured types - Built-In Types Values of the carrier set are not atomic, consisting rather than several atomic values arranged in some way. Common illu

What is called the basic operation of an algorithm, What is called the basi... What is called the basic operation of an algorithm? The most significant operation of the algorithm is the operation contributing the most to the total running time is known as

Explain the term - branching, Explain the term - Branching There are t... Explain the term - Branching There are two common ways of branching: case of ..... otherwise ...... endcase  if ..... then ..... else ..... endif   case of

Column major representation, Column Major Representation In memory th... Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

Financial index data analysis, need c++ algorithmic software program to der... need c++ algorithmic software program to derive one numerical outcome from 10 levels of variables with 135 combinations cross computed

Graph traversal schemes, Various graph traversal schemes Graph Traversa... Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

Fifo, give any example of page replacement using fifo and use your own refe... give any example of page replacement using fifo and use your own reference string

All pairs shortest paths algorithm, In the last section, we discussed regar... In the last section, we discussed regarding shortest path algorithm that starts with a single source and determines shortest path to all vertices in the graph. In this section, we