Java HashMap.get (Object) nieskończona pętla

Question

Kilka odpowiedzi na SO wspomnieć, że metoda get w HashMap może wpaść w nieskończoną pętlę (np. this one lub this one), jeśli nie jest prawidłowo zsynchronizowany (i zazwyczaj dolnej linii jest "don" nie używaj HashMap w środowisku wielowątkowym, używaj ConcurrentHashMap ").

Podczas gdy mogę łatwo zobaczyć, dlaczego jednoczesne wywołania metody HashMap.put (Object) mogą powodować nieskończoną pętlę, nie mogę całkiem zrozumieć, dlaczego metoda get (Object) może utknąć podczas próby odczytania HashMap to jest w tej chwili zmieniane. Spojrzałem na implementation in openjdk i zawiera on cykl, ale warunek wyjścia e != null powinien zostać spełniony prędzej czy później. Jak może zapętlić się na zawsze? kawałek kodu, który jest wyraźnie wymieniony być narażone na ten problem jest:

public class MyCache { 
    private Map<String,Object> map = new HashMap<String,Object>(); 

    public synchronized void put(String key, Object value){ 
     map.put(key,value); 
    } 

    public Object get(String key){ 
     // can cause in an infinite loop in some JDKs!! 
     return map.get(key); 
    } 
} 

Może ktoś wyjaśnić jak nitki oddanie obiektu do HashMap i kolejny odczyt z może przeplatać w taki sposób, że nieskończona Pętla jest generowana? Czy ma to związek z kwestią spójności pamięci podręcznej lub kolejnością instrukcji CPU (więc problem może się zdarzyć tylko na maszynie wieloprocesorowej)?

Answer 1

Chociaż nigdy osobiście nie użyłem hashmap i skończyłem z nieskończoną pętlą (kiedykolwiek), powiem, że jeśli mówimy o wątkach, odpowiedź brzmi "zakleszczenia".

Zakleszczenia są wtedy, gdy więcej niż jeden wątek próbuje uzyskać dostęp do tego samego zasobu jednocześnie, dlatego wszystkie uczestniczące wątki czekają na zakończenie wszystkich pozostałych wątków, a więc wszystkie zagłodzą.

W języku Java synchronizowane słowo kluczowe zapewnia synchronizację określonej metody we wszystkich wątkach, więc żadne dwa wątki nie próbują uzyskać dostępu do tych samych informacji naraz.

Powrót do zasobu zasobów ... Jeśli dobrze pamiętam ... W Javie cała mapa nie jest uważana za zasób, więc jedna metoda "sprawdzi ją" zaraz po uruchomieniu. Jednakże, jeśli dwie metody próbują uzyskać jednocześnie tablicę kontrolną: zakleszczenie.

Warto zauważyć, że Java jest bardzo bezpiecznym językiem, więc proste umieszczenie zsynchronizowanego słowa kluczowego przed wszystkimi metodami dotyczącymi tego wielowątkowego zasobu powinno sprawić, że wszystko będzie wyglądać jak nowe.

Dalsze czytanie: Jest bardzo inspirujący niejaki Edsgar W. Dijkstra, z Holandii wierzę, który pracował bardzo intensywnie na zapobieganie impasu i systemów wielowątkowych. Jedną z jego najsłynniejszych wizualizacji i zagadek dotyczących zakleszczeń był problem filozofów stołowych :. Naprawdę fantastyczny człowiek.

Answer 2

Biorąc pod uwagę, że jedyną możliwością widzę dla nieskończonej pętli byłoby e.next = e wewnątrz metody get:

for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) 

A to może się zdarzyć tylko w metodzie transfer podczas zmiany rozmiaru:

do { 
    Entry<K,V> next = e.next; 
    int i = indexFor(e.hash, newCapacity); 
    e.next = newTable[i]; //here e.next could point on e if the table is modified by another thread 
    newTable[i] = e; 
    e = next; 
} while (e != null); 

Jeśli tylko jeden wątek modyfikuje mapę, uważam, że nie można mieć nieskończonej pętli z jednym wątkiem.To było bardziej oczywiste ze starym realizacji get przed JDK 6 (lub 5):

public Object get(Object key) { 
     Object k = maskNull(key); 
     int hash = hash(k); 
     int i = indexFor(hash, table.length); 
     Entry e = table[i]; 
     while (true) { 
      if (e == null) 
       return e; 
      if (e.hash == hash && eq(k, e.key)) 
       return e.value; 
      e = e.next; 
     } 
    } 

Nawet wtedy sprawa nadal wydaje się dość nieprawdopodobne, z wyjątkiem, gdy istnieje wiele kolizji.

P.S: Chciałbym się jednak nie udać!

Answer 3

Link do HashMap w Javie 6. Został przepisany w Javie 8. Przed tym przepisać nieskończoną pętlę na get(Object) było możliwe, jeśli były dwa pisanie wątków. Nie jestem świadomy sposobu, w jaki nieskończona pętla na get może wystąpić z jednym pisarzem.

szczególności nieskończonej pętli występuje wtedy, gdy istnieją dwa równoczesne połączenia z resize(int) które połączenia transfer:

void transfer(Entry[] newTable, boolean rehash) { 
    int newCapacity = newTable.length; 
    for (Entry<K,V> e : table) { 
     while(null != e) { 
      Entry<K,V> next = e.next; 
      if (rehash) { 
       e.hash = null == e.key ? 0 : hash(e.key); 
      } 
      int i = indexFor(e.hash, newCapacity); 
      e.next = newTable[i]; 
      newTable[i] = e; 
      e = next; 
     } 
    } 
} 

Logika ta odwraca się kolejność węzłów w wiadrze mieszania. Dwa jednoczesne odwrócenia mogą spowodować powstanie pętli.

Spójrz:

   e.next = newTable[i]; 
      newTable[i] = e; 

Jeśli dwa gwinty są obróbce tego samego węzła e, a pierwszy gwint wykonuje zwykle ale drugi gwint ustawia e.next = e, ponieważ newTable[i] został już ustawiony na e przez pierwszy gwint. Węzeł e wskazuje teraz na siebie, a kiedy jest wywoływany get(Object), wchodzi w nieskończoną pętlę.

W języku Java 8 zmiana rozmiaru utrzymuje kolejność węzłów, więc pętla nie może wystąpić w ten sposób. Możesz jednak stracić dane.

Klasa Iterators dla klasy LinkedHashMap może utknąć w nieskończonej pętli, gdy istnieje wiele czytników i nie jest zapisywanych podczas utrzymywania dostępu. W przypadku wielu czytników i kolejności dostępu każdy odczyt usuwa, a następnie wstawia pobrany węzeł z podwójnie połączonej listy węzłów. Wiele czytników może prowadzić do ponownego włożenia tego samego węzła na liście, powodując powstanie pętli. Ponownie klasa została przepisana dla Java 8 i nie wiem, czy ten problem nadal istnieje, czy nie.

Answer 4

Sytuacja:

Pojemność domyślna HashMap jest 16, a współczynnik obciążenia wynosi 0,75, co oznacza, HashMap podwoi swoje zdolności podczas 12th parę klucz-wartość wkracza na mapie (16 * 0,75 = 12).

Gdy 2 wątki próbują uzyskać dostęp do HashMap jednocześnie, możesz napotkać nieskończoną pętlę. Wątek 1 i wątek 2 próbują umieścić 12. parę klucz-wartość.

gwintu 1 dostał szansę wykonanie:

1. wątku 1 próbuje umieścić parę klucz-wartość 12.,
2. gwintu 1 zakłada, że ​​graniczna zostanie osiągnięta i tworzy nowe wiadra zwiększonej pojemności. Zwiększono pojemność mapy z 16 do 32.
3. Wątek 1 przenosi teraz wszystkie istniejące pary klucz-wartość do nowych segmentów.
4. Wątek 1 wskazuje pierwszą parę klucz-wartość i następną (drugą) parę klucz-wartość, aby rozpocząć proces przesyłania.

Wątek 1 po wskazaniu par klucz-wartość i przed rozpoczęciem procesu przesyłania, poluzuj kontrolkę, a wątek 2 ma szansę na wykonanie.

Temat 2 dostał szansę wykonanie:

1. wątku 2 próbuje umieścić parę klucz-wartość 12.,
2. Temat 2 zakłada, że ​​graniczna zostanie osiągnięta i tworzy nowe wiadra zwiększonej pojemności. Zwiększono pojemność mapy z 16 do 32.
3. Wątek 2 przenosi teraz wszystkie istniejące pary klucz-wartość do nowych segmentów.
4. Wątek 2 wskazuje pierwszą parę klucz-wartość i następną (drugą) parę klucz-wartość, aby rozpocząć proces przesyłania.
5. Podczas przesyłania par klucz-wartość ze starych wiader do nowych segmentów pary klucz-wartość będą odwracane w nowych segmentach, ponieważ hashmap doda pary klucz-wartość na początku, a nie na końcu. Hashmap dodaje nowe pary klucz-wartość na początku, aby za każdym razem unikać przechodzenia połączonych list i utrzymywać stałą wydajność.
6. Wątek 2 przeniesie wszystkie pary klucz-wartość ze starych wiader do nowych, a wątek 1 otrzyma szansę na wykonanie.

gwintu 1 dostał szansę wykonanie:

1. gwintu 1 przed opuszczeniem kontrolę wskazywał na pierwszy element i następnego elementu starego wiadra.
2. Teraz, gdy wątek 1 rozpoczął wprowadzanie par klucz-wartość ze starego wiadra do nowego. Z powodzeniem umieszcza (90, val) i (1, val) w nowym Bucket.
3. Kiedy próbuje dodać kolejny element (1, val), który jest (90, val) do nowego segmentu, kończy się nieskończoną pętlą.

Rozwiązanie:

Aby rozwiązać ten problem albo użyć Collections.synchronizedMap lub ConcurrentHashMap.

ConcurrentHashMap jest bezpieczny dla wątków, ponieważ dostęp do kodu można uzyskać za pomocą pojedynczego wątku na raz.

HashMap można synchronizować za pomocą metody Collections.synchronizedMap(hashMap). Za pomocą tej metody otrzymamy obiekt HashMap, który jest odpowiednikiem obiektu HashTable. Więc każda modyfikacja jest wykonywana na mapie jest zablokowana na obiekcie mapy.