Мультикарта с хорошей производительностью

Question

В моем коде у меня есть карта, которая интенсивно используется несколько тысяч раз за несколько секунд. Первоначально у меня был TreeMap, но при тестировании с 9000 записей я наблюдал, как мой старый процессор таял. И это нужно масштабировать. Так что я перешел на HashMap и производительность была превосходной.

Сейчас я меняю свой дизайн и ищу MultiMap. Однако я боюсь влияния производительности на get() сторона, так как она должна перебирать указанную большую карту, выбирая совпадающие ключи, и при многократном вызове, даже синхронизированном, кажется, что это будет медленно.

Есть ли хорошая MultiMap, которая может обрабатывать такие большие значения с высокой производительностью? В этом приложении критически важна производительность, поскольку может быть много больших отдельных карт, обрабатывающих очень большую рабочую нагрузку, что делает "небольшие" потери производительности очень большими проблемами.

Бонусные баллы, если его можно извлечь для работы в одиночку без каких-либо зависимостей.

Answer 1

В одном из моих вопросов мне порекомендовали Apache Commons MultiMap: http://commons.apache.org/collections/api-3.2.1/org/apache/commons/collections/MultiHashMap.html

Это бесплатное программное обеспечение, так что вы можете, по крайней мере, получить исходный текст для его просмотра, а в зависимости от ситуации с лицензией вы можете изменить его или использовать отдельно.

Он использует ArrayList для внутреннего использования, но я думаю, что вы, вероятно, можете изменить его на использование HashSet или чего-то еще. Я бы посмотрел на createCollection(Collection coll) метод.

ОБНОВЛЕНИЕ: На самом деле HashMultiMap в Guava, похоже, уже о чем я говорил: https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Multimap.java

Я посмотрел на источник, и кажется, что каждая коллекция значений фактически поддерживается HashSet.

Answer 2

У меня было требование, где я должен был иметь Map<Comparable, Set<Comparable>> если вставка на карту выполняется одновременно, а также в соответствующем наборе, но после того, как ключ был использован на карте, его нужно было удалить, подумайте, что если задание выполняется каждые две секунды, которое потребляет все Set<Comparable> от конкретного ключа, но вставка должна быть полностью параллельной, чтобы большинство значений было буферизовано при запуске задания, вот моя реализация:

Примечание: я использую вспомогательный класс Maps от Guava для создания одновременных карт, также это решение эмулирует параллелизм Java на листинге 5.19:

import com.google.common.collect.MapMaker;

import java.util.concurrent.ConcurrentMap;

/**
 * Created by IntelliJ IDEA.
 * User: gmedina
 * Date: 18-Sep-2012
 * Time: 09:17:50
 */
public class LockMap<K extends Comparable>
{
  private final ConcurrentMap<K, Object> locks;

  public LockMap()
  {
    this(16, 64);
  }

  public LockMap(final int concurrencyLevel)
  {
    this(concurrencyLevel, 64);
  }

  public LockMap(final int concurrencyLevel, final int initialCapacity)
  {
    locks=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity).weakValues().makeMap();
  }

  public Object getLock(final K key)
  {
    final Object object=new Object();
    Object lock=locks.putIfAbsent(key, object);
    return lock == null ? object : lock;
  }

}


import com.google.common.collect.MapMaker;
import com.google.common.collect.Sets;

import java.util.Collection;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;

/**
 * A general purpose Multimap implementation for delayed processing and concurrent insertion/deletes.
 *
 * @param <K> A comparable Key
 * @param <V> A comparable Value
 */
public class ConcurrentMultiMap<K extends Comparable, V extends Comparable>
{
  private final int initialCapacity;
  private final LockMap<K> locks;
  private final ConcurrentMap<K, Set<V>> cache;

  public ConcurrentMultiMap()
  {
    this(16, 64);
  }

  public ConcurrentMultiMap(final int concurrencyLevel)
  {
    this(concurrencyLevel, 64);
  }

  public ConcurrentMultiMap(final int concurrencyLevel, final int initialCapacity)
  {
    this.initialCapacity=initialCapacity;
    cache=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity).makeMap();
    locks=new LockMap<K>(concurrencyLevel, initialCapacity);
  }

  public void put(final K key, final V value)
  {
    synchronized(locks.getLock(key)){
      Set<V> set=cache.get(key);
      if(set == null){
        set=Sets.newHashSetWithExpectedSize(initialCapacity);
        cache.put(key, set);
      }
      set.add(value);
    }
  }

  public void putAll(final K key, final Collection<V> values)
  {
    synchronized(locks.getLock(key)){
      Set<V> set=cache.get(key);
      if(set == null){
        set=Sets.newHashSetWithExpectedSize(initialCapacity);
        cache.put(key, set);
      }
      set.addAll(values);
    }
  }

  public Set<V> remove(final K key)
  {
    synchronized(locks.getLock(key)){
      return cache.remove(key);
    }
  }

  public Set<K> getKeySet()
  {
    return cache.keySet();
  }

  public int size()
  {
    return cache.size();
  }

}

Answer 3

Я использовал Google Guava в качестве замены Apache Commons, когда это возможно... Вот пример с его реализацией Multimap HashMultiMap, и обратите внимание, что значения карты - это коллекция значений вместо одной ссылки. Метод "contains()" используется для результата get(key).

private Multimap<Phase, ResultingState> phaseResults = HashMultimap.create();

/**
 * @param withState is the state to be verified.
 * @param onPhase is the phase to be verified.
 * @return Whether the given result was reported in the given phase.
 */
public boolean wasReported(ResultingState withState, Phase onPhase) {
    return phaseResults.containsKey(onPhase) && phaseResults.get(onPhase).contains(withState);
}

/**
 * @param resultingState is the resulting state.
 * @return Whether the given resulting state has ever been reported.
 */
public boolean anyReported(ResultingState resultingState) {
    return phaseResults.values().contains(resultingState);
}

Answer 4

Выбор будет во многом зависеть от того, что вы хотите сделать. Существует множество структур данных, и некоторые из них лучше других в определенных областях и наоборот.

Я мог бы рекомендовать вам потенциальных кандидатов. Если он полностью прочитан, ImmutableMultiMap может подойти.

Если вам нужно одновременное чтение / запись, я бы реализовал свою собственную мультикарту, возможно, используя ConcurrentHashMap и ConcurrentSkipListSet (вам нужно быть осторожным, потому что семантика между синхронизированной мультикартой и мультикартой, созданной таким образом с использованием неблокирующих структур данных, различается). Если вы используете ConcurrentSkipListSet, вы можете использовать бинарный поиск, и это быстрее, чем просто итерация.

Если у вас много строк, вы также можете начать с использования ConcurrentHashMap и синхронизированного списка. Это может значительно снизить конкуренцию, что может быть достаточно для решения проблемы с производительностью, и это просто.

Answer 5

Когда вы упоминаете, что "перебираете указанную большую карту, выбирая подходящие ключи", у меня возникает вопрос, используете ли вы лучшую структуру данных. Есть ли способ избежать этой итерации?

Обратите внимание, что Guava включает в себя несколько реализаций нескольких карт с различными характеристиками производительности. Как упомянул Zwei, ImmutableMultimap имеет лучшую производительность, чем изменяемые мультикарты. SetMultimaps быстрее, если ваш код проверяет, содержит ли мультикарта конкретное значение; в противном случае ArrayListMultimap работает лучше.