পাইথন ডিকশনারি হ্যাশ টেবিল (Hash Table) হিসেবে ইমপ্লিমেন্টেড। ট্রি সার্চিং (tree searching) ব্যবহার হয় না।
লুকআপ প্রক্রিয়া
- কী-এর হ্যাশ কোড তৈরি:
hash(key) - হ্যাশ থেকে বাকেট ইনডেক্স নির্ধারণ
- বাকেটে কী মিলানো (কলিশন হলে প্রোবিং/oprobing)
- মিললে ভ্যালু রিটার্ন, নাইলে
KeyError
পরফরম্যান্স
- O(1) এভারেজ / অ্যামোর্টাইজড কনস্ট্যান্ট টাইম
- ডিকশনারির সাইজ বড় হলেও লুকআপ টাইম কনস্ট্যান্ট থাকে
মেমরি ট্রেড-অফ
- হ্যাশ টেবিল স্পার্স (sparse) — লোড ফ্যাক্টর ~২/৩ রক্ষা করা হয়
- খালি বাকেটও মেমরি অকুপাই করে
- এটি স্পেস-ফর-টাইম ট্রেড-অফ
হ্যাশ ফাংশন
- ইমিউটেবল অবজেক্ট (স্ট্রিং, টাপল, ইন্ট) হ্যাশেবল
- মিউটেবল অবজেক্ট (লিস্ট, ডিক্ট) হ্যাশেবল নয়
- কাস্টম ক্লাসে
__hash__ও__eq__ইমপ্লিমেন্ট করুন
