Cześć,
Mam taki probłem: potrzebuje przeiterować przez HashMapę, która może być współbieżnie zmieniana. Niestety do dyspozycji mam tylko Javę 1.4 więc nie mogę użyć takich przyjemnych kolekcji jak ConcurrentHashMap. Jedyny pomysł jaki mi przychodzi do głowy to zrobienie <ort>kopi </ort>kolecji i iterowanie po tej kopi. Ale te rozwiązanie nie jest idealne (wydajność, zasoby). Czy może ktoś zna lepszy sposób jak sobie poradzić z taką sytuacją?
0
0
Nie rób kopii. Zaimplementuj interfejs Map w ten sposób, że metody będą synchronizowane, a całą obsługę będą delegować do HashMapy.
0
Właśnie na blokowanie całej Hashmapy podczas iterowania nie mogę sobie pozwolić. Każdy element jest przetwarzany sporą ilość czasu (w porównaniu do zwykłego przekopiowania referencji).
0
To, co chcesz zrobić nie da się osiągnąć z HashMap.
Wrzuć do swojego projektu ConcurrentHashMap oraz wszystkie klasy zależne (np. ReentrantLock).
Źródła możesz znaleźć tu:
http://download.java.net/openjdk/jdk7/
lub
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ (klikasz na numer, aby pobrać plik).
0
A kto każe ci synchronizować wszystkie metody?
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class SynchronizedHashMap<K, V> implements Map<K, V> {
private HashMap<K, V> map = new HashMap<K, V>();
/**
*
* @see java.util.HashMap#clear()
*/
public synchronized void clear() {
map.clear();
}
/**
* @param key
* @return
* @see java.util.HashMap#containsKey(java.lang.Object)
*/
public synchronized boolean containsKey(Object key) {
return map.containsKey(key);
}
/**
* @param value
* @return
* @see java.util.HashMap#containsValue(java.lang.Object)
*/
public synchronized boolean containsValue(Object value) {
return map.containsValue(value);
}
/**
* @return
* @see java.util.HashMap#entrySet()
*/
public Set<java.util.Map.Entry<K, V>> entrySet() {
return map.entrySet();
}
/**
* @param o
* @return
* @see java.util.AbstractMap#equals(java.lang.Object)
*/
public synchronized boolean equals(Object o) {
return map.equals(o);
}
/**
* @param key
* @return
* @see java.util.HashMap#get(java.lang.Object)
*/
public V get(Object key) {
return map.get(key);
}
/**
* @return
* @see java.util.HashMap#isEmpty()
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* @return
* @see java.util.HashMap#keySet()
*/
public Set<K> keySet() {
return map.keySet();
}
/**
* @param key
* @param value
* @return
* @see java.util.HashMap#put(java.lang.Object, java.lang.Object)
*/
public synchronized V put(K key, V value) {
return map.put(key, value);
}
/**
* @param m
* @see java.util.HashMap#putAll(java.util.Map)
*/
public synchronized void putAll(Map<? extends K, ? extends V> m) {
map.putAll(m);
}
/**
* @param key
* @return
* @see java.util.HashMap#remove(java.lang.Object)
*/
public synchronized V remove(Object key) {
return map.remove(key);
}
/**
* @return
* @see java.util.AbstractMap#toString()
*/
public String toString() {
return map.toString();
}
/**
* @return
* @see java.util.HashMap#values()
*/
public Collection<V> values() {
return map.values();
}
@Override
public int size() {
return map.size();
}
}
Synchronizowana jest tylko zmiana, a nie odczyt.
0
Koziołek - takie synchronizowanie metod chyba mi nic nie da. Chodzi o to, żebym mógł iterować po kolekcji, której stan jest taki sam jak na początku iteracji. ConcurentHashMap zapewnił by mi coś takiego. Jedyne co mi przychodzi do głowy to:
- założyć locka na kolekcji (ale ten sposób z przyczyn wydajnościowych odpada)
- saemmu zrobić kopie kolekcji i iterować po niej.
Pytanie tylko czy jest jakiś lepszy sposób na zrobienie tego w Javie 1.4.
Własna implementacja ConcurrentHashMap odpada ze względu na to, że nie mogą tyle czasu przeznaczyć na to zadanie.
0
@Nopp, zależy ci na tym by zgadzała się wielkość kolekcji czy też na tym by też elementy w niej zawarte były niezmienne. W pierwszym przypadku wystarczy pobrać KeySet i z mojego kodu posłać w piach metodę remove (niech robi nic). Iterujesz się po kluczach takich jak były w momencie pobrania. Jeżeli jednak chcesz mieć niezmienne wartości to lepiej jest zrobić własną metodę clone.
0
Koziołek - chodzi tylko o to, żeby mógł bezproblemowo przeiterować po Hashmapie. A Hashmapa może być modyfikowana przez inne wątki (tj. elementy mogą być usuwane i dodawane). Jak sobie poiteruje po KeySet to przy usunięciu elementu przez inny wątek dostanie ConcurentModificationException.
0
@Nopp, czytaj dokładnie, pliz. Pisałem, że bierzesz mój kod, wywalasz synchronizację, a metodę remove zamieniasz na;
public V remove(Object key) {
return null;
}
Trzeba tylko by jeszcze po przeiterowaniu zwalniać lock, który zabraniał by na usuniecie całej mapy.
0
Koziołek - nie za bardzo rozumiem. Musze dać możliwośc innym wątkom usuwania dowolnych elementów podczas iteracji. Jak wywalę metodę remove to nie będe mógł usuwać tych elementów.
0
Tru, to ja nie umiem czytać. W takim wypadku jedyna metoda to kopiowanie.
0
Nopp napisał(a)
Własna implementacja ConcurrentHashMap odpada ze względu na to, że nie mogą tyle czasu przeznaczyć na to zadanie.
Przecież nikt Ci nie każe pisać jej samemu. Java ma otwarty kod i możesz ściągnąć implementację z podanego przeze mnie parę postów wyżej źródła. Będziesz musiał jednak usunąć generyki i dodać ręczne rzutowanie.
Co do kodu Koziołka, to metodę values() trzeba by napisać tak (podobnie keySet() i entrySet()):
public synchronized Collection values(){
return new ArrayList(map.values());
}
Jeżeli natomiast słownik zmienia się bardzo rzadko, to można w prosty sposób napisać coś podobnego do java.util.concurrent.CopyOnWriteArraySet
Coś takiego:
private List values;
private Map map;
@Override
public synchronized Object put(Object key, Object value) {
Object oldValue = map.put(key, value);
if (oldValue != value){
values = null;
}
return oldValue;
}
@Override
public synchronized Collection values() {
if (values == null) {
values = new ArrayList(map.values());
}
return values;
}
0
Koziołek, Twój pomysł z synchronizowaniem wyłącznie zapisów jest niestety zły. Chodzi o to, że operacja odczytu może pobrać daną, akurat wtedy, kiedy jakiś inny wątek jest np. w połowie zapisu tej właśnie danej. W efekcie jeżeli nie jest to operacja atomowa, to przypadkowe odczyty będą śmieciowymi danymi i będą powodować bardzo wredne awarie. W małych systemach to może nie wyjdzie, ale w dużych lub napakowanych odczytami i zapisami stanie się to bardzo bolesne. Efekt jest taki jakby system chodził na uszkodzonej pamięci bez CRC/ECC.
A co do tematu, to mam małe pytanie. Po co iterować przez hashmapę? Przecież to jest struktura do wyszukiwania. Jeżeli trzeba po niej iterować, to chyba coś w projekcie nie jest zupełnie w porządku. Jeżeli już trzeba, to ja bym pociągnął z mapy wszystkie klucze w jednym ruchu, a następnie po kolei w kółko wybierał po nich dane normalnie konkurując z innymi wątkami. Gdyby w międzyczasie jakiś wątek usunął obiekt pod zassanym kluczem, to po prostu należałoby olać. Synchronizacji jednak w podstawowych metodach dostępu do danych się nie da się uniknąć (np. wyłącznie settery i gettery, z których korzysta cała reszta metod, nawet tych wewnętrznych). No i jeszcze druga sprawa - czy obiekty pobierane z mapy są przez inne wątki modyfikowane czy też jedyne co one robią, to wkładają i zdejmują?
0
Dla ścisłości - iteruje przez LinkedHashMap. Gdybym mógł użyć Listy i zwykłych iteratorów to bym właśnie takie rozwiązanie wybrał. na razie algorytm wygląda w uprosczeniu tak:
synchronized(map) {
array = shallowCopy(map);
}
for(int i = 0; i < array.length; i++) {
Element e = array[i];
process(e);
map.remove(e);
}
Gdybym użył listy/tablicy to operacja remove była by wykonywana w czasie linowym. A teraz przynajmniej nie blokuje usuwania i dodwania przez inne wątki w czasie gdy przetwarzam elementy z listy. Jeżeli ktoś usunie element który chcę przetworzyć to nic wielkiego się nie stanie, process map.remove sprawdzają czy dany element jest na liście. Jak jakiś wątek doda element to tym bardziej nic się nie stanie.
Jakby ktoś mógł ocenić taki sposób było by fajnie :)
0
Masz do czynienia z typowym schematem producentów i konsumentów.
W Javie 5+ używa się do tego zwykle klasy ArrayBlockingQueue. W Javie 4 można to zrobić efektywnie za pomocą bloków synchronized.
Tworzymy bufor:
final private List<Resource> list = new ArrayList<Resource>();
Procedura tworzenia i umieszczania elementu w buforze:
public void produce() throws InterruptedException {
final Resource resource = doProduce(); /* Tworzenie elementu poza sekcja krytyczna*/
synchronized (list) {
while (list.size() == MAX_BUFFER) { /* Mozna to pominac, jezeli nie chcemy miec ograniczonego bufora */
list.wait();
}
list.add(resource);
list.notifyAll(); /* Powiadomienie o nowym elemencie */
}
}
Procedura pobierania i przetwarzania elementu:
public void consume() throws InterruptedException {
Resource resource;
synchronized (list) {
while (list.isEmpty()) {
list.wait();
}
resource = list.remove(list.size() - 1); /* Dla ArrayList. W przypadku LinkedList nalezy usuwac pierwszy element */
list.notifyAll(); /* Powiadomienie o miejscu w buforze - potrzebne tylko dla ograniczonego bufora */
}
doConsume(resource); /* Konsumpcja elementu poza sekcja krytyczna*/
}
Zaletą tego rozwiązania jest to, że wątki muszą się synchronizować tylko na czas pobierania/usuwania elementu. Natomiast produkcja/konsumpcja mogą następować współbieżnie. Oczywiście wszystko działa w czasie O(1).
0
__krzysiek85 - niestety mój problem to nie jest typowy producent konsument. Wątek konsumenta jest odpalany co kilka sekund (nie mam pojęcia czemu tak jest, ale tego nie mogę zmienić) i wtedy musi on przejść przez całą listę i obsłużyć czekające zadania. W czasie gdy lista jest przetwarzana, mogą byc z niej usuwane lub dodwane elementy.