পাইথন ডিকশনারি হ্যাশ টেবিল (Hash Table) হিসেবে ইমপ্লিমেন্টেড। এখানে ট্রি সার্চিং (tree searching) ব্যবহার হয় না।
লুকআপ প্রক্রিয়া
- কী-এর হ্যাশ কোড ক্যালকুলেট করা হয় (
hash(key)) - হ্যাশ কোড অনুযায়ী বাকেট লোকেশন খুঁজে বের করা
- কলিশন হলে (একই বাকেটে একাধিক কী) কলিশন রেজোলিউশন অ্যালগরিদম (open addressing) চালানো হয়
- সঠিক কী মিলালে ভ্যালু রিটার্ন
কমপ্লেক্সিটি
- লুকআপ: O(1) এভারেজ / অ্যামোর্টাইজড কনস্ট্যান্ট
- ডিকশনারির সাইজ বড় হলেও লুকআপ টাইম প্রায় একই থাকে
ট্রেড-অফ
- স্পেস: ডিকশনারি স্পার্স (sparse) — খালি বাকেটও মেমরি নেয়
- টাইম: খুব দ্রুত লুকআপ, ইনসারশন, ডিলিশন
নোট: পাইথন ৩.৩+ এ হ্যাশ র্যান্ডমাইজেশন (hash randomization) ডিফল্ট অন, সিকিউরিটির জন্য (DoS আটাক প্রতিরোধ)।
