प्रभावी डेटा संरचनाएँ: Sets और Maps

Java में कोड ऑप्टिमाइज़ करना

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Space/Time complexity लागू करना

अब हमें space और time complexity पता है!

इसे इस्तेमाल कर बेहतर, कुशल कोड कैसे लिखें?

सही data structure चुनकर!

एक user management system

हम एक user management system बना रहे हैं
दिए गए username के लिए जाँचना है कि user मौजूद है या नहीं
List का उपयोग: complexity $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Sets

यूनिक elements का collection, तेज़ lookup के साथ
जोड़ने, हटाने, और मौजूदगी जाँचने की औसत time complexity $O(1)$

बेहतर user management समाधान:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}

Maps

Dictionary जैसा: word (key) -> definition (value)
HashMap: operations के लिए औसत time complexity $O(1)$

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}

Hashcode method

इन्हें तेज़ बनाने वाली चीज़ -> hashCode()
हमारे ArrayList उदाहरण में, हमें username का index पता नहीं था
hashcode() से हम object को ऐसे index में बदलते हैं जिसे देखा जा सके
जैसे pavlos.2020 -> 35189

pavlos.2020 को hashcode से प्रोसेस करने पर 35189 प्राप्त होता है

Elements का indexing

HashMap और HashSet के नीचे एक array होता है
जब हम element जोड़ते हैं:
- Java आपके element पर hashCode() कॉल कर एक integer लेता है
- उस पर modulo लगाकर bucket नंबर निकालता है

उदाहरण:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- यही हमारा bucket है!

Collisions

जब एक से अधिक items एक ही bucket में आ जाएँ
- इसे collision कहते हैं
bucket के लिए LinkedList
इसलिए हम $O(1)$ औसतन कहते हैं

याद रखने योग्य बात

Data structure चुनना काम के लिए सही औज़ार चुनने जैसा है - हथौड़ा (ArrayList) कील के लिए बढ़िया है, पर स्क्रू के लिए खराब है (जहाँ Set बेहतर होगा)।

Tools

अभ्यास करते हैं!

Java में कोड ऑप्टिमाइज़ करना