Hash tables, hash function and hashing techniques, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Hash tables, hash function and hashing techniques

The game tree, An interesting application or implementation of trees is the...

An interesting application or implementation of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can depict the sequence of possible moves

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

Hashing and five popular hashing functions, Q. Explain the term hashing? Ex...

Q. Explain the term hashing? Explain any five well known hash functions.                         Ans: Hashing method provides us the direct access of record from the f

Curve, write a c++ program to find out the area of a curve y=f(x) between x...

write a c++ program to find out the area of a curve y=f(x) between x=a and x=b

Binary search, An unsorted array is searched through linear search that sca...

An unsorted array is searched through linear search that scans the array elements one by one until the wanted element is found. The cause for sorting an array is that we search

Heap sort, We will start by defining a new structure called Heap. Figure 3 ...

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree. Figure: A Binary Tree A complete binary tree is said to assure the 'heap con

Prims algorithm, how to write prims algorithms? with example

how to write prims algorithms? with example

Example which cause problems for hidden-surface algorithms, Example which c...

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

Data structures, 1.  You are required to hand in both a hard copy and an el...

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

Show that towers of hanoi is o (2n), Question 1 Discuss the advantages of ...

Question 1 Discuss the advantages of implementation checks preconditions Question 2 Write a ‘C' program to search for an item using binary search Question 3 Show that To

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