HashMap আমাদের দৈনন্দিন কোডিংয়ের বিশ্বস্ত বন্ধু। কিন্তু অধিকাংশ জাভা ডেভেলপার এর পেছনের জটিল কার্যপ্রণালী না জেনেই HashMap ব্যবহার করেন, যার ফলে হঠাৎ পারফরম্যান্স বিপর্যয় কিংবা অদ্ভুত বাগ তৈরি হয়। এই টিউটোরিয়ালে আমরা HashMap-এর ভেতরের গঠন, হ্যাশ কোলিশন সমাধানের কৌশল, ডায়নামিক রিসাইজ পদ্ধতি এবং জাভা রিফ্লেকশন ব্যবহার করে সরাসরি ভেতরের বাকেট অ্যারে পরিদর্শনের উপায় বিস্তারিতভাবে শিখব। পুরো লেখায় একটি বাস্তব-চালনাযোগ্য উদাহরণ থাকছে, যা তুমি কপি করে রান করলেই HashMap-এর অভ্যন্তরীণ যাদু নিজের চোখে দেখতে পাবে।

ভূমিকা

জাভার HashMap একটি অত্যন্ত জনপ্রিয় ডেটা স্ট্রাকচার যা চাবি (Key) ও মানের (Value) জোড়া সংরক্ষণ করে এবং গড়ে O(1) সময়ে ডেটা খোঁজ, ঢোকানো ও মুছতে সক্ষম। এই গতির মূল রহস্য লুকিয়ে থাকে এর অভ্যন্তরীণ হ্যাশ টেবিলের মধ্যে। HashMap সংক্ষেপে বলতে গেলে একটি বাকেট অ্যারে (Bucket array) – একটি Node অবজেক্টের অ্যারে, যেখানে প্রতিটি Node একই হ্যাশ বিশিষ্ট একাধিক এন্ট্রির সংযুক্ত তালিকা (Linked List) অথবা রেড-ব্ল্যাক ট্রির (Red-Black Tree) মূল হতে পারে। যখন তুমি কোনো চাবি-মান জোড়া দাও, HashMap চাবির hashCode() ব্যবহার করে বাকেট খুঁজে বের করে এবং সেই বাকেটে ডেটা রাখে।

এই টিউটোরিয়ালটি পড়ার পর তুমি বুঝতে পারবে HashMap-এর ভেতরে কী ঘটে, কীভাবে put ও get মেথড কাজ করে, কেন equals ও hashCode এর সঠিক ইমপ্লিমেন্টেশন অপরিহার্য, এবং প্রয়োজনীয় ধারণক্ষমতা ও লোড ফ্যাক্টর নির্ধারণ করে কীভাবে পারফরম্যান্স তুুুলনামূলক বাড়ানো যায়। সেই সঙ্গে আমরা রিফ্লেকশনের সাহায্যে HashMap-এর গোপন অঙ্গ—অভ্যন্তরীণ টেবিল, থ্রেশহোল্ড, কোলিশন চেইন—সবই উন্মোচন করব।

পূর্বশর্ত

এই টিউটোরিয়ালটি ভালোভাবে বোঝার জন্য নিচের বিষয়গুলোতে তোমার ধারণা থাকা প্রয়োজন:

  • জাভা অবজেক্টের equals(Object) ও hashCode() মেথডের চুক্তি এবং কেন এদের একসঙ্গে ওভাররাইড করতে হয়।
  • জেনেরিকস ও মৌলিক Map ইন্টারফেস পরিচিতি।
  • জাভা Collections ফ্রেমওয়ার্কের সাথে কাজ করার অভিজ্ঞতা (বিশেষ করে HashMap এর ব্যবহার)।
  • জাভা রিফ্লেকশন API-এর প্রাথমিক ধারণা (ফিল্ড অ্যাক্সেস, setAccessible(true) ইত্যাদি) – যদিও এখানে প্রয়োজনীয় কোড বোঝার জন্য বিস্তারিত দেখাব।

HashMap-এর অভ্যন্তরীণ গঠন ও কার্যপ্রণালী

এই ধাপে আমরা HashMap-এর অভ্যন্তরীণ স্থাপত্যটি টুকরো টুকরো করে বুঝব এবং put অপারেশনের পেছনের ধাপগুলো বের করব।

১. মূল ডেটা স্ট্রাকচার – বাকেট অ্যারে ও নোড

HashMap এর অভ্যন্তরে transient Node<K,V>[] table; নামের একটি অ্যারেকে বাকেট অ্যারে হিসেবে ব্যবহার করে। প্রতিটি Node<K,V> অবজেক্ট একটি লিংকড লিস্টের সদস্য এবং এতে থাকে:

  • final int hash; – চাবির সংরক্ষিত হ্যাশ মান
  • final K key;
  • V value;
  • Node<K,V> next; – একই বাকেটের পরবর্তী এন্ট্রির রেফারেন্স

জাভা ৮ থেকে কোনো একটি বাকেটে যখন এন্ট্রির সংখ্যা TREEIFY_THRESHOLD (৮) এ পৌঁছায় এবং মোট বাকেট সংখ্যা MIN_TREEIFY_CAPACITY (৬৪) এর বেশি হয়, তখন লিংকড লিস্ট স্বয়ংক্রিয়ভাবে একটি রেড-ব্ল্যাক ট্রিতে রূপান্তরিত হয় – যাকে বলা হয় ট্রিফিকেশন। এটি ওই বাকেটের খোঁজের সময় O(n) থেকে কমিয়ে O(log n) করে দেয়।

২. হ্যাশ ফাংশন ও বাকেট ইন্ডেক্স নির্ধারণ

HashMap চাবির hashCode সরাসরি ব্যবহার না করে একটি স্প্রেড ফাংশন প্রয়োগ করে, যাতে অ্যারের ইন্ডেক্সে কোলিশন কম হয়। জাভা ৮-তে ব্যবহৃত hash() ফাংশন:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

এখানে মূল হ্যাশ কোডের উচ্চ ১৬ বিটকে নিম্ন ১৬ বিটের সাথে XOR করা হয়, যাতে ছোট অ্যারের জন্য শুধু নিচের বিট না দেখে পুরো হ্যাশের বিস্তার নেওয়া হয়।

তির্যক ইন্ডেক্স বের করার সূত্রটি অত্যন্ত দ্রুতগতির:

index = (table.length - 1) & hash

অ্যারের দৈর্ঘ্য সর্বদা ২-এর ঘাত (power of two) হওয়ায় table.length - 1 একটি বিটমাস্ক হিসেবে কাজ করে, যা মডুলো অপারেশনের মতো দ্রুত ইন্ডেক্স দেয়।

৩. put(K key, V value) – ধাপে ধাপে বিশ্লেষণ

নিচে একটি put অপারেশনের সরলীকৃত ধাপগুলি দেখানো হলো (প্রকৃত সোর্সে আরও জটিল অপ্টিমাইজেশন আছে):

  1. প্রথমে চাবি null হলে putForNullKey(value) (জাভা ৮ এর পূর্বে), অথবা টেবিলের প্রথম বাকেট (ইন্ডেক্স ০) এ সংরক্ষিত হয়।
  2. চাবির জন্য hash(key) বের করে সেই হ্যাশ এবং বর্তমান টেবিল দৈর্ঘ্য দিয়ে ইন্ডেক্স হিসাব করা হয়।
  3. ওই ইন্ডেক্সের নোডটি যদি null হয়, সরাসরি নতুন Node বসিয়ে দেওয়া হয়।
  4. অন্যথায় ওই বাকেটের লিংকড লিস্ট বা ট্রি ট্র্যাভার্স করে চাবির সাথে equals() ব্যবহার করে মিলিয়ে দেখা হয়:
    • যদি একই চাবি পাওয়া যায়, তাহলে পুরনো মান আপডেট করে রিটার্ন করে।
    • না পেলে তালিকার শেষে নতুন নোড জুড়ে দেয় (বা ট্রিতে ইনসার্ট)।
  5. ইনসার্ট করার পর সাইজ বাড়িয়ে চেক করা হয়, size > threshold (capacity * loadFactor) হলে resize() মেথড কল করে অ্যারেকে দ্বিগুণ করা হয় এবং সব এন্ট্রি পুনর্বণ্টিত হয়।

৪. রিসাইজ ও রিহ্যাশিং

HashMap-এর থ্রেশহোল্ড = capacity * loadFactor। ডিফল্ট লোড ফ্যাক্টর ০.৭৫ এবং প্রারম্ভিক ধারণক্ষমতা ১৬। যখনই সাইজ থ্রেশহোল্ড ছাড়ায়, তখন টেবিলের সাইজ দ্বিগুণ হয় (যেমন ১৬ → ৩২ → ৬৪ …) এবং প্রতিটি নোড নতুন ইন্ডেক্সে পুনর্বণ্টিত হয়। এই প্রক্রিয়াকে রিহ্যাশিং বলে। পুরনো চেইনের প্রতিটি নোডের জন্য নতুন ইন্ডেক্স হয় হয় আগের ইন্ডেক্স i অথবা i + oldCapacity – কারণ নতুন বিট মাস্কে একটি অতিরিক্ত উচ্চতর বিট যুক্ত হয়। এতে করে বড় বড় কলারেশন এড়ানো যায়, কিন্তু রিসাইজ নিজেই একটি ব্যয়বহুল অপারেশন।

একটি পূর্ণাঙ্গ উদাহরণ: রিফ্লেকশন দিয়ে HashMap-এর ভেতরের অবস্থা পর্যবেক্ষণ

এখন আমরা একটি পূর্ণাঙ্গ জাভা ক্লাস লেখব যা রিফ্লেকশন ব্যবহার করে HashMap-এর অভ্যন্তরীণ টেবিলে সরাসরি চোখ বুলাবে। এই উদাহরণে আমরা এমন একটি Key ক্লাস তৈরি করব যার hashCode ইচ্ছাকৃতভাবে একই রিটার্ন করে, কিন্তু equals মেথড ভিন্ন ভিন্ন অবজেক্টকে আলাদা রাখে। এরপর ধাপে ধাপে মান ঢুকিয়ে বাকেটের গঠন, কোলিশন চেইন এবং রিসাইজ প্রভাব পর্যবেক্ষণ করব।

import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;

/**
 * HashMap এর অভ্যন্তরীণ বাকেট অ্যারে এবং কোলিশন চেইন পর্যবেক্ষণের উদাহরণ।
 */
public class HashMapInternalViewer {

    // এমন একটি কী ক্লাস যার hashCode সবসময় 42 রিটার্ন করে, কিন্তু equals পৃথকীকরণ সক্ষম
    static class CollidingKey {
        private final int id;

        CollidingKey(int id) {
            this.id = id;
        }

        @Override
        public int hashCode() {
            return 42; // ইচ্ছাকৃতভাবে কোলিশন তৈরি
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof CollidingKey)) return false;
            return this.id == ((CollidingKey) obj).id;
        }

        @Override
        public String toString() {
            return "Key#" + id;
        }
    }

    // রিফ্লেকশন দিয়ে HashMap এর table ফিল্ড বার করা
    @SuppressWarnings("unchecked")
    private static Map.Entry<?,?>[] getTable(HashMap<?,?> map) throws Exception {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        return (Map.Entry<?,?>[]) tableField.get(map);
    }

    // একটি নির্দিষ্ট বাকেটের সমস্ত নোড প্রিন্ট করার হেল্পার
    private static void printBucket(Map.Entry<?,?> head) {
        int count = 0;
        Map.Entry<?,?> current = head;
        while (current != null) {
            System.out.printf("    -> %s = %s (hash: %d, class: %s)%n",
                current.getKey(), current.getValue(),
                current.hashCode(),
                current.getClass().getSimpleName());
            count++;
            // পরবর্তী নোডের রেফারেন্স পেতে রিফ্লেকশন ব্যবহার করতে হবে
            try {
                Field nextField = current.getClass().getDeclaredField("next");
                nextField.setAccessible(true);
                current = (Map.Entry<?,?>) nextField.get(current);
            } catch (Exception e) {
                break;
            }
        }
        if (count == 0) {
            System.out.println("    (খালি)");
        } else {
            System.out.println("    মোট নোড: " + count);
        }
    }

    public static void main(String[] args) throws Exception {
        // ছোট্ট প্রারম্ভিক ধারণক্ষমতা (4) এবং ডিফল্ট লোড ফ্যাক্টর (0.75) সহ একটি HashMap
        HashMap<CollidingKey, String> map = new HashMap<>(4);
        System.out.println("=== প্রাথমিক অবস্থা ===");
        System.out.println("সাইজ: " + map.size());

        // প্রথম কী যোগ করি
        CollidingKey k1 = new CollidingKey(1);
        map.put(k1, "এক");
        System.out.println("\n--- k1 যোগ করার পর ---");
        Map.Entry<?,?>[] table1 = getTable(map);
        System.out.println("টেবিল দৈর্ঘ্য: " + table1.length);
        // k1 এর হ্যাশ 42, টেবিল দৈর্ঘ্য 4 -> ইন্ডেক্স = (4-1) & hash(42) = 3 & 42 = 2
        int idx1 = (table1.length - 1) & 42; // hash(42) -> 42 ^ (42>>>16)=42
        System.out.println("ইন্ডেক্স (k1): " + idx1);
        printBucket(table1[idx1]);

        // দ্বিতীয় কী, একই হ্যাশ
        CollidingKey k2 = new CollidingKey(2);
        map.put(k2, "দুই");
        System.out.println("\n--- k2 যোগ করার পর (একই বাকেট) ---");
        Map.Entry<?,?>[] table2 = getTable(map);
        System.out.println("টেবিল দৈর্ঘ্য: " + table2.length);
        int idx2 = (table2.length - 1) & 42;
        System.out.println("ইন্ডেক্স (k2): " + idx2);
        printBucket(table2[idx2]);

        // তৃতীয় কী, এখনও একই বাকেটে কোলিশন
        CollidingKey k3 = new CollidingKey(3);
        map.put(k3, "তিন");
        System.out.println("\n--- k3 যোগ করার পর (এখনো একই বাকেট) ---");
        Map.Entry<?,?>[] table3 = getTable(map);
        System.out.println("টেবিল দৈর্ঘ্য: " + table3.length);
        int idx3 = (table3.length - 1) & 42;
        System.out.println("ইন্ডেক্স (k3): " + idx3);
        printBucket(table3[idx3]);

        // চতুর্থ কী যোগ করলেই থ্রেশহোল্ড (capacity*0.75 = 3) অতিক্রম করবে এবং resize হবে
        CollidingKey k4 = new CollidingKey(4);
        map.put(k4, "চার");
        System.out.println("\n--- k4 যোগ করার পর (রিসাইজ ঘটেছে) ---");
        Map.Entry<?,?>[] table4 = getTable(map);
        System.out.println("নতুন টেবিল দৈর্ঘ্য: " + table4.length + " (দ্বিগুণ হয়েছে)");
        // এখন ইন্ডেক্স হবে (8-1) & 42 = 7 & 42 = 2 অথবা (7 & 42) যদি 42 আরও বড়? 7 & 42 = 2? 42 binary: 101010, 7: 000111 -> 000010 = 2
        // তবে রিহ্যাশের সময় কিছু এন্ট্রি (42 এর হ্যাশ) শুধুমাত্র পুরনো ইন্ডেক্স বা oldCap + পুরনো ইন্ডেক্স এ যাবে না কারণ নতুন ক্যাপাসিটি 8 হলে বিটমাস্ক 7 => (n-1) & hash = 7 & 42 = 2; যাই হোক বাকেট চেক করব।
        // আমরা প্রতিটি বাকেটের দিকে নজর দিই
        for (int i = 0; i < table4.length; i++) {
            if (table4[i] != null) {
                System.out.println("বাকেট[" + i + "]:");
                printBucket(table4[i]);
            }
        }
    }
}

উপরের কোড প্রথমে ৪ ধারণক্ষমতা বিশিষ্ট একটি HashMap তৈরি করে এবং এমন তিনটি চাবি যোগ করে যাদের হ্যাশ প্রত্যেকেই ৪২। রিফ্লেকশন ব্যবহার করে আমরা অ্যাক্সেস পাই table ফিল্ডে – যা আসলে একটি Node<?,?>[] অ্যারে। প্রথম তিনটি কী যোগ করার পর দেখা যাবে যে তারা সব একই বাকেটে (ইন্ডেক্স ২) চেইন আকারে জমা হয়েছে। চতুর্থ কী ঢোকানোর সাথে সাথেই থ্রেশহোল্ড অতিক্রান্ত হয় এবং টেবিল দ্বিগুণ হয়ে ৮ হয়; পুনর্বণ্টনের পরেও একই বাকেটে থেকে যায় অথবা কিছু এন্ট্রি ছড়িয়ে যেতে পারে (রিহ্যাশিং বিধি অনুসারে)। এটি বাস্তবে রান করলে তুমি চেইনের গঠন ও রিসাইজ প্রভাব সরাসরি কনসোলে দেখতে পাবে।

সাধারণ সমস্যা ও সমাধান

HashMap ব্যবহারের সময় জাভা ডেভেলপাররা প্রায়ই নিচের সমস্যাগুলোর সম্মুখীন হন:

  • পরিবর্তনশীল চাবি (Mutable keys): যদি কোনো চাবির hashCode বা equals নির্ভর করে পরিবর্তনশীল ফিল্ডের ওপরে, তাহলে মান ঢোকানোর পর চাবি পরিবর্তন করলে HashMap সেই এন্ট্রি আর খুঁজে পায় না, এতে মেমরি লিক ও ভুল ফল হয়। সমাধান: অপরিবর্তনীয় (immutable) ক্লাস ব্যবহার করো যেমন String, Integer, অথবা নিজস্ব ইমিউটেবল ডিজাইন করো।
  • অদক্ষ hashCode বাস্তবায়ন: অনেক অবজেক্টের hashCode একই হলে অতি-কোলিশন ঘটে এবং বাকেটগুলো দীর্ঘ লিংকড লিস্টে পরিণত হয়, যার ফলে get ও put প্রায় O(n) সময় নেয়। সমাধান: hashCode-এ যথেষ্ট বিচ্ছুরণ (dispersion) নিশ্চিত করতে JDK প্রদত্ত টুলস বা IDE অটো-জেনারেশন ব্যবহার করো।
  • প্রারম্ভিক ধারণক্ষমতা ও লোড ফ্যাক্টর উপেক্ষা: বড় ডেটাসেটের জন্য ডিফল্ট ক্যাপাসিটি ও লোড ফ্যাক্টর ব্যবহার করলে বারবার রিসাইজিং ঘটে, যা পারফরম্যান্স নষ্ট করে। সমাধান: প্রত্যাশিত সাইজের ওপর ভিত্তি করে new HashMap(expectedSize / 0.75 + 1) প্যাটার্নে ক্যাপাসিটি নির্ধারণ করো।
  • মাল্টি-থ্রেডেড পরিবেশ: HashMap থ্রেড-সেফ নয়। একাধিক থ্রেড একসাথে মডিফাই করলে কন্কারেন্টমডিফিকেশন এক্সেপশন, ইনফিনিট লুপ (জাভা ৭ ও পূর্ববর্তী) বা ডেটা দুর্নীতি হতে পারে। সমাধান: ConcurrentHashMap অথবা Collections.synchronizedMap ব্যবহার করো।
  • নাল চাবি ও মান: HashMap একটি null কী ও একাধিক null মান অনুমোদন করে, কিন্তু ConcurrentHashMap এ null কী/মান নিষিদ্ধ। এ কারণে মাইগ্রেশনের সময় অপ্রত্যাশিত NullPointerException হতে পারে। সমাধান: প্রজেক্টের শুরুতেই নীতি ঠিক করে নাও এবং Optional ব্যবহার বিবেচনা করো।

সারসংক্ষেপ

এই টিউটোরিয়ালে আমরা HashMap-এর অভ্যন্তরীণ জগতে বিচরণ করেছি:

  • HashMap একটি বাকেট অ্যারে ভিত্তিক হ্যাশ টেবিল, যেখানে কোলিশন সমাধানে লিংকড লিস্ট ও উচ্চ ঘনত্বে রেড-ব্ল্যাক ট্রি ব্যবহার করা হয়।
  • হ্যাশ ফাংশন উচ্চ বিট ছড়িয়ে দিয়ে ইন্ডেক্স কোলিশন কমায়, আর ইন্ডেক্স বেরি করা হয় (n-1) & hash দ্রুতগামী অপারেশন দ্বারা।
  • put অপারেশনের সময় চাবির হ্যাশ ও equals এর সমন্বয়ে বাকেট চিহ্নিত করে প্রয়োজনে চেইন বা ট্রিতে এন্ট্রি স্থাপন করা হয়।
  • থ্রেশহোল্ড অতিক্রম হলে টেবিল দ্বিগুণ হয়ে পুনর্বণ্টন (রিহ্যাশ) সংঘটিত হয় – এটি একটি ব্যয়বহুল প্রক্রিয়া, তাই প্রারম্ভিক ধারণক্ষমতা গুরুত্বপূর্ণ।
  • একটি পূর্ণাঙ্গ রিফ্লেকশন উদাহরণের মাধ্যমে আমরা সরাসরি টেবিলের ভেতরের চেইন এবং রিসাইজ মুহূর্ত পর্যবেক্ষণ করেছি।
  • ব্যবহারিক সমস্যা (মিউটেবল কী, অদক্ষ হ্যাশ, মাল্টি-থ্রেড) ও তাদের সমাধান জেনে তুমি এখন HashMap কে আরও আত্মবিশ্বাসের সাথে ব্যবহার করতে পারবে।

এই জ্ঞান শুধু ইন্টারভিউর জন্য নয়, বরং দৈনন্দিন ডেভেলপমেন্টে টিউনিং ও ডিবাগিং-এর সময় তোমাকে আলাদা করে দেবে।

Share