Działanie sprawdzania mapy

Question

Chciałbym zrobić coś, używając wartości mapy dla danego klucza, tylko jeśli mapa zawiera dany klucz. Naiwnie napiszę:

Map<String, String> myMap = ...; 

if(myMap.containsKey(key)) { 
    String value = myMap.get(key); 

    // Do things with value 
} 

Powyższy kod wygląda na łatwy do zrozumienia, ale z punktu widzenia wydajności nie byłoby lepiej następujący kod?

Map<String, String> myMap = ...; 

String value = myMap.get(key); 

if(value != null) { 
    // Do things with value 
} 

W drugim fragmencie nie podoba się fakt, że value jest zadeklarowany w szerszym zakresie.

Jak zmienia się wydajność poszczególnych przypadków w odniesieniu do wdrożenia mapy?

Uwaga: Załóżmy, że wartości null nie są dopuszczone na mapie.

Answer 1

Map to interfejs, więc klasy implementacyjne mają dość dużą swobodę w sposobie implementacji każdej operacji (można całkowicie napisać klasę, która buforuje ostatni wpis, co może pozwolić na stały dostęp czasowy dla operacji get, jeśli jest taki sam jak ostatnio zdobytego obiektu, co czyni go praktycznie ekwiwalentnym, z wyjątkiem przypuszczalnie wymaganego porównania).

Dla TreeMap i HashMap np containsKey jest zasadniczo tylko get operacja (dokładniej getEntry) z czekiem na null.

Dlatego dla tych dwóch pojemników pierwsza wersja powinna zająć około dwa razy dłużej jako drugą (zakładając, że w obu przypadkach używasz tego samego typu Map).

Należy pamiętać, że HashMap.get to O (1) (z funkcją haszowania dobrze pasującą do danych) i TreeMap.get jest O (log n). Więc jeśli wykonasz jakąkolwiek znaczącą część pracy w pętli, a Map nie zawiera rzędu milionów elementów, różnica w wydajności prawdopodobnie będzie znikoma.

jednak zwrócić uwagę na zrzeczenie w the docs dla Map.get:

Jeżeli mapa zezwala na wartości null, wówczas wartość zwracana wartość null nie musi oznaczać, że mapa nie zawiera mapowanie dla klucza; możliwe jest również, że mapa wyraźnie odwzorowuje klucz na wartość null. Do odróżnienia tych dwóch przypadków można użyć operacji containsKey.

Answer 2

Oczywiście druga wersja jest bardziej wydajna: tylko przeglądasz klucz w mapie raz, podczas gdy w pierwszej wersji wyszukujesz go dwukrotnie, obliczając dwukrotnie kod skrótu klucza i szukając w hashbucketach, zakładając, że używasz oczywiście hashmap.

Możesz mieć zupełnie inną implementację interfejsu mapy, która byłaby w stanie obsłużyć ten rodzaj kodu znacznie lepiej, pamiętając wpis mapy, który był powiązany z kluczem w wywołaniu ostatniej metody zawiera, jeśli kolejne używa tego samego klucza (za pomocą operatora ==), a następnie można nieodwracalnie zwrócić związaną wartość z zapamiętanej pozycji mapy.

Jednak istnieje niebezpieczeństwo w 2 metody: Co jeśli kładę to na mapie:

map.put("null", null); 

następnie map.get („null”) zwróci wartość null i może traktować ją jako „null "nie jest mapowany, gdy map.contains (" null ") zwróci true!

Answer 3

Aby odpowiedzieć na to pytanie,
„Jak wykonywanie określonych przypadkach zmiany w stosunku do wykonania mapy?”
Różnica w wydajności jest znikoma.

Aby komentować Twojego komentarza,
„W drugim fragmencie nie podoba się fakt, że wartość zadeklarowana w szerszym zakresie.”
Dobrze, nie powinieneś. Widzisz, istnieją dwa sposoby, aby uzyskać zerowy wróciłem z mapą:

1. Klucz nie istnieje LUB
2. klucz nie istnieje, ale jego wartość jest null (jeśli realizacja Mapa pozwala zerowa wartości, takie jak HashMap).

Tak więc oba scenariusze mogą rzeczywiście mieć różne wyniki, jeśli klucz istnieje z wartością pustą!

EDIT

napisałem poniższy kod, żeby przetestować skuteczność dwóch scenariuszy:

public class TestMapPerformance { 

    static Map<String, String> myMap = new HashMap<String, String>(); 
    static int iterations = 7000000; 

    // populate a map with seven million strings for keys 
    static { 
     for (int i = 0; i <= iterations; i++) { 
      String tryIt = Integer.toString(i); 
      myMap.put(tryIt, "hi"); 
     } 
    } 
    // run each scenario twice and print out the results. 
    public static void main(String[] args) { 
     System.out.println("Key Exists: " + testMap_CheckIfKeyExists(iterations)); 
     System.out.println("Value Null: " + testMap_CheckIfValueIsNull(iterations)); 
     System.out.println("Key Exists: " + testMap_CheckIfKeyExists(iterations)); 
     System.out.println("Value Null: " + testMap_CheckIfValueIsNull(iterations)); 
    } 

    // Check if the key exists, then get its value 
    public static long testMap_CheckIfKeyExists(int iterations) {  
     Date date = new Date(); 
     for (int i = 0; i <= iterations; i++) { 
      String key = Integer.toString(i); 
      if(myMap.containsKey(key)) { 
       String value = myMap.get(key); 
       String newString = new String(value); 
      } 
     } 
     return new Date().getTime() - date.getTime(); 
    } 

    // Get the key's value, then check if that value is null 
    public static long testMap_CheckIfValueIsNull(int iterations) { 
     Date date = new Date(); 
     for (int i = 0; i <= iterations; i++) { 
      String key = Integer.toString(i); 
      String value = myMap.get(key); 
      if(value != null) { 
       String newString = new String(value); 
      } 
     } 
     return new Date().getTime() - date.getTime(); 
    } 

} 

ja prowadził ją i był to wynik:

Key Exists: 9901 
Value Null: 11472 
Key Exists: 11578 
Value Null: 9387 

Tak Podsumowując, różnica w wydajności jest znikoma.