一种简单的方法是仅使用

A simple approach would be to just use a read-write lock ([Reentrant]ReadWriteLock), so many threads could read concurrently, but once someone gets the write lock, nobody else can access the list.

或者您可以做一些与您的想法类似的事情:每个插槽一个读写锁+一个全局(结构")读写锁+一个用于跟踪 j> = i的变量案例.所以:

Or you could do something somewhat similar to your idea: one read-write lock for each slot + a global ("structural") read-write lock + a variable to keep track of the j >= i cases. So:

• 要访问(读取或写入)任何内容，线程至少需要全局读取锁.
• 只有试图进行结构更改(更改大小的线程)的线程会获得全局写锁定，但只会设置 int ModifyingFrom 变量，以指示从此处开始的所有位置均被锁定"( j> = i 情况).设置 modifyingFrom 后，您进行降级(请参见文档)从写到读锁定，让其他人可以访问列表.
• 任何试图执行任何非结构性更改的线程，一旦持有全局读取锁，就会检查其要执行的操作是否与 modifyingFrom 的当前值冲突.如果存在冲突，请休眠直到设置 modifyingFrom 的线程完成并通知正在等待的每个人.此检查必须同步(仅在某些对象上使用 synchronized(obj))，以便在发生冲突的线程之前 obj.notify()不会发生结构更改线程调用 obj.wait()并永远休眠(持有全局读取锁！).:(
• 您应该具有 boolean structureChangeHappening = false 或将 modifyingFrom 设置为某些 x>< list size> (当没有结构变化发生时)(然后，您只需检查 i< modifiedFrom 到 get()或 update()).完成结构更改的线程将 modifyingFrom 设置回该值，并且在此处必须进行同步以通知等待的线程.
• 一个想要在已经发生结构更改的线程将等待，因为它需要全局写锁，并且至少一个线程具有全局读锁.实际上，它会一直等到根本没有人访问该列表.
• 如果有

• To access (read or write) anything, a thread needs at least the global read lock.
• Only threads trying to make structural changes (the ones that change the size) get the global write lock, but only to set an int modifyingFrom variable indicating all positions from there on are "locked" (the j >= i cases). After setting modifyingFrom, you downgrade (see docs) from write to read lock, letting others access the list.
• Any thread trying to do anything that isn't a structural change, once holding the global read lock, checks if what it wants to do conflicts with the current value of modifyingFrom. If there's a conflict, sleep until the thread who has set modifyingFrom finishes and notifies everybody who is waiting. This check must be synchronized (just use synchronized (obj) on some object) so the structure-changing thread doesn't happen to obj.notify() before the conflicting thread calls obj.wait() and sleeps forever (holding the global read lock!). :(
• You should either have a boolean structuralChangeHappening = false or set modifyingFrom to some x > <list size> when no structural changes are happening (then you can just check that i < modifyingFrom to get() or update()). A thread finishing a structural change sets modifyingFrom back to this value and here's where it has to synchronize to notify waiting threads.
• A thread wanting to make a structural change when one is already happening will wait because it needs the global write lock and at least one thread has the global read lock. In fact, it will wait until nobody is accessing the list at all.
• A thread allocating a new (bigger... or smaller, if you had a trimToSize() or something) array would hold the global write lock during the entire operation.

我倾向于认为并不需要全局读写锁，但是最后两点证明了这一点.

I was tempted to think the global read-write lock wasn't really necessary, but the last two points justify it.

一些示例情况:

• 一些线程尝试获取 get(i)(每个线程都带有 i ，无论是否唯一):每个线程都将获得全局读取锁，然后第 i 个读锁，然后读取位置，没有人会等待.
• 相同情况，其他线程尝试 update([index =] i，element)::如果没有相等的 i ，没有人会等待.否则，将仅等待写线程或读冲突位置的线程.
• 线程 t 启动 insert([index =] 5，element)，其他线程尝试 get(i):一旦 t 设置了 modifyingFrom = 5 并释放了全局写锁，所有读取的线程都将获得全局读锁，然后检查 modifyingFrom.那些 i<modifyFrom 只是获得插槽的(读取)锁；其他的则等待直到 insert(5)完成并通知，然后获得插槽的锁定.
• 一个线程启动一个 add()并需要分配一个新数组:一旦获得全局写锁，其他人就无法完成任何操作.
• 列表的大小为7，一个线程 t_a 调用 add(element)，另一个线程 t_g 调用 get([index =] 7):
  • 如果 t_a 碰巧首先获得了全局写锁，则会设置 modifyingFrom = 7 ，并在释放锁后，立即设置 t_g 获取全局读取锁，看到 index(= 7)> = ModifyingFrom 并休眠直到 t_a 完成并通知它.
  • 如果 t_g 首先获得全局读取锁定，则它将检查 7<ModifyingFrom ( modifyingFrom>< list size>(== 7)，在示例之前的第4点)，然后抛出异常，因为 7> =< list size> 释放锁定后！然后， t_a 可以获取全局写锁定并正常进行.
  • Some threads trying to get(i) (each with it's i, unique or not): each one would get the global read lock, then the ith read lock, then read the position, and nobody would wait at all.
  • The same case with additional threads trying to update([index =] i, element): if there are no equal is, nobody will wait. Otherwise, only the thread writing or the threads reading the conflicting position will wait.
  • A thread t starts an insert([index =] 5, element), and other threads try to get(i): Once t has set modifyingFrom = 5 and released the global write lock, all threads reading get the global read lock, then check modifyingFrom. Those with i < modifyingFrom just get the (read) lock of the slot; the others wait until the insert(5) finishes and notifies, then get the lock of the slot.
  • A thread starts an add() and needs to allocate a new array: Once it gets the global write lock, nobody else can do anything until it has finished.
  • The size of the list is 7, a thread t_a calls add(element) and another thread t_g calls get([index =] 7):
    • If t_a happens to get the global write lock first, it sets modifyingFrom = 7, and once it has released the lock, t_g gets the global read lock, sees that index (= 7) >= modifyingFrom and sleeps until t_a finishes and notifies it.
    • If t_g gets the global read lock first, it checks that 7 < modifyingFrom (modifyingFrom > <list size> (== 7), 4th point before the examples), then throws an exception because 7 >= <list size> after releasing the lock! Then t_a is able to get the global write lock and proceeds normally.

    记住对 modifyingFrom 的访问必须同步.

    Remembering that accesses to modifyingFrom must be synchronized.

    您说过只需要执行五个操作，但是如果您想要一个迭代器，它可以检查是否通过其他方式(不是迭代器本身)更改了某些东西，就像标准类所做的那样.

    You said you want only that five operations, but if you wanted an iterator, it could check if something changed by other means (not the iterator itself), like standard classes do.

    现在，我不知道在什么条件下这会比其他方法更好.另外，请考虑在实际应用程序中可能需要更多限制，因为这只能确保一致性:如果尝试读取和写入相同的位置，则读取可能发生在写入之前或之后.也许有像 tryUpdate(int，E)这样的方法才有意义，该方法仅在调用该方法时没有发生冲突的结构变化或 tryUpdate(int，E，谓词< ArrayList>)，仅当列表处于满足谓词的状态(应该仔细定义它，以免引起死锁)时，它才能工作.

    Now, I don't know under which conditions exactly this would be better than other approaches. Also, consider that you may need more restrictions in a real application, because this should ensure only consistency: if you try to read and write the same position, the read can happen before or after the write. Maybe it would make sense to have methods like tryUpdate(int, E), that only does something if no conflicting structural changes are happening when the method is called, or tryUpdate(int, E, Predicate<ArrayList>), which only does its work if the list is in a state that satisfies the predicate (which should be defined carefully not to cause deadlocks).

    如果我错过了什么，请告诉我.可能会有很多极端情况.:)

    Please let me know if I missed something. There may be lots of corner cases. :)