Hash Map

Hash फिर bucket

Hash फ़ंक्शन key को array इंडेक्स में बदलता है। अलग keys एक ही bucket में टकरा सकती हैं; bucket के अंदर छोटी list (या tree) इसे सुलझाती है। अच्छे वितरण से get/put/delete औसत O(1), worst O(n)।

पहले अक्षर से पुस्तकालय

शीर्षक के पहले अक्षर से किताबें रखने पर आप सही शेल्फ़ पर तुरंत जा सकते हैं। यदि बहुत सारे शीर्षक 'S' से शुरू हों, वह शेल्फ़ धीमी — यही collision है।

एक पास में Two Sum

चलते-चलते हर संख्या का इंडेक्स रखें; डालने से पहले पूरक जाँचें।

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []

Output:

two_sum([2, 7, 11, 15], 9) -> [0, 1]

त्वरित जाँच: आपको key से तेज़ lookup चाहिए और क्रम की परवाह नहीं। चुनें...

• Sorted array + binary search
• Hash map
• Linked list