Реализация параллельного LinkedHashMap

Я пытаюсь создать параллельный LinkedHashMap для многопоточной архитектуры.

Если я использую Collections#synchronizedMap(), мне нужно будет использовать синхронизированные блоки для итерации. Эта реализация приведет к последовательному добавлению элементов.

Если я использую ConcurrentSkipListMap, есть ли способ реализовать Comparator для сохранения последовательно, как хранятся в Linked List или queue.

Я хотел бы использовать java, встроенный вместо сторонних пакетов.

EDIT:

В этом параллельном LinkedHashMap, если ключи являются именем, я хочу поместить ключи в последовательность их прибытия. то есть новое значение будет добавлено либо в начале, либо в конце, но последовательно.

Во время итерации LinkedHashMap можно добавить новые записи или удалить. но итерация должна быть последовательностью, в которую были добавлены записи.

Я понимаю, что с помощью Collections#synchronizedMap() должен быть реализован синхронизированный блок для итерации, но будет ли изменяться карта (записи могут быть добавлены/удалены) во время ее повторения.

Ответ 1

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

Ответ 2

A LinkedHashMap имеет двусвязный список, проходящий через хэш-таблицу. FIFO только мутирует ссылки на запись (вставка или удаление). Это делает реализацию версии довольно простой.

Напишите LHM с разрешенным порядком размещения.
Переключитесь на ConcurrentHashMap как хэш-таблицу.
Защитите #put()/#putIfAbsent()/#remove() с помощью блокировки.
Сделать поле "next" изменчивым.

На итерации блокировки не требуется, так как вы можете спокойно следовать за "следующим" полем. Чтение может быть заблокировано, просто передав CHM на #get().

Ответ 3

Используйте Collections#synchronizedMap().

В соответствии с моим убеждением, если я использую Collections.synchronizedMap(), мне придется использовать синхронизированные блоки для getter/setter.

Это неверно. Вам нужно только синхронизировать итерацию в любом из видов (набор ключей, значения, набор записей). Также см. Документацию по API.

Ответ 4

До сих пор мой проект использовал LRUMap из Apache Collections, но он основан на SequencedHashMap. Коллекции предлагает ListOrderedMap, но ни один из них не является потокобезопасным.

Я переключился на MapMaker из Google Guava. Вы можете посмотреть CacheBuilder.

Ответ 5

Um, простой ответ заключался бы в использовании монотонно растущего ключевого провайдера, на котором работает ваш Comparator. Подумайте AtomicInteger, и каждый раз, когда вы вставляете, вы создаете новый ключ для сравнения. Если вы объединяете свой реальный ключ, вы можете сделать внутреннюю карту OrderedKey<MyRealKeyType>.

class OrderedKey<T> implements Comparable<OrderedKey<T>> {
  T realKey;
  int index;
  OrderedKey(AtomicInteger source, T key) {
    index = source.getAndIncrement();
    realKey = key;
  }
  public int compareTo(OrderedKey<T> other) {
    if (Objects.equals(realKey, other.realKey)) {
      return 0;
    }
    return index - other.index;
  }


}

Это избавит вас от необходимости создания специализированного компаратора и даст вам хороший метод O (1) для вычисления размера (если вы не разрешите удаление, и в этом случае также посчитайте их), поэтому вы можете просто вычесть "все успешные удаляет" из "всех успешных добавлений", где успешно означает, что запись была фактически создана или удалена).