Hash tables

Hash tables (I)

A hash table is a data Structure that offer very fast insertion and search sometimes deletion almost in O( 1) in the best cases. 

O( 1) means few machine instructions to finish the operation

 Advantages of Hash Tables :

1. fast 
2. easy to code

Disadvantages of Hash Tables : 

1.  based on Array (Array is fixed length data structure)
2. performance may be degraded catastrophically when the table is full.
3. no convenient way to visit item n hash table.

What is hashing ?

• hashing means convert range of key values into range of Array index.

for example :

suppose you are writing a program to access  employee records in small company say 1000 employees .
requirement :

1. database used one mega byte 
2. fastest access to any individual record
3. employees are seldom laid off and even happen their records still exist. 

every employee has been given number from 1(from the founder) to 1000 (the most recent employee ) , this employee numbers can be used as keys.

we can use an Array fixed size , size of 1000 record , every array record contain employee object , since we know accessing specified  array element is very fast , when we know its index.

empRecord rec = databaseArray[500];

here is basic idea of hashing an easy way to find the index .

adding new record is easy too :

databaseArray[totalEmployees++] = newRecord;

as you know maximize array size is not an easy task since it require allocate new memory space and recopy the old one , we can made the database array more larger.

to be continued isA soon , i have to go to the Army in the next few hours .

i hope you are interested now to read about hashing .

with my best wishes

Ahmed Ghazey

resource : Data Structures & Algorithms in Java Second Edition
Robert Lafore