Java：某处是否还有另一种链表？
是否有一个预先实现的链表可以使用 id 而不是数组索引来实现？
动机：我想在这里完成的是一个可以通过多个并行线程删除女巫单元的链表。 java的LinkedList的问题在于引用是索引引用。
澄清一下：假设我有三个线程和一个包含三个单元格的 LinkedList。线程 1 生成单元格 1（或 0，但无论如何...），...线程 3 生成单元格 3。所以基本上，线程向其单元格生成内容，这些单元格充当缓冲区。现在，如果线程 2 删除了单元格 2（出于业务逻辑原因），线程 #3 的引用将更改为 #2。当然，如果线程 #3 仍在单元 #3 上工作，则无法完成此操作，因此需要同步，即使线程 #3 当前未使用其单元，仍需要告知线程它将使用单元#2 从现在开始。
解决方案：如果使用 id 而不是数组索引引用来实现链表，则其他线程将永远不会看到更改，即可以安全地删除第二个单元格，因为线程 #3 将使用它的单元格，类似于 linkedlist.add (id 3, C cell) 而不是这样的 add(int index, C cell)。
我想类似的东西已经在某个地方实现了，但经过一段时间的谷歌搜索后，我找不到它。感谢所有帮助！
Is there a pre-implemented linked list out there that would have been implemented using id's instead of array indexes?
MOTIVATION: what I want to accomplish here is a linked list from witch cells can be removed by multiple threads in parellel. The problem with java's LinkedList is that the references are index ref's.
To clarify: let's say I have three threads and a LinkedList of three cells. Thread number one produces to cell number one (or 0 but anyway...), ...and thread number three produces to cell number 3. so basically threads produce stuff to their cells that work as buffers. Now if thread number 2 removes cell number two (for a business logical reason) the reference of thread #3 changes to #2. Naturally this can't be done if thread #3 is still working on cell #3, so synchronization is needed and even if thread #3 isn't currently using it's cell, the thread still needs to be told that it's going to use cell #2 from now on.
The solution: if the linked list would have been implemented using id's instead of array index references the other threads would never see the changes, i.e. the cell number two could be safely removed since thread #3 would use it's cell something like this linkedlist.add(id 3, C cell) instead of like this add(int index, C cell).
I guess something like this is already implemented somewhere but after a while of googling, I couldn't find it. ALL HELP APPRECIATED!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
LinkedHashMap似乎相关，但我不确定它是否完全适合您的场景。尝试一下。它是一个HashMap，因此您可以使用项目的键来访问项目。LinkedHashMapseems relevant, but I'm not sure if it completely fits your scenario. Try it. It's aHashMapso you are accessing items with their keys.链接列表指的是“下一个”，当“N”是一个很大的数字时，尝试访问索引“N”处的项目时，使用链接列表中的索引可能会导致性能不佳。
为什么需要清单？订单有这么大的问题吗？为什么不能使用地图？
Linked Lists refer to the 'Next', working with Indices in Linked Lists can lead to bad performance when attempting to access the item at index 'N' when 'N' is a large number.
Why do you need a list? is the order that much of an issue? Why can't you use a Map?
按位置讨论传统 List 元素的方式只有两种。
您可以通过索引引用列表元素；即从第一个元素开始到达该元素所需的步数。 （这就是
List.get(int)的含义。）问题是元素的索引可能会由于列表上的其他操作而更改。您可以使用
迭代器作为游标来引用列表元素。其他一些操作可能会删除您正在查看的元素之前或之后的元素，但这不会影响当前元素，前提是您使用适当的List实现。 （如果您使用非并发列表，则可能会遇到ConcurrentModification异常。）底线是，如果您担心其他线程的更新导致索引更改，请不要使用索引。使用迭代器和支持并发修改的集合实现；例如，
CopyOnWriteArrayList、ConcurrentLinkedQueue或其他之一...具体取决于您想要执行的操作以及您需要的保证。我不知道有任何 List 实现允许您锁定会更改元素位置的更新。 List API 不支持这种事情。
此外：
LinkedList上使用get(int)或set(int, Object)无法扩展。There are only two ways of talking about a conventional List element by position.
You can refer to a list element by its index; i.e. by the number of steps it takes to reach the element starting from the first element. (That is what
List.get(int)means.) The problem is that the index of an element can change due to other operations on the list.You can refer to a list element using an
Iteratoras a cursor. Some other operation could remove an element before or after the one you are looking at, but this shouldn't effect the current one, provided that you use an appropriateListimplementation. (If you use a non-concurrent list, you are likely to getConcurrentModificationexceptions.)The bottom line is that if you are worried about some other thread's updates causing indexes to change, don't use indexes. Use an
Iterator, and a collection implementation that supports concurrent modifications; e.g.CopyOnWriteArrayList,ConcurrentLinkedQueueor one of the others ... depending on exactly what you are trying to do and what guarantees you require.I'm not aware of any List implementation that allows you to lock out updates that would change an element's position. The List APIs don't support this kind of thing.
Besides:
get(int)orset(int, Object)on aLinkedListdoesn't scale.