[हैश टेबल हैं] ओ (1) सम्मिलन और खोज
मुझे लगता है कि यह गलत है।
सबसे पहले, यदि आप कुंजीपटल को सीमित करने के लिए सीमित करते हैं,
तो आप तत्वों को सरणी में संग्रहीत कर सकते हैं और ओ (1) रैखिक स्कैन
कर सकते हैं। या आप सरणी को शफल कर सकते हैं और फिर ओ (1) अपेक्षित
समय में एक रैखिक स्कैन कर सकते हैं। जब सामान सीमित होता है, सामान
आसानी से ओ (1) होता है।
तो मान लें कि आपकी हैश तालिका किसी भी मनमानी बिट स्ट्रिंग को
स्टोर करेगी; इससे कोई फर्क नहीं पड़ता, जब तक कि चाबियों का एक अनंत
सेट होता है, जिनमें से प्रत्येक सीमित होते हैं। फिर आपको किसी भी
क्वेरी और सम्मिलन इनपुट के सभी बिट्स को पढ़ना होगा, अन्यथा मैं y0
पर रिक्त हैश और y1 पर क्वेरी डालता हूं, जहां y0 और y1 एक बिट बिट
स्थिति में भिन्न होते हैं जिसे आप नहीं देखते हैं।
लेकिन मान लें कि मुख्य लंबाई पैरामीटर नहीं है। यदि आपका सम्मिलन
और खोज ओ (1) लेती है, विशेष रूप से हैशिंग ओ (1) समय लेती है, जिसका
अर्थ है कि आप केवल हैश फ़ंक्शन से आउटपुट की सीमित मात्रा देखते हैं
(जिससे हो केवल एक सीमित आउटपुट, दिया गया)।
This means that with finitely many buckets, there must be an
infinite set of strings which all have the same hash value. Suppose
I insert a lot, i.e. ω(1), of those, and start querying. This means
that your hash table has to fall back on some other O(1)
insertion/search mechanism to answer my queries. Which one, and why
not just use that directly?