ConcurrentHashMap Условно заместване

Бих искал да мога условно да заменя стойност в ConcurrentHashMap. Тоест, като се има предвид:

public class PriceTick {
   final String instrumentId;
   ...
   final long timestamp;
   ...

И клас (нека го наречем TickHolder), който притежава ConcurrentHashMap (нека просто го наречем map).

Искам да мога да внедря метод за условно поставяне, така че ако няма запис за ключа, новият се вмъква, но ако има съществуващ запис, новият се вмъква само ако стойността на клеймото за време в новият PriceTick е по-голям от съществуващия.

За решение на HashMap от старата школа, TickHolder ще има put метод:

public void add(PriceTick tick) {
   synchronized(map) {
      if ((map.get(tick.instrumentId) == null)
         || (tick.getTimestamp() > map.get(tick.instrumentId).getTimestamp()) )
         map.put(tick.instrumentId, tick);
      }
}

С ConcurrentHashMap човек би искал да откаже синхронизацията и да използва някакъв атомарен метод като replace, но това е безусловно. Така че ясно трябва да бъде написан методът "условна замяна".

Въпреки това, тъй като операцията за тестване и замяна не е атомарна, за да бъде безопасна за нишки, тя ще трябва да бъде синхронизирана - но първоначалното ми четене на източника на ConcurrentHashMap ме кара да мисля, че външната синхронизация и техните вътрешни заключвания няма работят много добре, така че като минимум всеки метод на Map, който извършва структурни промени и съдържащият клас изпълнява, ще трябва да бъде синхронизиран от съдържащия клас... и дори тогава ще бъда доста неспокоен.

Мислех за подкласиране на ConcurrentHashMap, но това изглежда невъзможно. Той използва вътрешен краен клас HashEntry с достъп по подразбиране, така че въпреки че ConcurrentHashMap не е окончателен, той не е разширим.

Което изглежда означава, че трябва да се върна към прилагането на TickHolder като съдържащ HashMap от старата школа, за да напиша моя метод за условна замяна.

И така, въпросите: прав ли съм за горното? Пропуснал ли съм (надявам се) нещо, било то очевидно или едва доловимо, което да доведе до различно заключение? Наистина бих искал да мога да използвам този прекрасен раиран заключващ механизъм тук.


person CPerkins    schedule 08.09.2009    source източник


Отговори (4)


Решението на @cletus формира основата за моето решение на почти идентичен проблем. Мисля, че са необходими няколко промени, тъй като ако oldTick е null, тогава замяната хвърля NullPointerException, както е посочено от @hotzen

PriceTick oldTick;
do {
  oldTick = map.putIfAbsent(newTick.getInstrumentId());
} while (oldTick != null && oldTick.before(newTick) && !map.replace(newTick.getInstrumentId(), oldTick, newTick);
person robSE13    schedule 31.01.2014
comment
Опитвали ли сте разтвора на клетус? Защото не виждам защо ще имаш NullPointerException. Решението използва || и &&, така че ако oldTick е null, всяка дясна страна на двата израза няма да бъде изпълнена, което предотвратява всяко NullPointerException. - person Marc-Andre; 31.01.2014
comment
@Marc-Andre Rob е прав. С решението на Cletus, както е написано, първото извикване за добавяне ще предизвика NullPointerException. Срещнах това, когато за първи път видях отговора, направих промените в моя проект, но никога не преразгледах тази тема. - person CPerkins; 31.01.2014
comment
@CPerkins Благодаря за актуализацията! Не разбирам съвсем какво не е наред, но и аз не съм тествал кода. - person Marc-Andre; 31.01.2014
comment
@Marc-Andre, ако oldTick е null, това удовлетворява oldTick == null страната на (oldTick == null || oldTick.before(newTick)), така че продължаваме през && към map.replace, което изрично проверява и хвърля NullPointerException, ако oldTick или newTick са null. И тъй като не трябва да водим разговори в коментари, спирам сега. - person CPerkins; 01.02.2014
comment
((oldTick == null || oldTick.before(newTick)) && !map.replace()) ако oldTick == null имаме ((true) && !map.replace(). Обикновено, ако имате true от лявата страна на &&, той не трябва да изпълнява дясната страна (или имам нужда от сън, защото забравям някои основни неща). Но както казахте, не трябва да чатим и аз сам ще направя някои тестове. (Вероятно просто пренебрегвам замяната, тъй като никога не съм го използвал) - person Marc-Andre; 01.02.2014

Недетерминираното решение е да се извърши цикъл replace():

do {
  PriceTick oldTick = map.get(newTick.getInstrumentId());
} while ((oldTick == null || oldTick.before(newTick)) && !map.replace(newTick.getInstrumentId(), oldTick, newTick);

Колкото и странно да изглежда, това е често предлаган модел за подобни неща.

person cletus    schedule 08.09.2009
comment
интересно Когато казвате недетерминистичен, искате да кажете, че резултатът е недетерминистичен? Или че времето е? Също така, прав ли съм, че вашият метод преди е предназначен да служи за сравнение на моето времево клеймо? Или пропускам нещо? - person CPerkins; 08.09.2009
comment
Под недетерминиран имам предвид, че може да отнеме няколко итерации, за да се извърши замяната, защото get и replace очевидно не е атомарна операция, но е безопасно. - person cletus; 09.09.2009
comment
Схванах го. Благодаря. Детерминистичен резултат от недетерминистичен метод (с очевидно недетерминистично време). Напомня ми за TCP/IP. :) Благодаря, страхотна идея. - person CPerkins; 12.09.2009
comment
Replace не позволява oldTick да бъде null, така че това решение трябва директно да влезе в NullPointerException чрез replace, когато се опита да замени oldTick==null с newTick... - person hotzen; 27.07.2012

Верният отговор трябва да бъде

PriceTick oldTick;
do {
  oldTick = map.putIfAbsent(newTick.getInstrumentId(), newTick);
  if (oldTick == null) {
    break;
  }
} while (oldTick.before(newTick) && !map.replace(newTick.getInstrumentId(), oldTick, newTick);
person Drpmma    schedule 17.01.2020

Като алтернатива бихте ли могли да създадете клас TickHolder и да го използвате като стойност във вашата карта? Това прави картата малко по-тромава за използване (получаването на стойност сега е map.getValue(key).getTick()), но ви позволява да запазите поведението на ConcurrentHashMap.

public class TickHolder {
  public PriceTick getTick() { /* returns current value */
  public synchronized PriceTick replaceIfNewer (PriceTick pCandidate) { /* does your check */ }
}

И вашият put метод става нещо като:

public void updateTick (PriceTick pTick) {
  TickHolder value = map.getValue(pTick.getInstrumentId());
  if (value != null) {
    TickHolder newTick = new TickHolder(pTick);
    value = map.putIfAbsent(pTick.getInstrumentId(), newTick);
    if (value == null) {
      value = newTick;
    }
  }
  value.replaceIfNewer(pTick);
}
person Sbodd    schedule 08.09.2009
comment
интересно Имахте предвид да синхронизирате PriceTick? Как се играе тази синхронизация със заключващия механизъм вътре в ConcurentHashMap? - person CPerkins; 08.09.2009
comment
TickHolder.replaceIfNewer ще трябва да бъде синхронизиран - това е основно мястото, където отива вашата атомна операция за тестване и условно актуализиране. Няма пряко взаимодействие между синхронизацията на TickHolder.replaceIfNewer и синхронизацията на картата. Картата (с малкото логика в updateTick) гарантира, че никога няма повече от един TickHolder за даден ключ; Синхронизацията replaceIfNewer гарантира, че актуализациите на даден TickHolder нямат проблеми с нишките. Нито updateTick, нито самият PriceTick (ако приемем, че PriceTick е неизменен) ще се нуждаят от друга синхронизация - person Sbodd; 08.09.2009
comment
Малко съм объркан защо смятате, че няма нужда от друга синхронизация. Синхронизирането на replaceIfNewer ограничава само извикванията до този метод. Така че други нишки могат да правят структурни промени в картата, използвайки други методи, нали? Все пак това е интересен подход. Ще помисля по-късно. - person CPerkins; 08.09.2009
comment
Предполагам, че направих имплицитно предположение, че нищо никога не се премахва от вашата карта - всички записи минават през updateTick. В който случай, след като сте получили TickHolder за даден InstrumentId, вече не се интересувате от други структурни промени в картата; TickHolder, който имате, е стойността в картата за вашия InstrumentId и просто трябва вашата операция да бъде взаимно изключваща се с други операции на този InstrumentId. - person Sbodd; 08.09.2009
comment
Кърлежите трябва да се махнат, но не съм го казал. Обърнете внимание обаче, че това не са само премахвания - добавянията също могат да причинят структурни промени (напр. повторно изхвърляне). - person CPerkins; 12.09.2009