Member Avatar for peter_budo

People did any of you come across good tutorials on hash tables???

What I got from schools is useless and teacher is not able to explain properly.

Thanx for help

  • 5 Contributors
  • 8 Replies
  • 511 Views
  • 5 Years Discussion Span
  • Latest Post Latest Post by Siddhartha_90

Dani AI

Generated

A compact, beginner-friendly walkthrough to complement 's thorough (but sometimes dense) tutorial. Start by thinking of a hash table as "an array of buckets + a hash function that picks a bucket for a key." The hash converts a key to an integer index; collisions happen when two keys map to the same index. Two simple collision strategies are separate chaining (each bucket is a linked list) and open addressing (probe for a free slot). Aim for a load factor (n / number_of_buckets) well below 1 and resize the table when it grows to keep operations near O(1).

A minimal C example (separate chaining, integer keys) to get your hands dirty:

#include <stdlib.h>

#define TABLE_SIZE 101

typedef struct Node {
    int key;
    struct Node *next;
} Node;

Node *table[TABLE_SIZE]; /* initialize all to NULL */

unsigned int hash_int(int k) {
    if (k < 0) k = -k;
    return (unsigned int)k % TABLE_SIZE;
}

void insert_key(int k) {
    unsigned int h = hash_int(k);
    Node *n = malloc(sizeof *n);
    n->key = k;
    n->next = table[h];
    table[h] = n;
}

Node *find_key(int k) {
    unsigned int h = hash_int(k);
    for (Node *cur = table[h]; cur; cur = cur->next)
        if (cur->key == k) return cur;
    return NULL;
}

Notes and troubleshooting:

  • This example omits deletion and resizing; add them next. Always free nodes to avoid leaks.
  • For strings use a tested string hash (djb2 or FNV-1a) rather than naive sums.
  • If many collisions appear: increase table size (preferably to a prime), improve the hash, or switch collision strategy.
  • Watch for signed/unsigned issues and integer overflow when building hashes.
  • Learn by iteration: implement the tiny version above, write tests that print bucket lengths, step through inserts in a debugger, then add deletion and resizing.

If the classroom explanation was unclear, this hands-on, incremental approach usually makes the core ideas click before studying the deeper variants that and others described. For production use, prefer a well-tested library implementation.

Recommended Answers

All 8 Replies

Member Avatar for Narue

>People did any of you come across good tutorials on hash tables???
No, I never came across a good tutorial on hash tables. So I . :)

Member Avatar for peter_budo

Thank you Narue,
nice tutorial but to complex. I got bitte lost even then you provided exelent coments. Do you know of something less demanding for beginner and not programmer with experience.

Cheers

Member Avatar for Narue

That's about as simple as it gets. Yes, I covered some of the complicated variations, but if you have enough experience to want to learn hash tables, you shouldn't have too much trouble with that tutorial. What parts were confusing? I'll see if I can help you understand them and probably modify the tutorial itself to make things simpler.

Member Avatar for silentdragoon

Can you link to a new version of this hash tutorial please? It seems to have been lost in the sands of time.

Member Avatar for Narue

commented: well done +10
Member Avatar for silentdragoon

Excellent, thank you very much.

Love,
sd

Member Avatar for Kev06N

Cheers for the tut' great help!

Member Avatar for Siddhartha_90

Don't wanna revive thread but I must say brilliant tutorial..thankfully survived the sands of time for the past 3 years :D

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.