Skip to main content

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

Comments

Post a Comment

Popular posts from this blog

DevExpress C# Chart Tutorial

Hello , this blog post about Charting in DevExpress , I faced many problems I visited hundreds of pages to solve this problems , actually it was the first time I use DevExpress Charts, Work is not like school or university , in school if you don't know thing you can learn it any time you want , in work you have to do today task yesterday, I like to share my knowledge and skills with you , I hope this Post help you . // clear series on chart  chart.Series.Clear(); // clear Titles of chart chart.Titles.Clear(); // legend alignment  chart.Legend.AlignmentHorizontal = LegendAlignmentHorizontal.Center; chart.Legend.AlignmentVertical = LegendAlignmentVertical.Bottom; chart.Legend.Direction = LegendDirection.LeftToRight; // creating series // series view Type example Line DevExpress.XtraCharts.Series series = new DevExpress.XtraCharts.Series("series name ", ViewType.Line); // add title  DevExpress.XtraCharts.ChartTitle chtTitle = new DevExpress.XtraCharts.Cha...
3 comments
Read more

Designing Entity Relationship Diagram (ERD)

Al Salmo Aliko . Hello, in this post I'll discuss with you how to design good Entity Relationship Diagram ERD . this article for: IT Students learning about database. you are having difficulties in creating ERD. you are developer that need help in database design.   let's ask ourselves Why good database design is good ? or why we need ERD?         when I started programming Eng / Eman Ahmed was my First teacher, she said you must write your code with pen, and now I told you good database design start with paper and pen or in technological terms start with ERD, ERD is the model which shows logical layout of your database. let's List some advantages of good database design : very low or no redundant data is stored.  supporting planed or unplanned queries. good design easy to maintain and modify. from first glance you can understand it. an ERD consist from Entities and relationships between them; there exist...
2 comments
Read more

LeetCode Problem #11 Container With Most Water

LeetCode Problem #11 Container With Most Water Given  n  non-negative integers  a 1 ,  a 2 , ...,  a n  , where each represents a point at coordinate ( i ,  a i ).  n  vertical lines are drawn such that the two endpoints of line  i  is at ( i ,  a i ) and ( i , 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note:  You may not slant the container and  n  is at least 2. The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. Problem Link Solution Number One O(n^2) Brute Force : Try all valid combinations  outer loop start from i = 0 to length of array inner loop start from j = i+1 to length of array  compare current area with new area and choose max. return max area. Solution Number Two O(n) : Linear Solution greedy algorithm: calc...
Post a Comment
Read more