Hashing

DEFINITION:
A hash table is a special collection that is used to store key-value items. So
instead of storing just one value like the stack, array list and queue, the
hash table stores 2 values. These 2 values form an element of the hash
table.

Do C have a built in hash table:
In C we only have indexed arrays to work with. Thus to make a hash table
we will need to retrieve data with functions that use indexed arrays.

*HASHING:
Hashing is an efficient method to store and retrieve elements.
It’s exactly same as index page of a book. In index page, every topic is
associated with a page number. If we want to look some topic, we can
directly get the page number from the index.

How to calculate the hash key? Let’s take hash table size as 7.
size = 7 arr[size];
Formula:
key = element % size

*INITIALIZATION OF THE HASH BUCKET
Before inserting elements into array. Let’s make array default value as -1.
-1 indicates element not present or the particular index is available to
insert.

*INSERTING ELEMENTS

INSERTED 24

INSERTED 8

*What if we insert an element say 15 to existing hash table?
Insert : 15
Key = element % key
Key = 15 % 7
Key = 1
But already arr[1] has element 8 !
Here, two or more different elements pointing to the same index under
modulo size. This is called collision.

*IMPLEMENTATION OF HASH PROGRAM
Create an array of structure, data (i.e a hash table).
Take a key to be stored in hash table as input.
Corresponding to the key, an index will be generated.
*BASIC OPERATION OF A HASH TABLE
searches ,inserts and deletes an element from the hash table

*USES:
to compute an index ,also called hash code ,into an array of buckets or
slots from which the desired location can be found
*ADVANTAGES:
Synchronization
In many situations, hash tables turn out to be more efficient than search
trees or any other table lookup structure. For this reason, they are widely
used in many kinds of computer software's, particularly for associative
arrays, database indexing, caches and sets.

*DISADVANTAGES:
Hash collisions Hash tables becomes quite in efficient when there are
many collisions Hash tables does not all