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, тогда replace выдает исключение 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
Вы пробовали раствор cletus? Потому что я не понимаю, зачем тебе NullPointerException. В решении используются || и &&, поэтому, если oldTick имеет значение null, каждая правая часть обоих выражений не будет выполняться, предотвращая любое NullPointerException. - person Marc-Andre; 31.01.2014
comment
@ Марк-Андре Роб прав. С решением Cletus, как написано, первый вызов add вызовет исключение 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

Недетерминированное решение - использовать цикл _ 1_:

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
Интересный. Когда вы говорите «недетерминированный», вы говорите, что результат недетерминирован? Или что по срокам? Кроме того, я прав в том, что ваш метод before предназначен для сравнения моих меток времени? Или я что-то упускаю? - person CPerkins; 08.09.2009
comment
Под недетерминированным я подразумеваю, что для выполнения замены может потребоваться несколько итераций, потому что получение и замена, очевидно, не атомарная операция, но она безопасна. - 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