कुशल डेटा स्ट्रक्चर: 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 के साथ
जोड़ने, हटाने और मौजूदगी जाँचने के लिए औसत समय जटिलता $O(1)$

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

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 के लिए औसत समय जटिलता $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() method से हम object को ऐसे index में बदल सकते हैं जिसे खोजा जा सके
उदाहरण: pavlos.2020 -> 35189

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

Elements की indexing

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

उदाहरण:

[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 बेहतर हो सकता है).

खुले टूलबॉक्स में साथ-साथ रखे हथौड़ा, स्क्रूड्राइवर, रेंच और प्लायर

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

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