Hashing

HASHING

Hash Table:

•      A hash table is an array-like data structure that associates its input (the key) with the associated output (the record, or value).

•      A hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g., person names) to associated values (e.g., their telephone numbers). The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought.

Hash Function:

•      At the heart of the hash table algorithm is a simple array of items; this is often simply called the hash table. Hash table algorithms calculate an index from the data item's key and use this index to place the data into the array.

•      The implementation of this calculation is the hash function,

f: index = f(key,arrayLength)

•      The hash function calculates an index within the array from the data key. arrayLength is the size of the array.

Types of Hashing:

^à Static Hashing:

The hash function maps search key value to a fixed set of locations.

^à  Dynamic Hashing:

The hash table can grow to handle more items. The associated hash function must

change as the table grows.

Methods of Hashing Function:

i)                Mid Square Method

ii)              Module Division (or) Division Remainder

iii)           Folding Method

a)     Fold shifting Method

b)    Fold boundary method

iv)           Pseudo Random Number Generator Method

v)              Digit (or) Character Extraction method.

vi)           Radix Transformation.

Applications of Hash Tables:

^à Database Systems ^àSymbol Tables ^àData Dictionaries ^àBrowse caches

COLLISION

When a memory location filled if another value of the same memory location comes then there occurs collision.

When an element is inserted it hashes to the same value as an already inserted element, then it produces collision and need to be resolved.

Collision resolving methods:

1. Separate chaining (or) External Hashing

2. Open addressing (or) Closed Hashing (linear probing,quadratic probing, double hashing)

When two keys map to the same location in the hash table is referred as collision.