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

Question

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

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

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

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

EDIT:

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

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

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

Answer 1

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

Answer 2

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

1. Запись LHM только с разрешенным порядком вставки.
2. Переключение на ConcurrentHashMap в качестве хеш-таблицы.
3. Защита #put()/ #putIfAbsent() / #remove() с блокировкой.
4. Сделать поле «next» изменчивым.

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

Answer 3

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

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

Answer 4

Использование Collections#synchronizedMap().

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

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

Answer 5

Хм, простой ответ - использовать монотонно увеличивающегося ключевого провайдера, над которым работает ваш 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) для вычисления размера (если только вы не разрешаете удаления, в этом случае их тоже учитывают, так что вы можете просто вычесть «все успешные удаления»). «из« всех успешных добавлений », где« успешный »означает, что запись была фактически создана или удалена).