হ্যাশ টেবিলপড়তে ৫ মিনিট লাগবে

সেট এবং ম্যাপ (Sets & Maps)

চোখের পলকে মেম্বারশিপ চেক আর নাম ধরে ভ্যালু খোঁজা — সবার প্রিয় হ্যাশ টেবিল

Set lookup: O(1) গড়েMap lookup: O(1) গড়েMap insert: O(1) গড়েspace: O(n)

দৈনন্দিন প্রোগ্রামিংয়ে সবচেয়ে বেশি কাজে লাগা দুটো ডেটা স্ট্রাকচারই আসলে হ্যাশ টেবিলের ওপর দাঁড়ানো: সেট (Set) এবং ম্যাপ (Map)।

একটা সেট (Set) অনেকটা বিয়ের গেটের দারোয়ানের মতো, যার কাছে মেহমানদের একটা লিস্ট ধরানো আছে — আপনি শুধু জিজ্ঞেস করবেন "ভাই, এই লোকটা লিস্টে আছে কি?" আর সে সাথে সাথে আপনাকে হ্যাঁ বা না বলে দেবে। আর এখানে কোনো ডুপ্লিকেট বা একই জিনিস দুইবার থাকতে পারবে না। অন্যদিকে একটা ম্যাপ (Map) (যাকে ডিকশনারি বা হ্যাশ ম্যাপও বলা হয়) হলো অনেকটা মানুষের নামের লিস্ট আর ফোন নম্বরের মতো — আপনি শুধু কারো নাম (Key) বলবেন, আর সাথে সাথে তার ফোন নম্বর (Value) পেয়ে যাবেন।

Python — dict এবং set

পাইথনের বিল্ট-ইন dict হলো একটা হ্যাশ ম্যাপ। আর পাইথনের set হলো মূলত ভ্যালু ছাড়া একটা ডিকশনারির মতো, যেখানে শুধু Key-গুলোই থাকে। দুটোই ওপেন অ্যাড্রেসিং দিয়ে নিজেদের মতো দারুণ উপায়ে কাজ করে।

pseudocode

freq = {}  # ম্যাপ (Map): শব্দ → কয়বার আছে
for word in words:
    freq[word] = freq.get(word, 0) + 1

seen = set()  # সেট (Set): আগে দেখেছি কি না চেক করা
if x not in seen:
    seen.add(x)

JavaScript — Map, Set, আর সাধারণ অবজেক্ট (Objects)

জাভাস্ক্রিপ্টে এই কাজ করার তিনটে অপশন আছে, তবে তিনটে কিন্তু মোটেই এক নয়:

Object — সাধারণ Key-Value রাখার জন্য, তবে Key-গুলো স্ট্রিং বা সিম্বল হতে হয়। এতে প্রোটোটাইপ পলিউশনের রিস্ক থাকে, আর ES2015-এর আগে এতে সিরিয়াল ঠিক থাকার কোনো গ্যারান্টি ছিল না।
Map — এখানে Key হিসেবে যেকোনো ডেটা টাইপ রাখা যায়। যে সিরিয়ালে ঢোকাবেন, সেই সিরিয়ালটা ঠিক থাকে। এতে .size প্রপার্টি আছে, আর অ্যালগরিদম টাইপের কাজের জন্য এটাই সবচেয়ে সেরা।
Set — যেকোনো ডেটা টাইপের ইউনিক (শুধু একবার থাকবে এমন) ভ্যালু রাখার জন্য বেস্ট। এটাও ঢোকানোর সিরিয়াল ঠিক রাখে।

সোজা হিসাব: যদি আপনার Key-গুলো সাধারণ লেখা বা স্ট্রিং না হয়ে অন্য কিছু হয়, অথবা সিরিয়াল ঠিক রাখাটা জরুরি হয়—তাহলে Map/Set ব্যবহার করুন। আর যদি শুধু স্ট্রিং দিয়ে Key বানান এবং শেষে JSON-এ পাঠাতে চান, তখন নরমাল Object ব্যবহার করাই ভালো।

◈ Explore sets and maps

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

Map/Set দিয়ে ইন্টারভিউয়ের কমন প্যাটার্নগুলো

Two Sum (দুটো সংখ্যার যোগফল) — প্রতিটা সংখ্যার ইনডেক্স একটা ম্যাপে রাখুন। নতুন একটা সংখ্যা পেলে O(1) সময়ে চেক করে দেখুন, ম্যাপে ওর বন্ধু (complement) বসে আছে কি না।

Contains Duplicate (ডুপ্লিকেট আছে কি না) — সবগুলো জিনিস একটা সেটে একে একে ঢোকাতে থাকুন। যদি .add() করার পরও সেটের সাইজ না বাড়ে (অথবা ঢোকানোর আগেই .has() দিয়ে চেক করে দেখেন যে আছে), তার মানে ডুপ্লিকেট পাওয়া গেছে!

Group Anagrams (অ্যানাগ্রাম এক করা) — প্রতিটা শব্দকে সর্ট করে একটা কমন Key বানিয়ে ফেলুন (যেমন "eat" → "aet"), এরপর সেটাকে ম্যাপের Key বানিয়ে লিস্টের ভেতরে আসল শব্দটাকে ঢুকিয়ে দিন।

অর্ডার ঠিক রাখা বনাম সিরিয়াল না থাকা

সাধারণ হ্যাশ-ভিত্তিক Map/Set-গুলোর কোনো গ্যারান্টি দেওয়া সিরিয়াল থাকে না — আপনি যেভাবে ঢোকাবেন, সেভাবে যে পুরো সিরিয়ালটা মিলবে তার কোনো নিশ্চয়তা নেই (ভাষা ভেদে এটা বদলায়)। যদি আপনার এমন কিছু লাগে যেটা অটোমেটিকভাবে সর্ট বা সিরিয়াল করা থাকবে, তাহলে TreeMap (জাভাতে) বা SortedDict (পাইথনের sortedcontainers-এ) ব্যবহার করতে পারেন। এগুলো ভেতরে ভেতরে একটা ব্যালান্সড BST (Binary Search Tree) ব্যবহার করে, ফলে সব কাজ O(log n) স্পিডে হয়ে সিরিয়াল ঠিক রাখে।

দ্রষ্টব্য: যখনই কোনো সমস্যা বা প্রশ্নে দেখবেন ডুপ্লিকেট শব্দটা আছে, অথবা বলবে কে কয়বার আছে গুনতে, বা জানতে চাইবে "এটা কি আগে কখনো দেখেছি?" — তখনই সবার আগে Set বা Map-কে ডাকবেন। এগুলো প্রায় সবসময়ই একটা বিরক্তিকর O(n²) ব্রুট-ফোর্স সল্যুশনকে ম্যাজিকের মতো টেনে O(n) বানিয়ে দেয়।