Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | Hashing

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.

**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.**

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.