Java: есть ли другой вид связанного списка где-нибудь? - PullRequest
Новая
       53

Java: есть ли другой вид связанного списка где-нибудь?

0 голосов
/ 04 апреля 2011

Существует ли предварительно реализованный связанный список, который был бы реализован с использованием идентификаторов вместо индексов массива?

МОТИВАЦИЯ: здесь я хочу получить связанный список из ячеек ведьм, который можно удалить несколькими потоками в parellel. Проблема с Java LinkedList заключается в том, что ссылки являются индексными ссылками.

Чтобы уточнить: скажем, у меня есть три потока и LinkedList из трех ячеек. Поток номер один производит для ячейки номер один (или 0, но в любом случае ...), ... и поток номер три производит для ячейки номер 3. Таким образом, в основном потоки производят вещи для своих ячеек, которые работают как буферы. Теперь, если поток номер 2 удаляет ячейку номер два (по бизнес-логической причине), ссылка на поток № 3 меняется на # 2. Естественно, этого нельзя сделать, если поток № 3 все еще работает с ячейкой № 3, поэтому необходима синхронизация, и даже если поток № 3 в настоящее время не использует свою ячейку, потоку все равно нужно сообщить, что он будет использовать ячейку. №2 отныне.

Решение: если связанный список будет реализован с использованием идентификаторов вместо ссылок на индексы массива, другие потоки никогда не увидят изменений, то есть ячейка номер два может быть безопасно удалена, поскольку поток № 3 будет использовать свою ячейку примерно так connectedlist.add (id 3, ячейка C) вместо этого добавить (индекс int, ячейка C).

Полагаю, что-то подобное уже где-то реализовано, но через некоторое время поисковика я не смог его найти. ВСЕ ПОМОЩЬ ЦЕНЫ!

Ответы [ 3 ]

3 голосов
/ 04 апреля 2011

LinkedHashMap кажется уместным, но я не уверен, полностью ли это соответствует вашему сценарию.Попытайся.Это HashMap, поэтому вы получаете доступ к элементам с помощью их ключей.

2 голосов
/ 04 апреля 2011

Связанные списки относятся к «Далее», работа с индексами в связанных списках может привести к снижению производительности при попытке доступа к элементу с индексом «N», когда «N» - большое число.

Почемутебе нужен список?порядок это большая проблема?Почему вы не можете использовать карту?

1 голос
/ 04 апреля 2011

Есть только два способа говорить об обычном элементе List по позиции.

  • Вы можете ссылаться на элемент списка по его индексу; то есть по количеству шагов, необходимых для достижения элемента, начиная с первого элемента. (Вот что означает List.get(int).) Проблема в том, что индекс элемента может измениться из-за других операций в списке.

  • Вы можете ссылаться на элемент списка, используя Iterator в качестве курсора. Некоторые другие операции могут удалить элемент до или после того, на который вы просматриваете, но это не должно влиять на текущую, если вы используете соответствующую реализацию List. (Если вы используете непараллельный список, вы, вероятно, получите ConcurrentModification исключения.)

Суть в том, что если вы беспокоитесь об обновлениях других потоков, приводящих к изменению индексов, не используйте индексы. Используйте Iterator и реализацию коллекции, которая поддерживает одновременные модификации; например CopyOnWriteArrayList, ConcurrentLinkedQueue или один из других ... в зависимости от того, что именно вы пытаетесь сделать и что вам требуется.

Я не знаю ни одной реализации List, которая позволяла бы вам блокировать обновления, которые могли бы изменить положение элемента. API списков не поддерживают подобные вещи.

Кроме того:

  • блокировка такого списка может стать главным узким местом параллелизма, а
  • с использованием get(int) или set(int, Object) на LinkedList не масштабируется.
...