As we saw with binary search, certain data structures such as a binary search tree can help improve the efficiency of searches. From linear search to binary search, we improved our search efficiency from O(n) to O(logn). We now present a new data structure, called a hash table, that will increase our efficiency to O(1), or constant time.
In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person’s name), find the corresponding value (e.g. that person’s telephone number). It works by transforming the key using a hash function into a hash, a number that is used to index into an array to locate the desired location (”bucket”) where the values should be.
Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. (O(1) means that it takes a constant amount of time independent of the number of items involved.) However, the rare worst-case lookup time can be as bad as O(n). Compared to other associative array data structures, hash tables are most useful when large numbers of records are to be stored, especially if the size of the data set can be predicted.
Hash tables may be used as in-memory data structures. Hash tables may also be adopted for use with persistent data structures; database indexes sometimes use disk-based data structures based on hash tables, although balanced trees are more popular.
// here 10 pointers are used to address 10 linked lists which form a hash tablw
#include<stdio.h>
#include<malloc.h>
int main()
{
int i,k,num;
struct node
{
int n;
struct node* next;
};
struct node *temp,*p1,*AOP[10];
for(i=0;i<10;i++)
AOP[i]= NULL;
for( i=0;i<20;i++)
{
scanf(“%d”, &num);
k=num%10;
p1=( struct node*) malloc ( sizeof(struct node));
p1->n=num;
p1->next=NULL;
if(AOP[k]==NULL)
AOP[k]=p1;
else
{
p1->next=AOP[k];
AOP[k]=p1;
}
}
for(i=0;i<10;i++)
{
temp=AOP[i];
printf(“List number %d :”, i);
while(temp!=NULL)
{
printf(“%5d”,temp->n);
temp=temp->next;
}
printf(“\n“);
}
}
good explanation
Clear and practical explanation. Thanks.
Kewl website. really appreciate the effort in making learning colorful . Keep up the good work and also keep updating the website. All my support and kudos to you!
Santu
You use scanf for an integer and don’t check it’s return? What if I enter ‘z’?? And you’re teaching?
Go easy, David-programming-god. He is teaching about hash tables, not about robust programming. Don’t try to search off-topic errors just to sound intelligent, and appreciate the good explanation as we others do.
Nice site indeed!
Chris
Hey David,
You misspelled the possessive its. And you’re critiquing?
Hallo, This is a rather nice blog, I do believe I’ll subscribe. But could you consider fixing the formatting in the code samples? In Firefox on OS X the indentation is lost and makes the programs rather hard to read.
Same issue on formatting with firefox and IE on winXP. But great info content.
This contents are really excellent. It is proving fruitful to all sort of ace programmers of corporates.
Good explanation. However, I think that it either needs expanding or another article to supplement it. I think there should be some mention of the hash function itself and how to create a good hash function if the key is not a simple integer. I also think there needs to be mention of expanding the array when it becomes full.
The article was nice, but it didn’t actually explain how to add an item to the table. Also, as James said, you do need to go more in depth in how to actually use a hash table.
Actually, this article sounded more like it was an explanation of a lookup table, not a hash table.
Great site. I found it by a lucky “Stumble”. Good clear answers. Thank you.
Just stumbled upon your website with wonderful explanations of data-structures, algorithms and more. I just want to say this is great stuff and it really helps people like me which don’t come from a traditional programming background.
I’m currently trying to understand O-notation to the fullest and I’m finally coming around understanding what the functions represent. One thing you can help out here is with an explanation of O-notation and how you can derive to a specific Order based on given code.
Many books/websites will say that a Hashtable is O(1) or a Binary is O(logn) but they don’t show you how to arrive to that conclusion. The reason I think this is important is because when we write our own algorithms we’ll need a way to find the Order on average-case running time. Doing this for an algorithm I can write is not always easy to know how to do.
I know there are methods for calculating algorithm complexity by counting the operations by hand. After, we discard the constants that are lowest and other factors eventually just ending up with the Order itself. This process is what eludes me currently and this is something you can help with I would think.
Another good article could be on Bitwise manipulation. I love reading about that stuff as well.
Take care!,
-Ralph
A person who uses scanf without checking the return, in even a trivial example, is either uniformed or a schlock. Further, the example is virtually meatless in regard to hash tables.