হ্যাশ টেবিল — চাবি থেকে সরাসরি ঠিকানায় পৌঁছানো

১ · স্বপ্নটা কী — খোঁজাখুঁজি ছাড়াই এক লাফে পৌঁছানো

একটি বিশ্ববিদ্যালয়ের হলে এক হাজার ছাত্র থাকেন। অফিসে একটি খাতায় সবার নাম আর রুম নম্বর লেখা। একজন অভিভাবক এসে বললেন, “রোল ২৩৪১-এর ছেলেটি কোন রুমে?” কেরানি খাতার প্রথম পাতা থেকে আঙুল চালিয়ে খুঁজতে শুরু করলেন। ভাগ্য খারাপ হলে এক হাজার নাম পড়তে হবে।

এবার অন্য একটি হলের কথা ভাবুন। সেখানে নিয়ম হলো — রোল নম্বরের শেষ তিন অঙ্কই রুম নম্বর। রোল ২৩৪১ মানে রুম ৩৪১. কেরানিকে খাতা খুলতেই হয় না। একটি ছোট হিসাব, তারপর সোজা হেঁটে সেই রুমে। একজন ছাত্র খুঁজতে যত সময়, এক লাখ ছাত্র থাকলেও প্রায় তত সময়।

এ পর্যন্ত কোর্সে আমরা খোঁজার তিনটি উপায় দেখেছি। প্রতিটির দাম আলাদা:

খেয়াল করুন, array-তে a[341] এক ধাপের কাজ, কারণ CPU base + 341 × size হিসাব করে সরাসরি সেই ঠিকানায় যায় (পর্ব ১৬)। সমস্যা হলো, বাস্তবের চাবি প্রায় কখনো সুন্দর ছোট সংখ্যা নয়। চাবি হতে পারে একটি নাম (“Mitu”), একটি মোবাইল নম্বর (01711-xxxxxx), একটি ওয়েবসাইটের ঠিকানা। a["Mitu"] লেখা যায় না।

২ · Hash function — চাবিকে ঘরের নম্বরে বদলানো

যে নিয়মটি চাবিকে সংখ্যায় বদলায়, তার নাম hash function. হলের উদাহরণে নিয়মটি ছিল “শেষ তিন অঙ্ক”। কিন্তু চাবি যদি লেখা হয়, যেমন “Dhaka”? পর্ব ১৯-এ দেখেছি, C-তে একটি string আসলে কয়েকটি byte-এর সারি — প্রতিটি অক্ষর একটি ছোট সংখ্যা (ASCII মান)। 'D' মানে 68, 'h' মানে 104. তাহলে অক্ষরগুলোর সংখ্যা মিলিয়ে একটি বড় সংখ্যা বানানো যায়।

সবচেয়ে বিখ্যাত সহজ string hash-গুলোর একটি হলো djb2. এটি তৈরি করেন গণিতবিদ ও ক্রিপ্টোগ্রাফার Daniel J. Bernstein; বহু বছর আগে তিনি এটি comp.lang.c নামের অনলাইন আলোচনা-গ্রুপে প্রকাশ করেছিলেন। নিয়মটি মাত্র দুই লাইনের: শুরুতে h = 5381, তারপর প্রতিটি অক্ষর c-এর জন্য h = h * 33 + c. শেষে মোট ঘরের সংখ্যা দিয়ে ভাগশেষ নিলে পাওয়া যায় ঘরের নম্বর। নিচে “Dhaka” চাবিটি ৮টি ঘরের একটি টেবিলে কোথায় যাবে, ধাপে ধাপে হিসাব করে দেখুন:

1size_t hash(const char *s) {2    unsigned long h = 5381;3    while (*s) {4        h = h * 33 + (unsigned char)*s;5        s++;6    }7    return h % 8;     /* 8 buckets */8}

ভালো hash function-এর তিনটি গুণ

একটি গুরুত্বপূর্ণ কথা: এখানে “ভালো” মানে টেবিলের জন্য ভালো। পাসওয়ার্ড বা ডিজিটাল স্বাক্ষরের জন্য যে hash লাগে (যেমন SHA-256), তার লক্ষ্য একেবারে আলাদা — সেটি ধীর হলেও চলে, কিন্তু উল্টো দিক থেকে ভাঙা অসম্ভব হতে হবে। ভাবনার প্রশ্ন ৫-এ এ নিয়ে বিস্তারিত আছে।

৩ · Collision — যা কখনো এড়ানো যায় না

এখন একটি অস্বস্তিকর সত্য। Hash function যত ভালোই হোক, দুটি আলাদা চাবি একই ঘরে পড়বেই। একে বলে collision. কারণটি সহজ গণিত — pigeonhole principle: ১০টি কবুতর আর ৯টি খোপ থাকলে অন্তত একটি খোপে দুটি কবুতর ঢুকবেই। সম্ভাব্য নাম অসংখ্য, আর আমাদের টেবিলে ঘর মাত্র কয়েকটি।

আমাদের ৮ ঘরের টেবিলেই দেখুন: djb2 দিয়ে “Rafi” আর “Joy” দুটোই যায় ৭ নম্বর ঘরে। “Dhaka”, “Sylhet” আর “Comilla” — তিনটিই ৬ নম্বরে। এটি hash-এর দোষ নয়; ৮টি ঘরে বেশি চাবি রাখলে এমন হবেই।

কত তাড়াতাড়ি collision শুরু হয় — জন্মদিনের ধাঁধা

একটি ক্লাসে কতজন থাকলে দুজনের জন্মদিন একই দিনে হওয়ার সম্ভাবনা ৫০%? অনেকে আন্দাজ করেন ১৮০ জনের মতো (৩৬৫-এর অর্ধেক)। আসল উত্তর মাত্র ২৩ জন। একে বলে birthday paradox. ধাঁধাটি আসলে ভুল আন্দাজের: আমরা ভাবি “আমার সাথে কারও মিলবে কি না”, অথচ প্রশ্ন হলো “যেকোনো দুজনের মিলবে কি না” — আর ২৩ জনে জোড়া হয় ২৫৩টি।

অর্থাৎ ১০ লাখ ঘরের টেবিল ১% ভরার অনেক আগেই প্রথম collision হয়ে যায়। ৫০ জনের ক্লাসে জন্মদিন মেলার সম্ভাবনা প্রায় ৯৭%, আর ৭০ জনে প্রায় ৯৯.৯%. তাই hash table নকশার প্রশ্ন কখনোই “collision কীভাবে এড়াব” নয় — প্রশ্ন হলো “collision হলে কী করব”।

৪ · Separate chaining — প্রতিটি ঘরে একটি শিকল

পর্ব ৩৩-এ আমরা linked list বানিয়েছিলাম — প্রতিটি node নিজের ডেটা আর পরের node-এর ঠিকানা রাখে। Separate chaining-এ hash table হলো আসলে কয়েকটি linked list-এর মাথার একটি array. প্রতিটি ঘরকে বলে bucket. শুরুতে সব bucket-এ NULL — অর্থাৎ খালি শিকল।

নিচে ৮টি bucket-এর একটি টেবিলে ছাত্রদের নাম আর নম্বর রাখা হচ্ছে। চতুর্থ নামটিতে collision হবে। তারপর দুটি খোঁজা — একটি পাওয়া যাবে, একটি যাবে না:

1put("Rafi", 78);    /* hash -> 7 */2put("Mitu", 91);    /* hash -> 4 */3put("Tanvir", 65);  /* hash -> 1 */4put("Joy", 83);     /* hash -> 7 ! */5get("Rafi");6get("Sakib");       /* hash -> 7 */

এবার পুরো জিনিসটি আসল C-তে। এটি একটি সম্পূর্ণ, ছোট hash table: নাম থেকে নম্বর। put রাখে, get খোঁজে, আর শেষে প্রতিটি শিকলের প্রতিটি node free করা হয়:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NB 8                                   /* number of buckets */
typedef struct Node { const char *key; int marks; struct Node *next; } Node;
Node *table[NB];                               /* 8 empty chains (all NULL) */
size_t hash(const char *s) {                   /* djb2 -> bucket index */
    unsigned long h = 5381;
    while (*s) h = h * 33 + (unsigned char)*s++;
    return h % NB;
}
void put(const char *k, int m) {               /* new node joins the chain front */
    Node *n = malloc(sizeof *n);  if (n == NULL) { perror("malloc"); exit(1); }
    size_t b = hash(k);  *n = (Node){ k, m, table[b] };  table[b] = n;
}
int get(const char *k) {                       /* -1 means not found */
    for (Node *n = table[hash(k)]; n != NULL; n = n->next)
        if (strcmp(n->key, k) == 0) return n->marks;
    return -1;
}
int main(void) {
    put("Rafi", 78); put("Mitu", 91); put("Joy", 83);   /* Rafi, Joy: bucket 7 */
    printf("Joy -> %d, Rafi -> %d, Sakib -> %d\n", get("Joy"), get("Rafi"), get("Sakib"));
    for (int i = 0; i < NB; i++)                /* free every node of every chain */
        while (table[i]) { Node *n = table[i]; table[i] = n->next; free(n); }
    return 0;
}

৫ · Open addressing — পাশের খালি ঘর খোঁজা

Chaining-এ প্রতিটি নতুন চাবির জন্য একটি malloc, আর প্রতিটি node মেমরির কোথায় পড়বে ঠিক নেই। Open addressing অন্য পথে যায়: সব চাবি একটিই array-তে, প্রতি ঘরে একটি করে। ঘর ভরা থাকলে একটি নির্দিষ্ট নিয়মে পরের ঘর দেখা হয়। সবচেয়ে সহজ নিয়মটি হলো linear probing — ঠিক পরের ঘর, তারপর তার পরেরটা, শেষে পৌঁছালে আবার শুরুতে ((i + 1) % 8).

নিচে ৮ ঘরের টেবিলে কয়েকটি জেলার নাম রাখা হচ্ছে। djb2 দিয়ে Dhaka, Sylhet আর Comilla তিনটিই ৬ নম্বরে পড়ে। শেষ ধাপে একটি লুকানো ফাঁদ আছে — খেয়াল রাখুন:

1put("Dhaka");     /* hash -> 6 */2put("Sylhet");    /* hash -> 6 */3put("Comilla");   /* hash -> 6 */4put("Khulna");    /* hash -> 0 */5get("Khulna");6get("Rajshahi");  /* hash -> 7 */7slot[7] = EMPTY;  /* delete Sylhet */8get("Comilla");

তাহলে দুটির মধ্যে কোনটি ভালো? উত্তরটি নির্ভর করে মেমরির আচরণের ওপর। আগের পর্বগুলোতে (পর্ব ১৬ ও ২২) দেখেছি, CPU মেমরি থেকে একবারে একটি পুরো cache line আনে, তাই পাশাপাশি রাখা ডেটা খুব দ্রুত পড়া যায় (spatial locality). Linear probing-এর “পরের ঘর” প্রায়ই একই cache line-এ থাকে। Chaining-এর পরের node হয়তো heap-এর অন্য প্রান্তে।

৬ · Load factor ও resizing — টেবিল ভরে এলে কী করবেন

টেবিল কতটা ভরা, তা মাপার সংখ্যাটির নাম load factor: মোট চাবি ÷ মোট ঘর। ৮ ঘরে ৬টি চাবি মানে load factor 0.75. Chaining-এ এটিই গড় শিকলের দৈর্ঘ্য। ১০ লাখ চাবি যদি ৮টি ঘরেই থাকে, প্রতিটি শিকল গড়ে সোয়া লাখ লম্বা — তখন “hash table” আসলে ৮টি লম্বা linked list.

Linear probing-এ load factor আরও নাটকীয় প্রভাব ফেলে। Donald Knuth-এর বিশ্লেষণ থেকে পাওয়া গড় হিসাব দেখুন (চাবি টেবিলে আছে বা নেই — দুই ক্ষেত্রে গড়ে কতগুলো ঘর দেখতে হয়):

অর্থাৎ ৯০% ভরা টেবিলে “নেই” বলতে গড়ে ৫০টি ঘর দেখতে হয়। তাই প্রতিটি বাস্তব hash table একটি সীমা ঠিক করে রাখে — যেমন Java-র HashMap-এর ডিফল্ট সীমা 0.75, আর CPython-এর dict প্রায় দুই-তৃতীয়াংশ ভরলেই বড় হয়। সীমা পেরোলে শুরু হয় rehashing: দ্বিগুণ বড় নতুন array নেওয়া, আর প্রতিটি চাবিকে নতুন ঘরের সংখ্যা দিয়ে আবার % করে নতুন জায়গায় বসানো।

একটি insert-এ পুরো টেবিল নতুন করে সাজানো — শুনতে ভয়ংকর। কিন্তু পর্ব ২০-এর dynamic array-র যুক্তিটি এখানেও খাটে। প্রতিবার দ্বিগুণ করলে বড় কাজটি ঘটে খুব কম — ৮, ১৬, ৩২, ৬৪… চাবিতে একবার করে। n বার insert-এ মোট সরানো হয় n-এর দ্বিগুণেরও কম। ভাগ করে দিলে প্রতিটি insert-এর গড় খরচ ধ্রুব থাকে — একে বলে amortized O(1).

৭ · খরচের হিসাব — গড়ে O(1), সবচেয়ে খারাপে O(n)

এখন আমরা সৎভাবে খরচের হিসাব করতে পারি। Hash function ভালো আর load factor একটি সীমার নিচে থাকলে প্রতিটি শিকল গড়ে ছোট, তাই insert, lookup আর delete — তিনটিই average case-এ O(1). কিন্তু যদি কোনো কারণে সব চাবি একই ঘরে পড়ে? তখন একটি শিকলেই n টি node, আর খোঁজা আবার linear search — worst case O(n).

Hash function কতটা গুরুত্বপূর্ণ, তা নিজে মেপে দেখুন। নিচের প্রোগ্রাম ১,০০০টি চাবি (user0 থেকে user999) ১০১টি ঘরে বসায় — দুটি আলাদা hash দিয়ে। একটি “খেলনা” hash শুধু অক্ষরগুলো যোগ করে; অন্যটি djb2. দুটি ফাংশনই আমরা function pointer হিসেবে test-এ পাঠাচ্ছি (পর্ব ২৮):

#include <stdio.h>
#define NB 101                                  /* a prime number of buckets */
unsigned long toy(const char *s) { unsigned long h = 0; while (*s) h += (unsigned char)*s++; return h; }
unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    while (*s) h = h * 33 + (unsigned char)*s++;
    return h;
}
void test(const char *name, unsigned long (*f)(const char *)) {
    int count[NB] = {0}, used = 0, worst = 0;  char key[16];
    for (int i = 0; i < 1000; i++) {
        snprintf(key, sizeof key, "user%d", i);       /* user0 ... user999 */
        int b = (int)(f(key) % NB);
        if (count[b]++ == 0) used++;
        if (count[b] > worst) worst = count[b];
    }
    printf("%-4s: %3d of %d buckets used, longest chain = %d\n", name, used, NB, worst);
}
int main(void) { test("toy", toy); test("djb2", djb2); return 0; }

Hash table বনাম BST — কখন কোনটি

পর্ব ৩৫-এর BST-ও চাবি দিয়ে খোঁজে। তাহলে সবসময় hash table নয় কেন? কারণ hash table ইচ্ছে করেই চাবিগুলোর ক্রম ভেঙে দেয় — “Dhaka” আর “Dhakb” দুই প্রান্তে যায়। ফলে কিছু প্রশ্নের উত্তর সে দিতে পারে না:

৮ · Hash flooding — যখন collision নিজেই অস্ত্র

অংশ ৭-এর worst case-কে আমরা “দুর্ভাগ্য” ভেবেছিলাম। কিন্তু যদি কেউ ইচ্ছে করে দুর্ভাগ্য তৈরি করে? djb2-এর মতো hash-এর সূত্র সবাই জানে। তাই একজন আক্রমণকারী আগে থেকেই হিসাব করে হাজার হাজার এমন চাবি বানাতে পারেন, যেগুলো সবই একই ঘরে পড়বে।

একটি ওয়েব সার্ভারের কথা ভাবুন। কোনো ফর্ম জমা দিলে সার্ভার সাধারণত সব ফিল্ডের নাম আর মান একটি hash table-এ রাখে। আক্রমণকারী একটি অনুরোধে এক লাখ ফিল্ড পাঠালেন, যাদের সবার নাম একই ঘরে পড়ে। প্রতিটি নতুন ফিল্ড রাখার আগে সার্ভার পুরো শিকল ঘেঁটে দেখে নামটি আগে আছে কি না — প্রথমটিতে ১টি তুলনা, দ্বিতীয়টিতে ২টি… মোট প্রায় ৫০০ কোটি তুলনা, একটিমাত্র অনুরোধে। কয়েকটি এমন অনুরোধেই সার্ভারের CPU পুরো ব্যস্ত, সাধারণ গ্রাহকেরা আর সাড়া পান না। এটি একধরনের denial-of-service আক্রমণ, যার নাম hash flooding.

প্রতিরক্ষা — গোপন চাবিওয়ালা hash

সমস্যার মূল হলো, hash-এর হিসাব সবাই আগে থেকে করতে পারে। সমাধান: প্রোগ্রাম চালু হওয়ার সময় একটি এলোমেলো গোপন সংখ্যা (key/seed) বেছে নিন, আর hash-এর হিসাবে সেটি মিশিয়ে দিন। একই প্রোগ্রাম চলাকালীন hash নির্দিষ্ট থাকে (deterministic শর্ত ঠিক থাকে), কিন্তু বাইরের কেউ গোপন সংখ্যাটি না জানলে কোন চাবি কোন ঘরে যাবে আগে বলতে পারেন না।

শুধু একটি seed যোগ করাই যথেষ্ট নয় — কিছু দুর্বল hash-এ seed থাকা সত্ত্বেও collision বানানো যায়। এজন্য ২০১২ সালে Jean-Philippe Aumasson ও Daniel J. Bernstein (সেই djb2-এর স্রষ্টাই!) তৈরি করেন SipHash — ছোট চাবির জন্য দ্রুত, আর গোপন key ছাড়া এর ফল আন্দাজ করা কার্যত অসম্ভব হিসেবে নকশা করা। Python, Rust সহ বেশ কয়েকটি ভাষা তাদের ডিফল্ট hash table-এ SipHash বা এর কাছাকাছি কোনো keyed hash ব্যবহার করে। Java অন্য পথ নিয়েছে: HashMap-এ কোনো শিকল খুব লম্বা হলে সেটিকে একটি ভারসাম্যপূর্ণ tree-তে বদলে দেয়, ফলে সবচেয়ে খারাপ ক্ষেত্রেও খোঁজা O(log n).

৯ · বাস্তবে hash table — আপনি প্রতিদিন যা ব্যবহার করেন

Hash table সম্ভবত সফটওয়্যারের সবচেয়ে বেশি ব্যবহৃত ডেটা স্ট্রাকচার। কয়েকটি জায়গা যেখানে এটি চুপচাপ কাজ করছে:

একটি চেনা সমস্যা — ফোনবুকে ডুপ্লিকেট নম্বর

আপনার ফোনে ৫,০০০ কন্টাক্ট, অনেক নম্বর দুবার-তিনবার সেভ করা। কোনগুলো ডুপ্লিকেট? সহজ উপায়ে প্রতিটি নম্বরকে বাকি সবার সাথে মেলালে লাগে প্রায় ১.২৫ কোটি তুলনা (O(n²))। Hash table দিয়ে: প্রতিটি নম্বর একবার পড়ুন, টেবিলে আছে কি না দেখুন — থাকলে ডুপ্লিকেট, না থাকলে রেখে দিন। মোট মাত্র ৫,০০০ বার রাখা-খোঁজা, O(n). এই কাজটির নাম deduplication. Cloud storage-গুলোও এভাবে একই ফাইলের দুটি কপি চিনে ফেলে জায়গা বাঁচায় — সেখানে চাবি হলো ফাইলের ভেতরের ডেটার hash.

এই মডিউলে আমরা কাঠামোগুলো C-তে নিজ হাতে, মেমরির চোখ দিয়ে বানাচ্ছি। Cuckoo hashing, Robin Hood hashing বা consistent hashing-এর মতো উন্নত কৌশল আর তাদের গাণিতিক বিশ্লেষণ গভীরভাবে পাবেন ডেটা স্ট্রাকচার ও অ্যালগরিদম কোর্সে।

১০ · AI-এর যুগে hash table — যা যাচাই করবেন

“C-তে একটি hash table লিখে দাও” — AI এটি কয়েক সেকেন্ডে লিখবে, আর প্রথম দেখায় কোড পরিষ্কারও লাগবে। সমস্যা হলো, hash table-এর বাগগুলো ছোট পরীক্ষায় ধরা পড়ে না। দশটি চাবি দিয়ে পরীক্ষা করলে সব ঠিক; দশ লাখ চাবিতে বা বাইরের ইনপুটে গিয়ে সমস্যা দেখা দেয়।

AI-এর লেখা hash table-এ সাধারণ ভুল

AI-এর দেওয়া hash table হাতে পেলে — যাচাইয়ের চেকলিস্ট

• String চাবি strcmp দিয়ে তুলনা হচ্ছে, == দিয়ে নয়
• Hash-এর টাইপ unsigned, আর %-এর ফল সবসময় 0 থেকে bucket সংখ্যা − 1-এর মধ্যে
• Load factor গোনা হচ্ছে এবং একটি সীমা পেরোলে resize হচ্ছে — resize-এর পর পুরোনো সব চাবি আবার খুঁজে পাওয়া যাচ্ছে
• Valgrind বা -fsanitize=address দিয়ে চালিয়ে শূন্য leak দেখেছি — শুধু array নয়, প্রতিটি node ও চাবি free হচ্ছে
• নেই এমন চাবি, খালি string, আর একই চাবি দুবার — তিনটিই পরীক্ষা করেছি
• চাবি বাইরে থেকে এলে (নেটওয়ার্ক, ফাইল) seed বা keyed hash ব্যবহার করা হচ্ছে