hashing is a technique for performing almost constant time in case of insertion deletion and find operation.

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects.

Mapping key must be simple to compute and must help in identifying the associated records.

Function that help us in generating such type of keys is termed as Hash Function.

Hashing is the process of mapping large amount of data item to a smaller table with the help of a hashing function. The essence of hashing is to facilitate the next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand vast amount of data items in a given collection (i.e. collection size). Due to this hashing process, the result is a Hash data structure that can store or retrieve data items in an average time disregard to the collection size.

Hash table support on eof the most efficient type of searching. Fundamentally a hash table consists of an array in which data is accessed via a special index caled key.

- Database system
- Symbol table in compiler
- Tagged buffer etc.

Hash function is a function which is applied to the key produce an int which can be used as an aggress in a hash table.

Perfect hash function produces no collision. Good hash function minimize collision by seperating the elements uniformly throughout the array.

- Hashing With Channing or Separate Chaining

- Linear Porbing
- Quadratic Probing
- Double Hashing

Hashing Name | Hash Function |

Hashing With Channing | ` h(k)=k mod n ` |

Linear Probing | ` h(k,i)= (h` |

Quadratic Probing | ` h(k,i)= (h` |

Double Hashing | ` h(k,i)= (h` |

Conside the following insertion of element

5, 28, 19, 15, 20, 33, 12, 17, 10into a chained hash table. The hash table has nine slots and function being`h(k) = k mod 9.`

`h(5) = 5 mod 9 = 5 `

`h(28) = 28 mod 9 = 1 `

`h(19) = 19 mod 9 = 1 `

`h(15) = 15 mod 9 = 6 `

`h(20) = 20 mod 9 = 2 `

`h(33) = 33 mod 9 = 6 `

`h(12) = 12 mod 9 = 3 `

`h(17) = 17 mod 9 = 8 `

`h(10) = 10 mod 9 = 1 `

Conside the following keys

26, 37, 59, 76, 65, 86inta a gash table of size m=11 using linear probing, consider the primary hash function`h`

^{'}(k) = k mod m

Consider insertion the keys

20, 12, 31, 4, 25, 28, 27, 88, 69into a hash table of length m=11, hashing open addressing with the primary hash function`h`

. Illustrate the result of inserting keys using double hashing with_{j}(k) = k mod m`h`

._{2}(k) = 1+ ( k mod (m-1))

Hope you have enjoyed this post. :)

Blog Category

© 2017 atnyla All rights reserved