Hash table — hash function, collision আর load factor

১ · রোল নম্বরের খাতা থেকে hash table — direct-address table আর তার সীমা

একটি স্কুলের ক্লাস টিচারের কথা ভাবুন। ক্লাসে ৬০ জন ছাত্রছাত্রী, রোল নম্বর 1 থেকে 60. তিনি একটি খাতায় ৬০টি পাতা রেখেছেন, আর রোল 37-এর সব তথ্য আছে ঠিক ৩৭ নম্বর পাতায়। কারও খবর জানতে খাতা উল্টে খুঁজতে হয় না — সরাসরি সেই পাতা খোলেন। নতুন তথ্য লেখা, পড়া বা মুছে ফেলা — সবকিছু এক ধাপে।

প্রোগ্রামের ভাষায় এটি একটি direct-address table: key-ই অ্যারের index. a[roll] পড়া O(1), কারণ পর্ব ১০-এ দেখেছেন, অ্যারের যেকোনো ঘরে সরাসরি যাওয়া যায় (random access বলে)। আমরা আসলে যে dictionary ADT চাই, তার তিনটি কাজ — insert(key, value), find(key), delete(key) — এখানে তিনটিই Θ(1).

সমস্যা শুরু হয় যখন key-গুলো আর ছোট পরিসরে থাকে না। একটি মুদি দোকান তার bKash গ্রাহকদের মোবাইল নম্বর দিয়ে বাকির হিসাব রাখতে চায়। নম্বর ১১ অঙ্কের, তাই সম্ভাব্য key প্রায় 10¹¹ টি। প্রতিটি ঘরে ৮ byte রাখলেও অ্যারের আকার হবে 8 × 10¹¹ byte ≈ ৮০০ GB — অথচ দোকানের গ্রাহক হয়তো ৫০০ জন! আর key যদি নাম বা email হয়, সম্ভাব্য key-এর জগৎ (universe, U) কার্যত অসীম। Direct-address table তখন অচল।

এটিই hash table-এর মূল ধারণা। m টি ঘরের (bucket বা slot) একটি অ্যারে নিন, যেখানে m মোটামুটি আসল key-এর সংখ্যা n-এর কাছাকাছি। আর একটি hash function h নিন, যা প্রতিটি key-কে 0 থেকে m − 1-এর একটি সংখ্যায় পাঠায়: h : U → {0, 1, …, m − 1}. key k রাখা হবে ঘর h(k)-এ। জায়গা লাগে Θ(n + m), U-এর আকারের ওপর আর নির্ভর করে না।

শেষ সারির দুটি শব্দই এই পর্বের পুরো গল্প: “গড়ে” আর “worst case”. কেন গড়ে O(1), কোন অনুমানের ওপর সেই গড় দাঁড়িয়ে, আর কেউ যদি ইচ্ছা করে worst case বানাতে চায় তখন কী হয় — একে একে দেখব।

২ · Hash function — key থেকে ঘরের নম্বর বানানো

প্রথমে ধরে নিই key একটি অঋণাত্মক পূর্ণসংখ্যা (নাম বা string-কে আগে সংখ্যায় বদলাতে হয়, নিচে দেখবেন)। সংখ্যাকে 0 থেকে m − 1-এ নামানোর দুটি ক্লাসিক উপায় আছে।

Division method — h(k) = k mod m

Division method-এ hash হলো ভাগশেষ: h(k) = k mod m (modulo অপারেশন)। একটি ভাগ, তাই খুব দ্রুত। কিন্তু m বাছাই করতে হয় সাবধানে। m যদি 2-এর ঘাত হয়, যেমন m = 16, তাহলে k mod 16 মানে শুধু k-এর শেষ ৪টি bit — বাকি সব bit উপেক্ষিত। বাস্তবের key প্রায়ই নিয়ম মেনে চলে: মেমরির ঠিকানা সাধারণত 8-এর গুণিতক, অনেক আইডি 10 বা 100-এর গুণিতক। দেখুন key 8, 16, 24, 32, 40-এ কী হয়:

সাধারণ নিয়ম: key-গুলোর মধ্যে যদি m-এর সাথে একটি সাধারণ উৎপাদক g থাকে, তাহলে তারা মাত্র m/g টি ঘর ব্যবহার করতে পারে। তাই division method-এ m হিসেবে একটি মৌলিক সংখ্যা নিন, যা 2-এর কোনো ঘাতের খুব কাছে নয়। C++-এর GCC লাইব্রেরি ঠিক এ কারণেই bucket-সংখ্যা হিসেবে মৌলিক সংখ্যার একটি তালিকা ব্যবহার করে।

Multiplication method — Knuth-এর সোনালি ধ্রুবক

Multiplication method-এ 0 আর 1-এর মাঝের একটি ধ্রুবক A নিয়ে h(k) = ⌊m · (k·A mod 1)⌋, যেখানে “mod 1” মানে ভগ্নাংশ অংশটুকু। এখানে m-এর মান নিয়ে চিন্তা কম — 2-এর ঘাত হলেও চলে, কারণ ভগ্নাংশ অংশে k-এর সব অঙ্কের প্রভাব থাকে। Donald Knuth তাঁর The Art of Computer Programming-এ A ≈ (√5 − 1)/2 ≈ 0.6180339887 নেওয়ার পরামর্শ দেন — সোনালি অনুপাতের (golden ratio) উল্টো। m = 16 নিয়ে পরপর চারটি key:

পাশাপাশি key-গুলো টেবিলের দূরে দূরে ছড়িয়ে গেল। বাস্তবে এটি পূর্ণসংখ্যায় করা হয়: 32-bit key-কে 2654435769 (= ⌊2³²/φ⌋, hex-এ 0x9E3779B9) দিয়ে গুণ করে overflow হতে দিন, তারপর ওপরের p টি bit নিন — m = 2^p. একে প্রায়ই Fibonacci hashing বলে। পর্ব ১৫-এর splitmix64 hash-এর প্রথম ধ্রুবক 0x9e3779b97f4a7c15-ও একই সংখ্যার 64-bit রূপ।

String-এর hash — polynomial hash

নাম, শব্দ বা URL-কে আগে একটি সংখ্যায় বদলাতে হয়। সবচেয়ে সরল ভাবনা — অক্ষরগুলোর ASCII মান যোগ করা — খুব খারাপ: "ab" আর "ba" দুটোরই যোগফল 97 + 98 = 195, অর্থাৎ সব anagram একই ঘরে। অক্ষরের অবস্থানও hash-এ ঢোকাতে হবে। পর্ব ১১-এর polynomial hash ঠিক তা-ই করে: string s = s₀s₁…s_L−1-কে একটি base p-এর সংখ্যার অঙ্ক হিসেবে পড়ুন:

Horner-এর নিয়মে একটি লুপেই হয়: শুরুতে h = 0, প্রতিটি অক্ষর c-এর জন্য h = (h·p + c) mod M. Java-র String.hashCode() ঠিক এটি, p = 31 আর M = 2³² (int overflow). তখন "ab" = 97·31 + 98 = 3105, কিন্তু "ba" = 98·31 + 97 = 3135 — আলাদা। এই hash-এর একটি বিশেষ ক্ষমতা আছে: একটি জানালা এক অক্ষর সরালে নতুন hash পুরোনোটি থেকে O(1)-এ বের করা যায় — rolling hash, যা দিয়ে পর্ব ৫৮-এ Rabin-Karp string matching হবে। খেয়াল রাখুন, L দৈর্ঘ্যের string-এর hash বের করতেই Θ(L) সময় লাগে — তাই string key-তে “O(1)” আসলে “O(L)”.

ভালো hash function-এর গুণ

• নির্ধারিত (deterministic): একই key-এর জন্য প্রোগ্রাম চলার পুরো সময় একই মান। নইলে রাখা জিনিস আর খুঁজে পাওয়া যাবে না।
• সমতার সাথে সামঞ্জস্য: a == b হলে h(a) == h(b) হতেই হবে। এ কারণে Python-এ শুধু hashable (অপরিবর্তনীয়) মান dict-এর key হতে পারে — list বদলে গেলে তার hash-ও বদলে যেত।
• সমানভাবে ছড়ানো (uniform): বাস্তবের key-গুলো ঘরগুলোতে প্রায় সমানভাবে ভাগ হবে, key-এর নিয়মিত প্যাটার্ন থাকলেও।
• key-এর প্রতিটি অংশ কাজে লাগানো: key-এর যেকোনো একটি bit বদলালে hash-এর প্রায় অর্ধেক bit বদলানো উচিত — একে বলে avalanche effect. শুধু প্রথম অক্ষর বা শেষ অঙ্ক দেখা hash এখানে ফেল করে।
• দ্রুত: প্রতিটি কাজে hash বের করতে হয়, তাই SHA-256-এর মতো cryptographic hash সাধারণত টেবিলের জন্য অনেক ধীর। তবে অংশ ৮-এ দেখবেন, শত্রু থাকলে কিছুটা গোপনীয়তাও লাগে।

৩ · Collision এড়ানো যায় না — pigeonhole আর birthday paradox

দুটি ভিন্ন key একই ঘরে পড়লে তাকে বলে collision. সবচেয়ে ভালো hash function দিয়েও কি এটি পুরোপুরি এড়ানো যায়? পর্ব ০৬-এর pigeonhole principle সাথে সাথে বলে দেয়: না। |U| > m হলে (আর বাস্তবে |U| বিশাল, m ছোট) অন্তত দুটি key-এর একই ঘর থাকবেই। কিন্তু আরও অবাক করা কথা হলো, key-এর সংখ্যা n যখন m-এর তুলনায় অনেক ছোট, তখনও collision প্রায় নিশ্চিত।

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

শেষ ভগ্নাংশটি 343/365, কারণ ২৩তম মানুষের জন্য বাকি থাকে 365 − 22 = 343 দিন। তাই অন্তত একটি মিলের সম্ভাবনা 1 − 0.4927 ≈ 0.5073 — ৫০%-এর একটু বেশি। কেন এত কম মানুষেই? কারণ মিল খোঁজা হচ্ছে যেকোনো দুজনের মধ্যে, আর ২৩ জনে জোড়া আছে 23·22/2 = 253 টি। প্রতিটি জোড়ার মিলের সম্ভাবনা 1/365, তাই মোটামুটি হিসাব P(কোনো মিল নেই) ≈ e^−253/365 = e^−0.693 ≈ 0.50 (এখানে 1 − x ≈ e^−x ব্যবহার করেছি)। সাধারণভাবে n টি key আর m টি ঘরে

অর্থাৎ ঘর যত বেশি হোক, collision শুরু হয় ঘরের সংখ্যার বর্গমূলের কাছাকাছি key-তেই। নিচের প্রোগ্রাম ঠিক হিসাব আর এই আনুমানিক সূত্র পাশাপাশি দেখায়, আর তিনটি টেবিল-আকারের জন্য ৫০%-এর সীমা বের করে।

#include <cmath>
#include <cstdio>
#include <initializer_list>
int main() {
    const double m = 365;                               // 365 "buckets" = days of the year
    std::printf(" n   exact    1-exp(-n(n-1)/2m)\n");
    for (int n : {5, 10, 20, 23, 30, 40, 50, 57, 70}) {
        double q = 1;                                   // q = P(all n keys land in different buckets)
        for (int i = 0; i < n; ++i) q *= (m - i) / m;
        std::printf("%2d   %.4f   %.4f\n", n, 1 - q, 1 - std::exp(-n * (n - 1) / (2 * m)));
    }
    for (double M : {365.0, 1e6, 4294967296.0}) {      // smallest n with P(collision) >= 1/2
        double q = 1;
        int n = 0;
        while (1 - q < 0.5) { q *= (M - n) / M; ++n; }
        std::printf("m = %.0f: n = %d   sqrt(2 m ln 2) = %.1f\n", M, n, std::sqrt(2 * M * std::log(2.0)));
    }
}

 n   exact    1-exp(-n(n-1)/2m)
 5   0.0271   0.0270
10   0.1169   0.1160
20   0.4114   0.4058
23   0.5073   0.5000
30   0.7063   0.6963
40   0.8912   0.8820
50   0.9704   0.9651
57   0.9901   0.9874
70   0.9992   0.9987
m = 365: n = 23   sqrt(2 m ln 2) = 22.5
m = 1000000: n = 1178   sqrt(2 m ln 2) = 1177.4
m = 4294967296: n = 77164   sqrt(2 m ln 2) = 77162.7

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

প্রথম সমাধানটি চিঠির খোপের মতোই সরল: প্রতিটি ঘরে একটি linked list (পর্ব ১২) রাখুন, আর ঘর h(k)-এ যতগুলো key পড়ে সবাইকে সেই তালিকায় রাখুন। একে বলে separate chaining. Insert মানে তালিকার মাথায় যোগ করা (key আগে থেকে আছে কি না, map-এ সেটি আগে দেখতে হয়), find মানে সেই এক তালিকা ধরে হাঁটা, delete মানে তালিকা থেকে node সরানো। নিচে m = 7, h(k) = k mod 7:

বিশ্লেষণ — কেন গড়ে O(1 + α)

Worst case সহজ: সব n টি key এক bucket-এ পড়লে hash table একটি লম্বা linked list, আর find Θ(n). গড় হিসাবের জন্য একটি অনুমান লাগে — simple uniform hashing: প্রতিটি key স্বাধীনভাবে m টি bucket-এর যেকোনোটিতে সমান সম্ভাবনায় (1/m) পড়ে। এখন load factor α = n/m সংজ্ঞায়িত করুন — প্রতি bucket-এ গড় key-এর সংখ্যা।

• ব্যর্থ খোঁজা (key নেই): k-এর bucket-এর পুরো তালিকা দেখতে হয়। n টি key-এর প্রত্যেকটি সেই নির্দিষ্ট bucket-এ পড়ে 1/m সম্ভাবনায়, তাই expected value-এর linearity অনুযায়ী তালিকার প্রত্যাশিত দৈর্ঘ্য n · (1/m) = α. hash বের করার এক ধাপসহ মোট খরচ Θ(1 + α).
• সফল খোঁজা (key আছে): key x খুঁজতে x-এর আগে তালিকায় থাকা key-গুলো দেখতে হয় — অর্থাৎ x-এর পরে insert হওয়া আর একই bucket-এ পড়া key-গুলো (মাথায় বসানো হয় বলে)। i-তম insert হওয়া key-এর পরে আসে n − i টি key, প্রত্যেকটি 1/m সম্ভাবনায় একই bucket-এ। সব i-এর গড় নিলে দেখা key-এর প্রত্যাশিত সংখ্যা 1 + (1/n) Σ_i=1ⁿ (n − i)/m = 1 + (n − 1)/(2m) ≈ 1 + α/2. এটিও Θ(1 + α).

তাই যদি bucket-এর সংখ্যা m সবসময় n-এর সমানুপাতিক রাখা যায় (m = Θ(n), অর্থাৎ α একটি ধ্রুবক), তাহলে প্রতিটি কাজ গড়ে O(1). Insert (মাথায় বসানো) আর delete (doubly linked list হলে, node হাতে থাকলে) O(1); key আছে কি না আগে দেখতে হলে খোঁজার খরচ যোগ হয়। জায়গা Θ(n + m). লক্ষ করুন, এই “গড়” একটি অনুমানের ওপর দাঁড়িয়ে — key-গুলো যেন এলোমেলোভাবে bucket-এ ছড়ায়। কিন্তু h নির্দিষ্ট হলে আসলে কোথাও কোনো এলোমেলোতা নেই: একই key-গুলো বারবার দিলে খরচ হুবহু একই থাকে, আর কেউ ইচ্ছা করে খারাপ key বাছলে এই গড়ের হিসাব খাটে না। এই সূক্ষ্ম পার্থক্যই অংশ ৮-এর আক্রমণের দরজা।

Chaining-এর সুবিধা-অসুবিধা. খুব সরল, delete সহজ, α 1-এর বেশি হলেও চলে (শুধু ধীর হয়), আর খারাপ hash-এও ধীরে ধীরে খারাপ হয়, হঠাৎ ভেঙে পড়ে না। কিন্তু প্রতিটি key-এর জন্য একটি আলাদা node আর pointer — বাড়তি মেমরি, আর node-গুলো মেমরিতে ছড়ানো বলে তালিকা ধরে হাঁটা cache-এর জন্য খারাপ (পর্ব ১২-এ linked list-এর এই দুর্বলতা দেখেছেন)।

৫ · Open addressing — টেবিলের ভেতরেই জায়গা খোঁজা

দ্বিতীয় সমাধানে কোনো তালিকা নেই: প্রতিটি ঘরে সর্বোচ্চ একটি key, সবকিছু অ্যারের ভেতরেই। নিজের ঘর ভরা থাকলে একটি নির্দিষ্ট নিয়মে পরের ঘর, তার পরের ঘর দেখুন, যতক্ষণ খালি ঘর না মেলে। একে বলে open addressing. সিনেমা হলে নিজের আসনে কেউ বসে থাকলে আপনি পাশের খালি আসনে বসেন, আর আপনাকে খুঁজতে আসা বন্ধুও একই নিয়মে এগোবে।

প্রতিটি key k-এর জন্য ঘরের একটি ক্রম থাকে — probe sequence h(k, 0), h(k, 1), h(k, 2), … — যা 0 থেকে m − 1-এর সব ঘরকে কোনো এক ক্রমে ছুঁয়ে যায়। Insert সেই ক্রমে প্রথম খালি ঘরে বসায়; find একই ক্রমে এগোয়, key পেলে থামে, আর একটি খালি ঘর পেলে বলে “নেই” — কারণ key থাকলে insert-এর সময় এই খালি ঘরেই বসত। যেহেতু প্রতিটি ঘরে একটিই key, এখানে সবসময় n ≤ m, অর্থাৎ α ≤ 1.

Linear probing আর primary clustering

সবচেয়ে সরল নিয়ম linear probing: h(k, i) = (h(k) + i) mod m — নিজের ঘর, তারপর ঠিক পরেরটি, তারপর তার পরেরটি, শেষে পৌঁছালে আবার শুরু থেকে। নিচে m = 11, h(k) = k mod 11:

এই ঘটনার নাম primary clustering: ভরা ঘরগুলো লম্বা একটানা দল বাঁধে, আর একটি দল যত লম্বা, নতুন key তাতে পড়ার সম্ভাবনা তত বেশি (দৈর্ঘ্য L-এর cluster-এ পড়ার সম্ভাবনা প্রায় (L + 1)/m) — “ধনী আরও ধনী হয়”. ঢাকার রাস্তার জ্যামের মতো: একটি মোড়ে গাড়ি আটকালে পেছনের গাড়ি জমে, আর জমা লাইন পাশের মোড়ের লাইনের সাথে মিশে আরও লম্বা হয়।

১৯৬০-এর দশকের শুরুতে Donald Knuth linear probing-এর গড় খরচ ঠিকঠাক বের করেন (একটি ভালো, এলোমেলো hash ধরে নিয়ে, আর বড় m-এর জন্য): সফল খোঁজায় প্রায় ½(1 + 1/(1 − α)) probe, ব্যর্থ খোঁজা বা insert-এ প্রায় ½(1 + 1/(1 − α)²). তুলনার জন্য, যদি প্রতিটি key-এর probe sequence সম্পূর্ণ এলোমেলো একটি ক্রম হতো (uniform hashing), তাহলে ব্যর্থ খোঁজায় সর্বোচ্চ 1/(1 − α) probe লাগত — কারণ প্রথম probe ভরা ঘরে পড়ে α সম্ভাবনায়, প্রথম দুটিই ভরা ঘরে পড়ে বড়জোর α² সম্ভাবনায়, এভাবে প্রত্যাশিত probe ≤ 1 + α + α² + … = 1/(1 − α), পর্ব ০৬-এর geometric series অনুযায়ী।

টেবিলের শিক্ষা পরিষ্কার: α ছোট থাকলে linear probing চমৎকার, কিন্তু α 1-এর কাছে গেলে ব্যর্থ খোঁজার খরচ বিস্ফোরিত হয় — 0.9-এ গড়ে ৫০টিরও বেশি probe. তাই open addressing-এ α সাধারণত 0.5 থেকে 0.75-এর মধ্যে রাখা হয়। তবু বাস্তবে linear probing প্রায়ই সবচেয়ে দ্রুত, কারণ পাশাপাশি ঘর দেখা মানে একই cache line — পর্ব ১০-এর spatial locality.

Quadratic probing আর double hashing

Cluster ভাঙতে probe-এর লাফ বদলানো যায়। Quadratic probing-এ h(k, i) = (h(k) + i²) mod m — লাফ 1, 4, 9, 16, … ক্রমে বাড়ে, তাই পাশাপাশি cluster জমে না। কিন্তু সব probe-এর ক্রম আর সব ঘর ছোঁয় না; প্রমাণ করা যায় m মৌলিক হলে প্রথম ⌈m/2⌉ টি probe আলাদা ঘরে পড়ে, তাই α ≤ ½ রাখলে insert সবসময় খালি ঘর পায়। আরেকটি দুর্বলতা থেকে যায়: একই home-এর দুটি key হুবহু একই ক্রমে হাঁটে — একে বলে secondary clustering.

Double hashing এটিও সারায়: দ্বিতীয় একটি hash function h₂ লাফের দৈর্ঘ্য ঠিক করে — h(k, i) = (h₁(k) + i · h₂(k)) mod m. দুটি শর্ত: h₂(k) কখনো 0 হবে না (নইলে একই ঘরে ঘুরপাক), আর h₂(k) ও m-এর গসাগু 1 হবে, যাতে সব ঘর ছোঁয়া যায় — m মৌলিক নিলে দ্বিতীয়টি আপনাআপনি সত্য। একটি প্রচলিত পছন্দ h₁(k) = k mod m, h₂(k) = 1 + (k mod (m − 1)). m = 11-এ home slot 1-এর দুটি key-এর প্রথম পাঁচটি probe দেখুন:

Double hashing-এ প্রতিটি key-এর নিজস্ব পথ, তাই এর আচরণ uniform hashing-এর খুব কাছাকাছি — বিশ্লেষণে প্রায় 1/(1 − α). বিনিময়ে লাফগুলো দূরে দূরে, তাই cache-এর সুবিধা কম। বাস্তবের লাইব্রেরি এই দুইয়ের মধ্যে আপস করে, যেমন Python-এর dict (অংশ ৯)।

৬ · Delete-এর ফাঁদ — tombstone

Chaining-এ delete সহজ — তালিকা থেকে node সরিয়ে দিন। Open addressing-এ ভাবুন: আগের ডায়াগ্রামের টেবিল থেকে 23 মুছতে ঘরটি খালি করে দিলেন। এখন 34 খুঁজুন: home slot 1-এ 12, slot 2 খালি — “খালি ঘর মানে key নেই” নিয়মে খোঁজা থামবে, অথচ 34 বসে আছে slot 4-এ! খালি ঘরটি probe sequence-এর শিকল ভেঙে দিয়েছে. সমাধান হলো মোছা ঘরে একটি বিশেষ চিহ্ন রাখা — tombstone (কবরের ফলক), নিচে #: “এখানে কেউ ছিল”. খোঁজার সময় tombstone পার হয়ে যেতে হয়, আর insert-এর সময় সেই ঘর আবার ব্যবহার করা যায়।

Tombstone-এর একটি দাম আছে: এগুলো key নয়, কিন্তু খোঁজার পথ লম্বা করে। অনেক insert-delete-এর পর টেবিল tombstone-এ ভরে গেলে খালি ঘর প্রায় থাকে না, আর ব্যর্থ খোঁজা পুরো টেবিল ঘুরে আসে। তাই বাস্তবায়নে “ভরা” গোনার সময় key আর tombstone দুটোই গোনা হয়, আর সীমা ছাড়ালে rehash করে (অংশ ৭) সব tombstone একসাথে মুছে ফেলা হয়। Linear probing-এ আরেকটি উপায়ও আছে — delete-এর পর পেছনের key-গুলোকে সরিয়ে ফাঁক ভরাট করা (backward-shift deletion), যাতে tombstone-ই লাগে না।

এবার পুরো কৌশলটি কোডে: linear probing, tombstone-সহ delete, আর প্রতিটি কাজের পর টেবিল ছাপা। . খালি, # tombstone.

#include <bits/stdc++.h>
#include <initializer_list>
using namespace std;
const int M = 11, EMPTY = -1, TOMB = -2;      // keys are >= 0; TOMB marks a deleted slot
vector<int> t(M, EMPTY);
void show(const string& what) {
    cout << what << "\n   [";
    for (int i = 0; i < M; ++i) cout << (i ? " " : "") << (t[i] == EMPTY ? "." : t[i] == TOMB ? "#" : to_string(t[i]));
    cout << "]\n";
}
pair<int, int> locate(int k) {                // -> {slot or -1, number of probes}
    for (int p = 1, s = k % M; p <= M; ++p, s = (s + 1) % M) {
        if (t[s] == EMPTY) return {-1, p};    // a truly empty slot ends the search
        if (t[s] == k) return {s, p};         // tombstones are simply skipped
    }
    return {-1, M};
}
void insert(int k) {                          // assumes the table never becomes full
    if (locate(k).first >= 0) return show("insert " + to_string(k) + ": already present");
    int s = k % M; while (t[s] >= 0) s = (s + 1) % M;   // first empty OR tombstone slot
    t[s] = k; show("insert " + to_string(k) + " -> slot " + to_string(s));
}
void erase(int k) {
    int s = locate(k).first;
    if (s >= 0) t[s] = TOMB;                  // mark, never empty: later keys stay reachable
    show("erase " + to_string(k) + " -> " + (s >= 0 ? "tombstone at slot " + to_string(s) : string("not found")));
}
void lookup(int k) {
    auto [s, p] = locate(k);
    cout << "find " << k << ": " << (s >= 0 ? "slot " + to_string(s) : string("absent")) << " after " << p << " probes\n";
}
int main() {
    for (int k : {22, 33, 44, 5, 16, 27}) insert(k);
    erase(33); lookup(44); lookup(66); insert(66); erase(5); lookup(27);
}

insert 22 -> slot 0
   [22 . . . . . . . . . .]
insert 33 -> slot 1
   [22 33 . . . . . . . . .]
insert 44 -> slot 2
   [22 33 44 . . . . . . . .]
insert 5 -> slot 5
   [22 33 44 . . 5 . . . . .]
insert 16 -> slot 6
   [22 33 44 . . 5 16 . . . .]
insert 27 -> slot 7
   [22 33 44 . . 5 16 27 . . .]
erase 33 -> tombstone at slot 1
   [22 # 44 . . 5 16 27 . . .]
find 44: slot 2 after 3 probes
find 66: absent after 4 probes
insert 66 -> slot 1
   [22 66 44 . . 5 16 27 . . .]
erase 5 -> tombstone at slot 5
   [22 66 44 . . # 16 27 . . .]
find 27: slot 7 after 3 probes

M = 11
EMPTY, TOMB = None, "#"                 # TOMB marks a deleted slot
t = [EMPTY] * M
def show(what):
    print(what)
    print("   [" + " ".join("." if x is EMPTY else str(x) for x in t) + "]")
def locate(k):                          # -> (slot or -1, number of probes)
    s = k % M
    for p in range(1, M + 1):
        if t[s] is EMPTY: return -1, p  # a truly empty slot ends the search
        if t[s] == k: return s, p       # tombstones are simply skipped
        s = (s + 1) % M
    return -1, M
def insert(k):                          # assumes the table never becomes full
    if locate(k)[0] >= 0: return show(f"insert {k}: already present")
    s = k % M
    while t[s] is not EMPTY and t[s] != TOMB:
        s = (s + 1) % M                 # stop at the first empty OR tombstone slot
    t[s] = k
    show(f"insert {k} -> slot {s}")
def erase(k):
    s = locate(k)[0]
    if s >= 0: t[s] = TOMB              # mark, never empty: later keys stay reachable
    show(f"erase {k} -> " + (f"tombstone at slot {s}" if s >= 0 else "not found"))
def lookup(k):
    s, p = locate(k)
    print(f"find {k}: " + (f"slot {s}" if s >= 0 else "absent") + f" after {p} probes")
for k in [22, 33, 44, 5, 16, 27]: insert(k)
erase(33); lookup(44); lookup(66); insert(66); erase(5); lookup(27)

insert 22 -> slot 0
   [22 . . . . . . . . . .]
insert 33 -> slot 1
   [22 33 . . . . . . . . .]
insert 44 -> slot 2
   [22 33 44 . . . . . . . .]
insert 5 -> slot 5
   [22 33 44 . . 5 . . . . .]
insert 16 -> slot 6
   [22 33 44 . . 5 16 . . . .]
insert 27 -> slot 7
   [22 33 44 . . 5 16 27 . . .]
erase 33 -> tombstone at slot 1
   [22 # 44 . . 5 16 27 . . .]
find 44: slot 2 after 3 probes
find 66: absent after 4 probes
insert 66 -> slot 1
   [22 66 44 . . 5 16 27 . . .]
erase 5 -> tombstone at slot 5
   [22 66 44 . . # 16 27 . . .]
find 27: slot 7 after 3 probes

নিজে চালিয়ে দেখুন — chaining বনাম linear probing

নিচের টুলে “চালিয়ে দেখুন” চাপুন। একই key দুটি টেবিলে একসাথে ঢোকে, দুটিরই m = 11 আর h(k) = k mod 11. বাঁয়ে chaining-এর তালিকা (নতুন key মাথায়, লাল), ডানে linear probing-এর slot (এই insert-এ যে slot-গুলো দেখা হলো সেগুলো লাল)। শুরুতে কোড নিজে নয়টি key দেয় — প্রথম ছয়টি ওপরের প্রোগ্রামের মতোই। এরপর নিজে key দিন, বা “এলোমেলো ৭টি” চাপুন আর দেখুন cluster কত দ্রুত লম্বা হয়।

const M = 11;                                   // both tables: m = 11, h(k) = k mod 11
const ch = Array.from({ length: M }, () => []); // separate chaining: one list per bucket
const lp = new Array(M).fill(null);             // linear probing: one key per slot
let path = [], hotB = -1;
const $ = id => document.getElementById(id);
const h = k => ((k % M) + M) % M;
function longestCluster() {                     // longest run of occupied slots (wraps around)
  let best = 0, run = 0;
  for (let i = 0; i < 2 * M; i++) { run = lp[i % M] === null ? 0 : run + 1; best = Math.max(best, Math.min(run, M)); }
  return best;
}
function draw(msg) {
  $("ch").innerHTML = ch.map((b, i) => `<div class="r"><b>${i}</b>` +
    b.map((k, j) => `<span class="${i === hotB && j === 0 ? "hl" : ""}">${k}</span>`).join("") + "</div>").join("");
  $("lp").innerHTML = lp.map((k, i) => `<div class="c${path.includes(i) ? " hl" : ""}"><small>${i}</small>${k ?? "·"}</div>`).join("");
  $("msg").textContent = msg; console.log(msg);
}
function insert(k) {
  if (!Number.isInteger(k)) return draw("please type a whole number");
  if (lp.includes(k)) return draw(`${k} is already in both tables`);
  if (!lp.includes(null)) return draw("probing table is full: it must grow (rehash) first");
  const b = h(k); ch[b].unshift(k); hotB = b;   // chaining: put the key at the head of its chain
  let s = b; path = [s];
  while (lp[s] !== null) { s = (s + 1) % M; path.push(s); }
  lp[s] = k;
  draw(`insert ${k}: h=${b} | chain[${b}] length ${ch[b].length} | probing: slot ${s}, ${path.length} probes, longest cluster ${longestCluster()}`);
}
function clearAll() { ch.forEach(b => (b.length = 0)); lp.fill(null); path = []; hotB = -1; }
$("bi").onclick = () => insert(Number($("hk").value));
$("br").onclick = () => { clearAll(); for (let i = 0; i < 7; i++) { let k; do k = Math.floor(Math.random() * 100); while (lp.includes(k)); insert(k); } };
$("bz").onclick = () => { clearAll(); draw("empty tables"); };
for (const k of [22, 33, 44, 5, 16, 27, 3, 4, 55]) insert(k);

insert 22: h=0 | chain[0] length 1 | probing: slot 0, 1 probes, longest cluster 1
insert 33: h=0 | chain[0] length 2 | probing: slot 1, 2 probes, longest cluster 2
insert 44: h=0 | chain[0] length 3 | probing: slot 2, 3 probes, longest cluster 3
insert 5: h=5 | chain[5] length 1 | probing: slot 5, 1 probes, longest cluster 3
insert 16: h=5 | chain[5] length 2 | probing: slot 6, 2 probes, longest cluster 3
insert 27: h=5 | chain[5] length 3 | probing: slot 7, 3 probes, longest cluster 3
insert 3: h=3 | chain[3] length 1 | probing: slot 3, 1 probes, longest cluster 4
insert 4: h=4 | chain[4] length 1 | probing: slot 4, 1 probes, longest cluster 8
insert 55: h=0 | chain[0] length 4 | probing: slot 8, 9 probes, longest cluster 9

৭ · Load factor আর rehashing — টেবিল বড় করার হিসাব

অংশ ৪ আর ৫-এর সব “গড়ে O(1)” দাঁড়িয়ে আছে একটি শর্তে: α ধ্রুবক থাকবে। কিন্তু key আসতেই থাকে, n বাড়ে, আর m স্থির থাকলে α = n/m-ও বাড়ে। সমাধান পর্ব ১০-এর dynamic array-এর মতোই: α একটি সীমা ছাড়ালে প্রায় দ্বিগুণ আকারের নতুন টেবিল বানান, আর পুরোনো সব key সেখানে আবার ঢোকান। একে বলে rehashing. শুধু কপি করলে হয় না — h(k) = k mod m-এ m বদলালে প্রায় প্রতিটি key-এর ঘরই বদলে যায়, তাই প্রতিটি key-কে আবার hash করতে হয়।

কেন তবু amortized O(1)

একটি rehash Θ(n) — তাহলে কি insert ধীর? না, কারণ rehash খুব কম ঘটে। ধরুন টেবিল প্রতিবার দ্বিগুণ হয়, আর শেষে n টি key আছে। শেষ rehash-এ সর্বোচ্চ n টি key সরেছে, তার আগেরটিতে n/2, তার আগে n/4… মোট সরানো সর্বোচ্চ n + n/2 + n/4 + … < 2n. সাথে n টি সাধারণ insert. তাই n টি insert-এর মোট খরচ O(n), অর্থাৎ প্রতি insert amortized O(1) — পর্ব ১০-এর vector-এর হুবহু একই যুক্তি, আর পর্ব ৬০-এ potential method দিয়ে এর আনুষ্ঠানিক প্রমাণ দেখবেন। শর্ত একটাই: আকার গুণ করে বাড়াতে হবে, যেমন ×2 বা ×1.5 হারে। প্রতিবার শুধু ১০টি ঘর যোগ করলে মোট খরচ Θ(n²/10) — O(n²).

• লাইব্রেরির সীমা: C++ unordered_map-এর max_load_factor() ডিফল্ট 1.0, Java HashMap-এর 0.75, আর CPython-এর dict ভরতে দেয় মোটামুটি 2/3 পর্যন্ত। Chaining-এ α 1 হলেও চলে; open addressing-এ সীমা কম রাখতে হয়।
• আগেই জায়গা নিন: কতগুলো key আসবে জানা থাকলে C++-এ m.reserve(n) বা Java-তে new HashMap<>(capacity) দিন — বারবার rehash এড়ায়। কনটেস্টে বড় unordered_map-এ এটি একটি সহজ গতিবৃদ্ধি।
• Latency-র দিক: amortized O(1) মানে গড়, প্রতিটি নয় — যে insert rehash ঘটায় সে একাই Θ(n). বিশাল টেবিলে এক মুহূর্তের এই থেমে যাওয়া কিছু সার্ভারে সমস্যা, তাই Redis-এর মতো সিস্টেম rehash একবারে না করে প্রতিটি কাজের সাথে অল্প অল্প করে — একে বলে incremental rehashing.
• আকার মৌলিক না 2-এর ঘাত: mod m-এর জন্য মৌলিক m ভালো (GCC তা-ই করে)। Java আর Python 2-এর ঘাত নেয়, কারণ তখন mod মানে শুধু একটি bit-mask (hash & (m − 1)) — দ্রুত। তবে তখন hash-এর নিচের bit-গুলো ভালো হতে হয়, তাই Java hash-এর ওপরের ১৬টি bit নিচের সাথে XOR করে মিশিয়ে নেয়: h ^ (h >>> 16).

৮ · শত্রুর ইনপুট — universal hashing, hash flooding আর SipHash

অংশ ৪-এর বিশ্লেষণ ধরে নিয়েছিল key-গুলো “এলোমেলোভাবে” ছড়ায়। কিন্তু ইনপুট যদি দেয় এমন কেউ, যে আপনার hash function জানে আর আপনার প্রোগ্রাম ধীর করতে চায়? দুঃসংবাদটি প্রমাণ করা সহজ: যেকোনো নির্দিষ্ট hash function-এর একটি খারাপ ইনপুট আছে। |U| ≥ n·m হলে pigeonhole অনুযায়ী অন্তত একটি bucket-এ U-এর অন্তত n টি key পড়ে; আক্রমণকারী শুধু সেই n টি key পাঠায়, আর সব এক bucket-এ — প্রতিটি কাজ Θ(n), n টি insert মিলে Θ(n²). পর্ব ১৫-এ দেখেছেন, কনটেস্টে এই adversarial input-এর নাম anti-hash test.

Universal hashing — এলোমেলোতা আমাদের হাতে

সমাধানটি quick sort-এর এলোমেলো pivot-এর মতো (পর্ব ২২): এলোমেলোতা ইনপুটের ওপর ছেড়ে না দিয়ে নিজে নিন. ১৯৭৯ সালে J. Lawrence Carter আর Mark Wegman (প্রথম সংস্করণ ১৯৭৭ সালের একটি সম্মেলনে) universal hashing-এর ধারণা দেন: hash function-এর একটি পরিবার H, আর প্রোগ্রাম শুরুতে H থেকে এলোমেলোভাবে একটি h বেছে নেয়। পরিবারটি universal, যদি যেকোনো দুটি আলাদা key x ≠ y-এর জন্য

অর্থাৎ যেকোনো নির্দিষ্ট জোড়া key-এর collision-এর সম্ভাবনা ঠিক ততটুকু, যতটা সম্পূর্ণ এলোমেলো hash-এ। ফল: chaining-এ যেকোনো key x-এর bucket-এ অন্য key-এর প্রত্যাশিত সংখ্যা = Σ_{y ≠ x} Pr[h(y) = h(x)] ≤ (n − 1)/m < α. তাই প্রত্যাশিত খরচ O(1 + α) — যেকোনো ইনপুটের জন্য, কারণ সম্ভাবনা এখন h বাছাইয়ের ওপর, ইনপুটের ওপর নয়। আক্রমণকারী ইনপুট বানানোর সময় জানে না কোন h বেছে নেওয়া হবে, তাই তার পক্ষে কোনো নির্দিষ্ট ইনপুটকে খারাপ বানানো সম্ভব নয়। এটি পর্ব ৬১-এর randomized algorithm-এর একটি সুন্দর উদাহরণ।

একটি ক্লাসিক universal পরিবার: সব key-এর চেয়ে বড় একটি মৌলিক সংখ্যা p নিন, আর এলোমেলোভাবে a ∈ {1, …, p − 1}, b ∈ {0, …, p − 1} বেছে নিন।

প্রমাণের মূল ভাবনা: x ≠ y হলে (a, b) থেকে (ax + b mod p, ay + b mod p) জোড়ায় যাওয়ার নিয়মটি এক-এক (bijection), কারণ p মৌলিক বলে x − y-এর mod p-তে উল্টো আছে। তাই দুটি মান p-এর মধ্যে এলোমেলো দুটি আলাদা সংখ্যার মতো আচরণ করে, আর শেষ “mod m”-এর পর তারা একই ঘরে পড়ে বড়জোর 1/m সম্ভাবনায়।

Hash flooding — যখন আক্রমণ বাস্তব

২০০৩ সালে Scott Crosby আর Dan Wallach একটি গবেষণায় দেখান যে বাস্তব সফটওয়্যারের hash table (যেমন Perl-এর) ইচ্ছা করে বানানো ইনপুটে quadratic সময়ে নেমে আসে — এই “algorithmic complexity attack” দিয়ে অল্প ডেটা পাঠিয়েই সার্ভার অচল করা যায়। ২০১১ সালের ডিসেম্বরে জার্মানির একটি নিরাপত্তা সম্মেলনে (28C3) Alexander Klink আর Julian Wälde দেখান যে PHP, Java, Python, Ruby-সহ বহু জনপ্রিয় ওয়েব প্ল্যাটফর্ম একই আক্রমণে দুর্বল: ওয়েব সার্ভার একটি POST অনুরোধের সব প্যারামিটার একটি hash table-এ রাখে, তাই হাজার হাজার collision-ওয়ালা প্যারামিটার-নাম পাঠালেই একটি অনুরোধে CPU দীর্ঘক্ষণ ব্যস্ত। একে বলে hash flooding, এক ধরনের denial-of-service আক্রমণ।

Java-র উদাহরণটি দেখার মতো। অংশ ২-এর সূত্রে "Aa" = 65·31 + 97 = 2112, আর "BB" = 66·31 + 66 = 2112 — একই hash! আর দুটিই দুই অক্ষরের, তাই এগুলো জোড়া দিয়ে বানানো যেকোনো string — "AaAa", "AaBB", "BBAa", "BBBB" — সবার hash এক। k টি টুকরো জুড়লে 2^k টি আলাদা string, সবাই এক bucket-এ। Hash function সবার জানা আর নির্দিষ্ট — এটাই দুর্বলতা।

প্রতিকার হিসেবে এসেছে গোপন key-ওয়ালা hash. ২০১২ সালে Jean-Philippe Aumasson আর Daniel J. Bernstein SipHash প্রকাশ করেন: একটি দ্রুত hash function, যা একটি 128-bit গোপন key নেয়। প্রোগ্রাম চালু হওয়ার সময় key এলোমেলোভাবে বাছাই হয়, তাই বাইরের কেউ জানে না কোন string কোন bucket-এ যাবে — universal hashing-এর ভাবনার বাস্তব, দ্রুত রূপ। Python ৩.৩ থেকে string-এর hash প্রতিবার চালানোয় আলাদা seed পায় (PYTHONHASHSEED), আর ৩.৪ থেকে str ও bytes-এর hash SipHash-ভিত্তিক; Rust-এর HashMap-এর ডিফল্ট hash-ও SipHash-এর একটি রূপ। Java অন্য পথ নিয়েছে: Java 8 থেকে HashMap-এর কোনো bucket-এ বেশি key জমলে তালিকাটি একটি red-black tree-তে বদলে যায় (অংশ ৯), তাই ওই bucket-এ worst case O(n) থেকে নেমে আসে O(log n)-এ (key Comparable হলে, যেমন String-এর ক্ষেত্রে)।

৯ · লাইব্রেরি আর প্রয়োগ — set, map, two-sum থেকে Bloom filter

দুই ধরনের hash container আছে। Hash set শুধু key রাখে আর উত্তর দেয় “আছে কি না” — C++-এ unordered_set, Python-এ set, Java-তে HashSet. Hash map প্রতিটি key-এর সাথে একটি value রাখে (key → value জোড়া) — C++-এ unordered_map, Python-এ dict, Java-তে HashMap. ভেতরের কৌশল একই; Java-র HashSet তো আসলে ভেতরে একটি HashMap, যার প্রতিটি value একটি নকল বস্তু। তিন ভাষার লাইব্রেরি কিন্তু তিনটি আলাদা নকশা বেছে নিয়েছে:

Python dict-এর probe সাধারণ linear নয়: পরের ঘর হিসাব হয় j = (5j + 1 + perturb) mod 2^k, যেখানে perturb শুরুতে পুরো hash আর প্রতি ধাপে ৫ bit ডানে সরে। ফলে hash-এর ওপরের bit-গুলোও পথ ঠিক করতে কাজে লাগে, আর একই home-এর key-রা আলাদা পথে ছড়ায় — double hashing-এর মতো সুবিধা, কম খরচে।

প্রচলিত প্রয়োগ

• Two-sum: অ্যারেতে এমন দুটি index খুঁজুন যাদের যোগফল target. প্রতিটি a[j]-এর জন্য দেখুন target − a[j] আগে দেখা হয়েছে কি না — hash map-এ (মান → index) রাখলে গড়ে O(n) সময়, O(n) জায়গা। পর্ব ১৬-এর two pointer সমাধান সাজানো অ্যারেতে O(1) জায়গায় কাজ করে, কিন্তু সাজাতে লাগে O(n log n) আর মূল index হারায়। (two-sum)
• Frequency counting: কোন শব্দ কতবার এসেছে, কোন bKash নম্বরে আজ কতটি লেনদেন — cnt[key]++. মান ছোট পূর্ণসংখ্যা হলে সাধারণ অ্যারে (frequency array) আরও দ্রুত — ছোট U-তে direct-address table-এ ফিরে যাওয়া।
• Deduplication: একটি hash set-এ রেখে দিন; ইতিমধ্যে থাকলে বাদ। ডুপ্লিকেট বাদ দেওয়া গড়ে O(n), সাজিয়ে করলে O(n log n) — তবে hash-এ মূল ক্রম রাখতে আলাদা যত্ন লাগে।
• Caching আর memoization: একবার হিসাব করা উত্তর (ইনপুট → ফল) hash map-এ রেখে দিন, পরের বার সরাসরি নিন। পর্ব ৫২-এর memoization-এর ভিত্তি এটিই; Python-এর functools.cache ভেতরে একটি dict. Doubly linked list-এর সাথে জুড়লে LRU cache (পর্ব ১২)।

Bloom filter — “হয়তো আছে” বা “নিশ্চিত নেই”

কখনো কখনো শুধু জানতে চাই একটি key সেটে আছে কি না, আর মেমরি খুব কম। ১৯৭০ সালে Burton H. Bloom একটি চতুর কাঠামো দেন — Bloom filter: m টি bit-এর একটি অ্যারে (শুরুতে সব 0) আর k টি আলাদা hash function. Insert(x): k টি hash-এর প্রতিটি ঘরে bit 1 করুন। Query(x): k টি ঘরই 1 হলে উত্তর “হয়তো আছে”, কোনো একটি 0 হলে “নিশ্চিত নেই”. অন্য key-রা মিলে ঠিক x-এর k টি ঘরই 1 করে ফেলতে পারে, তাই false positive সম্ভব; কিন্তু x ঢোকানো হলে তার ঘরগুলো কখনো 0 হয় না, তাই false negative অসম্ভব। key-গুলো নিজে কোথাও রাখা হয় না — শুধু bit.

n টি key ঢোকানোর পর একটি নির্দিষ্ট bit তখনো 0 থাকার সম্ভাবনা (1 − 1/m)^kn ≈ e^−kn/m. একটি নতুন key-এর k টি ঘরই 1 হওয়ার সম্ভাবনা, অর্থাৎ false positive-এর হার প্রায়

প্রতি key-এ ১০ bit (m/n = 10) আর k = 7 নিলে p ≈ (1 − e^−0.7)⁷ ≈ 0.0082 — ১%-এরও কম, অথচ key-গুলো নিজে রাখলে লাগত অনেক গুণ বেশি জায়গা। ডেটাবেস (যেমন LevelDB, RocksDB, Cassandra-র মতো LSM-tree ভিত্তিক) ডিস্কের একটি ফাইল পড়ার আগে Bloom filter দেখে নেয়: “নিশ্চিত নেই” হলে ধীর ডিস্ক-পড়া বাদ। সাধারণ Bloom filter থেকে delete করা যায় না (একটি bit অন্য key-এরও হতে পারে); তার জন্য প্রতি ঘরে ছোট counter রাখা “counting Bloom filter” আছে।

Consistent hashing — সার্ভার বদলালেও key কম সরে

একটি বড় ওয়েবসাইটের ডেটা ১০টি cache সার্ভারে ভাগ করা আছে, সার্ভার = h(key) mod 10. একটি সার্ভার যোগ হলে mod 11 — প্রায় সব key-এর সার্ভার বদলে যায়, পুরো cache একসাথে অকেজো। Consistent hashing (David Karger ও সহকর্মীরা, ১৯৯৭) সার্ভার আর key দুটোকেই একটি বৃত্তের ওপর hash করে, আর প্রতিটি key যায় বৃত্তে ঘড়ির কাঁটার দিকে তার পরের সার্ভারে। নতুন সার্ভার শুধু তার ঠিক আগের অংশের key নেয় — গড়ে মোট key-এর মাত্র প্রায় 1/(সার্ভারের সংখ্যা) অংশ সরে। এই ধারণা থেকে Akamai-র content delivery network গড়ে ওঠে, আর Amazon-এর Dynamo (২০০৭) ও Cassandra-র মতো ডেটাবেস এটি ব্যবহার করে।

১০ · AI-এর যুগে hash table — “গড়ে O(1)” থেকে “গড়” শব্দটি হারিয়ে যায়

“Linear probing-ওয়ালা একটি hash table লিখে দাও” — AI কয়েক সেকেন্ডে লিখবে, আর insert-find-এর ছোট পরীক্ষায় চলবেও। Hash table-এর ভুল সাধারণত লুকিয়ে থাকে delete-এ আর ভরা টেবিলে, যা ছোট পরীক্ষায় আসেই না। আর বিশ্লেষণের প্রশ্নে AI প্রায়ই “hash table-এ সব কাজ O(1)” বলে দেয় — “গড়ে”, “কোন অনুমানে” আর “worst case” বাদ দিয়ে।

Hash table-এ AI সাধারণত যেসব ভুল করে

Hash table-এর কোড যাচাইয়ের চেকলিস্ট

• ছোট একটি ইনপুটে (m = 7 বা 11) প্রতিটি কাজের পর টেবিলটি হাতে dry run করে কোডের ছাপার সাথে মিলিয়েছি
• একই home-এর কয়েকটি key দিয়ে delete-এর পর find চালিয়েছি — tombstone পার হয়ে খোঁজা ঠিক চলে
• Edge case চালিয়েছি: খালি টেবিল, ডুপ্লিকেট insert, অনুপস্থিত key মোছা, ঋণাত্মক key, প্রায় ভরা টেবিল
• হাজারটি এলোমেলো কাজ চালিয়ে উত্তর ভাষার নিজস্ব set/dict-এর সাথে মিলিয়েছি — stress testing, যেখানে লাইব্রেরিই brute force উত্তর
• সবচেয়ে লম্বা chain বা probe-এর সংখ্যা মেপে দেখেছি, সব key এক জায়গায় জমছে কি না
• AI-এর দেওয়া complexity-তে “গড়ে”, “worst case” আর “amortized” আলাদা করে লেখা আছে কি না দেখেছি