what are hash tables and how do they work?

normal

As we saw with binary search, certain ageless 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) beautifully. 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

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.

//this program creates a hash table as a set of linked lists
// here 10 pointers are used to address 10 linked lists which form a hash tablw
#include
#include

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“);
}
}

11 thoughts on “what are hash tables and how do they work?

  1. espinchi March 8, 2007 at 3:43 am

    good explanation 🙂

  2. liberty March 16, 2007 at 3:45 am

    Clear and practical explanation. Thanks.

  3. David April 13, 2007 at 3:45 am

    You use scanf for an integer and don’t check it’s return? What if I enter ‘z’?? And you’re teaching?

  4. Chris April 14, 2007 at 3:45 am

    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

  5. buggsy April 15, 2007 at 3:46 am

    Hey David,

    You misspelled the possessive its. And you’re critiquing?

  6. Danno April 15, 2007 at 3:46 am

    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.

  7. Kaell April 16, 2007 at 3:46 am

    Same issue on formatting with firefox and IE on winXP. But great info content.

  8. James April 26, 2007 at 3:47 am

    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.

  9. Ross May 1, 2007 at 3:47 am

    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.

  10. Ralph May 9, 2007 at 3:48 am

    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

  11. David May 13, 2007 at 3:48 am

    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.

Comments are closed.