senior
Напишите минимальный неблокирующий ArrayList (всего четыре метода — add(), get(), remove(), size())
Реализация потокобезопасного ArrayList без использования блокировок. Подход — copy-on-write: при каждой модификации создаётся новая копия внутреннего массива, а ссылка на массив обновляется атомарно через volatile.
Код: copy-on-write ArrayList
class NonBlockingArrayList<T> {
private volatile Object[] content = new Object[0];
NonBlockingArrayList<T> add(T item) {
return add(content.length, item);
}
NonBlockingArrayList<T> add(int index, T item) {
if (index < 0) {
throw new IllegalArgumentException();
}
boolean needsModification = index > content.length - 1;
if (!needsModification) {
if (item == null) {
needsModification = content[index] != null;
} else {
needsModification = !item.equals(content[index]);
}
}
if (needsModification) {
final Object[] renewed = Arrays.copyOf(content, Math.max(content.length, index + 1));
renewed[index] = item;
content = renewed;
}
return this;
}
NonBlockingArrayList<T> remove(int index) {
if (index < 0 || index >= content.length) {
throw new IllegalArgumentException();
}
int size = content.length - 1;
final Object[] renewed = new Object[size];
System.arraycopy(content, 0, renewed, 0, index);
if (index + 1 < size) {
System.arraycopy(content, index + 1, renewed, index, size - index);
}
content = renewed;
return this;
}
@SuppressWarnings("unchecked")
T get(int index) {
return (T) content[index];
}
int size() {
return content.length;
}
}
Принцип работы:
- Чтение (
get,size) — доступ кvolatile-ссылке, без блокировки и копирования. Очень дёшево. - Запись (
add,remove) — создание нового массива, копирование элементов, обновлениеvolatile-ссылки. Дорого при большом массиве.
Ограничения:
- Данная реализация не является строго потокобезопасной при конкурентных записях (два потока могут одновременно прочитать
content, создать свои копии и последний перезапишет результат первого). Для полной потокобезопасности нужен CAS-цикл сAtomicReferenceили блокировка на запись, как вCopyOnWriteArrayListиз JDK. - Аналог JDK —
java.util.concurrent.CopyOnWriteArrayList, который используетReentrantLockдля защиты операций записи.
На собеседовании важно понимать trade-off: copy-on-write идеален для сценариев «много чтений, редкие записи» (списки подписчиков, кэши конфигурации), но плох для часто изменяемых списков.