Почему Java 8 не включает неизменяемые коллекции?

130

Команда Java проделала огромную работу по устранению барьеров для функционального программирования в Java 8. В частности, изменения в коллекциях java.util делают большую работу по объединению преобразований в очень быстрые потоковые операции. Учитывая, как хорошо они проделали работу, добавив первоклассные функции и функциональные методы к коллекциям, почему они полностью не смогли обеспечить неизменные коллекции или даже неизменные интерфейсы коллекций?

Без изменения какого-либо существующего кода команда Java может в любое время добавить неизменяемые интерфейсы, такие же как изменяемые, минус методы "set" и заставить существующие интерфейсы расширяться от них, например так:

                  ImmutableIterable
     ____________/       |
    /                    |
Iterable        ImmutableCollection
   |    _______/    /          \   \___________
   |   /           /            \              \
 Collection  ImmutableList  ImmutableSet  ImmutableMap  ...
    \  \  \_________|______________|__________   |
     \  \___________|____________  |          \  |
      \___________  |            \ |           \ |
                  List            Set           Map ...

Конечно, такие операции, как List.add () и Map.put (), в настоящее время возвращают логическое или предыдущее значение для данного ключа, чтобы указать, была ли операция успешной или неудачной. Неизменяемые коллекции должны обрабатывать такие методы как фабрики и возвращать новую коллекцию, содержащую добавленный элемент, что несовместимо с текущей подписью. Но это можно обойти, используя другое имя метода, например, ImmutableList.append () или .addAt () и ImmutableMap.putEntry (). Результирующая многословность будет более чем перевешена преимуществами работы с неизменяемыми коллекциями, а система типов предотвратит ошибки вызова неправильного метода. Со временем старые методы могут устареть.

Победы неизменных коллекций:

  • Простота - рассуждения о коде проще, когда базовые данные не меняются.
  • Документация - если метод принимает неизменяемый интерфейс коллекции, вы знаете, что он не собирается изменять эту коллекцию. Если метод возвращает неизменную коллекцию, вы знаете, что не можете ее изменить.
  • Параллелизм - неизменяемые коллекции можно безопасно разделять между потоками.

Как человеку, который пробовал языки, которые предполагают неизменность, очень трудно вернуться на Дикий Запад с безудержной мутацией. Коллекции Clojure (абстракция последовательностей) уже имеют все, что обеспечивают коллекции Java 8, плюс неизменяемость (хотя, возможно, использование дополнительной памяти и времени из-за синхронизированных списков ссылок вместо потоков). В Scala есть как изменяемые, так и неизменяемые коллекции с полным набором операций, и, хотя эти операции нетерпеливы, вызов .iterator дает ленивое представление (и существуют другие способы их ленивой оценки). Я не понимаю, как Java может продолжать конкурировать без неизменных коллекций.

Может кто-нибудь указать мне на историю или обсуждение этого? Конечно, это где-то публично.

java history immutability collections GlenPeterson
источник
9
Связанный с этим - Ayende недавно написал в блоге о коллекциях и неизменных коллекциях в C #, с тестами. ayende.com/blog/tags/performance - tl; dr - неизменность медленная .
Одед
20
с вашей иерархией я могу дать вам ImmutableList и затем изменить его на вас, когда вы не ожидаете, что это может сломать много вещей, поскольку у вас есть только constколлекции
ratchet freak
18
@ Oded Неизменность медленная, но блокировка тоже. Так же ведется история. Простота / правильность стоит скорости во многих ситуациях. С небольшими коллекциями скорость не проблема. Анализ Ayende основан на предположении, что вам не нужны история, блокировка или простота, и что вы работаете с большим набором данных. Иногда это правда, но это не лучшая вещь. Есть компромиссы.
ГленПетерсон
5
@GlenPeterson - вот для чего нужны защитные копии Collections.unmodifiable*(). но не относитесь к ним как к неизменным, когда это не так
трещотка урод
13
А? Если ваша функция принимает ImmutableListв этой диаграмме, люди могут перейти в изменчивый List? Нет, это очень плохое нарушение LSP.
Теластин

Ответы:

113

Потому что неизменные коллекции абсолютно требуют обмена, чтобы быть пригодными для использования. В противном случае каждая отдельная операция помещает в кучу целый другой список. Языки, которые являются полностью неизменяемыми, такие как Haskell, генерируют удивительное количество мусора без агрессивной оптимизации и обмена. Наличие коллекции, которую можно использовать только с <50 элементами, не стоит помещать в стандартную библиотеку.

Более того, неизменяемые коллекции часто имеют принципиально иные реализации, чем их изменяемые аналоги. Например ArrayList, эффективный неизменяемый объект ArrayListвообще не будет массивом! Он должен быть реализован с помощью сбалансированного дерева с большим коэффициентом ветвления, Clojure использует 32 IIRC. Делать изменчивые коллекции «неизменяемыми», просто добавляя функциональное обновление, является ошибкой производительности, равно как и утечка памяти.

Кроме того, совместное использование не является жизнеспособным в Java. Java предоставляет слишком много неограниченных хуков к изменчивости и равенству ссылок, чтобы сделать совместное использование «просто оптимизацией». Возможно, вас немного раздражит, если вы сможете изменить элемент в списке и понять, что вы только что изменили элемент в других 20 версиях этого списка.

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

jozefg
источник
21
Мой пример говорил о неизменных интерфейсах . Java может предоставить полный набор как изменчивых, так и неизменных реализаций этих интерфейсов, которые позволят получить необходимые компромиссы. Программист должен выбрать изменяемый или неизменяемый в зависимости от ситуации. Программисты должны знать, когда использовать List против Set сейчас. Обычно вам не нужна изменяемая версия, пока у вас не возникнет проблема с производительностью, и тогда она может понадобиться только как сборщик. В любом случае наличие неизменяемого интерфейса само по себе является победой.
ГленПетерсон
4
Я снова читаю ваш ответ и думаю, что вы говорите, что у Java есть фундаментальное допущение изменчивости (например, Java-бины), и что коллекции являются лишь верхушкой айсберга, и удаление этого не решит основную проблему. Действительный пункт. Я мог бы принять этот ответ и ускорить мое принятие Scala! :-)
ГленПетерсон
8
Я не уверен, что неизменные коллекции требуют умения делиться общими частями, чтобы быть полезными. Самый распространенный неизменяемый тип в Java, неизменяемый набор символов, используемый для предоставления общего доступа, но больше не позволяет. Ключевым моментом, который делает его полезным, является возможность быстро копировать данные из Stringв StringBuffer, манипулировать им, а затем копировать данные в новый неизменяемый String. Использование такого шаблона с наборами и списками может быть так же хорошо, как использование неизменяемых типов, которые предназначены для облегчения производства слегка измененных экземпляров, но могут быть еще лучше ...
суперкат
3
Вполне возможно сделать неизменную коллекцию в Java, используя совместное использование. Элементы, хранящиеся в коллекции, являются ссылками, и их ссылки могут быть видоизменены - ну и что? Такое поведение уже нарушает существующие коллекции, такие как HashMap и TreeSet, но они реализованы в Java. И если несколько коллекций содержат ссылки на один и тот же объект, вполне ожидаемо, что изменение объекта вызовет изменение, видимое при просмотре из всех коллекций.
Секрет Соломонова
4
jozefg, вполне возможно реализовать эффективные неизменяемые коллекции на JVM со структурным разделением. Scala и Clojure имеют их как часть своей стандартной библиотеки, обе реализации основаны на HAMT Фила Багвелла (Hash Array Mapped Trie). Ваше утверждение о том, что Clojure реализует неизменные структуры данных со сбалансированными деревьями, совершенно неверно.
Сезм
78

Изменяемая коллекция не является подтипом неизменной коллекции. Вместо этого изменчивые и неизменные коллекции являются родственными потомками читаемых коллекций. К сожалению, понятия «читабельный», «только для чтения» и «неизменяемый», похоже, сливаются воедино, хотя они означают три разные вещи.

  • Доступный для чтения базовый класс коллекции или тип интерфейса обещает, что можно читать элементы, и не предоставляет никаких прямых средств изменения коллекции, но не гарантирует, что код, получающий ссылку, не может привести или манипулировать ею таким образом, чтобы разрешить изменение.

  • Интерфейс коллекции только для чтения не включает никаких новых членов, но должен быть реализован только классом, который обещает, что нет способа манипулировать ссылкой на него таким образом, чтобы изменить коллекцию или получить ссылку на что-либо это могло бы сделать это. Это, однако, не обещает, что коллекция не будет изменена чем-то другим, имеющим ссылку на внутренние компоненты. Обратите внимание, что интерфейс коллекции, доступный только для чтения, может не быть в состоянии предотвратить реализацию изменяемыми классами, но может указывать, что любая любая реализация или класс, производный от реализации, который допускает мутацию, должны рассматриваться как «незаконная» реализация или производная реализации ,

  • Неизменяемая коллекция - это коллекция, которая всегда будет содержать одни и те же данные, пока существует какая-либо ссылка на них. Любая реализация неизменяемого интерфейса, который не всегда возвращает одни и те же данные в ответ на конкретный запрос, нарушается.

Иногда полезно иметь сильно связанные изменяемые и неизменяемые типы коллекций , которые и реализуют или вытекают из того же «читаемого» типа и имеют читаемые типа включают в себя AsImmutable, AsMutableи AsNewMutableметоду. Такой дизайн может позволить коду, который хочет сохранить данные в коллекции для вызова AsImmutable; этот метод сделает защитную копию, если коллекция изменчива, но пропустите копию, если она уже неизменна.

Supercat
источник
1
Отличный ответ. Неизменяемые коллекции могут дать вам довольно надежную гарантию, связанную с безопасностью потоков и тем, как вы можете рассуждать о них с течением времени. Доступные для чтения / только для чтения коллекции нет. Фактически, чтобы соблюдать принцип подстановки liskov, Read-Only и Immutable, вероятно, должны быть абстрактным базовым типом с конечным методом и закрытыми членами, чтобы гарантировать, что ни один производный класс не сможет уничтожить гарантию, данную типом. Или они должны быть полностью конкретного типа, которые либо обертывают коллекцию (только для чтения), либо всегда принимают защитную копию (неизменяемую). Вот как это делает guava ImmutableList.
Лоран Бурго-Рой
1
@ LaurentBourgault-Roy: Есть преимущества как для закрытых, так и для наследуемых неизменяемых типов. Если кто-то не хочет позволить незаконному производному классу нарушать свои инварианты, запечатанные типы могут предложить защиту от этого, в то время как наследуемые классы не предлагают ни одного. С другой стороны, для кода, который знает что-то о данных, которые он содержит, возможно, будет гораздо более компактно хранить его , чем типу, который ничего не знает об этом. Рассмотрим, например, тип ReadableIndexedIntSequence, который инкапсулирует последовательность int, с методами getLength()и getItemAt(int).
суперкат
1
@ LaurentBourgault-Roy: Учитывая ReadableIndexedIntSequence, можно создать экземпляр неизменяемого типа на основе массива, скопировав все элементы в массив, но предположим, что конкретная реализация просто вернула 16777216 длины и ((long)index*index)>>24для каждого элемента. Это была бы законная неизменная последовательность целых чисел, но копирование ее в массив было бы огромной тратой времени и памяти.
суперкат
1
Я полностью согласен. Мое решение дает вам правильность (до некоторой степени), но чтобы добиться производительности с большим набором данных, вы должны иметь постоянную структуру и дизайн для неизменности с самого начала. Для небольшой коллекции, хотя вы можете время от времени брать непреложную копию. Я помню, что Scala провела некоторый анализ различных программ и обнаружила, что примерно 90% созданных списков имеют длину не более 10 элементов.
Лоран Бурго-Рой
1
@ LaurentBourgault-Roy: Фундаментальный вопрос заключается в том, доверяет ли человек людям не создавать сломанные реализации или производные классы. Если это так, и если интерфейсы / базовые классы предоставляют методы asMutable / asImmutable, то можно улучшить производительность на много порядков [например, сравнить стоимость вызова asImmutableэкземпляра определенной выше последовательности и стоимость конструирования неизменяемая копия на основе массива. Я бы сказал, что иметь интерфейсы, определенные для таких целей, вероятно, лучше, чем пытаться использовать специальные подходы; ИМХО, самая большая причина ...
суперкат
15

Java Collections Framework предоставляет возможность создавать версию коллекции только для чтения с помощью шести статических методов в классе java.util.Collections :

Как кто-то указал в комментариях к исходному вопросу, возвращенные коллекции не могут считаться неизменными, потому что даже если коллекции нельзя изменить (никакие члены не могут быть добавлены или удалены из такой коллекции), фактические объекты, на которые ссылается коллекция могут быть изменены, если их тип объекта позволяет это.

Однако эта проблема останется вне зависимости от того, возвращает ли код один объект или неизменяемую коллекцию объектов. Если тип позволяет мутировать его объекты, то это решение было принято при разработке типа, и я не вижу, как изменение JCF могло бы изменить это. Если важна неизменность, то члены коллекции должны быть неизменяемого типа.

Arkanon
источник
4
Дизайн немодифицируемых коллекций был бы значительно улучшен, если бы обертки включали указание того, была ли обернутая вещь уже неизменной, и были ли immutableListдругие фабричные методы, которые возвращали бы оболочку, доступную только для чтения, вокруг копии переданного объекта. список, если переданный список не был уже неизменным . Было бы легко создать пользовательские типы, подобные этому, но для одной проблемы: у joesCollections.immutableListметода не было бы способа распознать, что ему не нужно копировать возвращаемый объект fredsCollections.immutableList.
суперкат
8

Это очень хороший вопрос. Мне нравится развлекать идею о том, что из всего кода, написанного на Java и работающего на миллионах компьютеров по всему миру, каждый день, круглосуточно, около половины всех тактов должно быть потрачено впустую, делая только безопасные копии коллекций, которые возвращается функциями. (И сбор мусора в этих коллекциях за миллисекунды после их создания.)

Процент Java-программистов знают о существовании unmodifiableCollection()семейства методов Collectionsкласса, но даже среди них многие просто не беспокоятся об этом.

И я не могу винить их: интерфейс, который притворяется читаемым и пишущим, но выдает « UnsupportedOperationExceptionесли», если вы допустите ошибку, вызывая любой из его методов «записи», - это довольно злая вещь!

Теперь интерфейс, подобный Collectionкоторому будет отсутствовать add(), remove()и clear()методы не будут интерфейсом «ImmutableCollection»; это будет интерфейс «UnmodifiableCollection». Фактически, никогда не может быть интерфейса «ImmutableCollection», потому что неизменность является природой реализации, а не характеристикой интерфейса. Я знаю, это не очень ясно; позволь мне объяснить.

Предположим, кто-то вручает вам такой интерфейс коллекции только для чтения; безопасно ли передавать его в другой поток? Если бы вы точно знали, что это действительно неизменная коллекция, тогда ответом будет «да»; К сожалению, так как интерфейс, вы не знаете , как это реализовано, так что ответ должен быть не : для всех вы знаете, это может быть неизменяемым (для вас) вида коллекции , которая на самом деле изменяемая, (например, то, что вы получаете Collections.unmodifiableCollection()), поэтому попытка чтения из него, пока другой поток его модифицирует, приведет к чтению поврежденных данных.

Итак, по сути, вы описали набор не «неизменяемых», а «неизменяемых» интерфейсов коллекций. Важно понимать, что «немодифицируемый» просто означает, что любой, у кого есть ссылка на такой интерфейс, не может изменять базовую коллекцию, и они предотвращаются просто потому, что в интерфейсе отсутствуют какие-либо методы модификации, а не потому, что базовая коллекция обязательно является неизменной. Основная коллекция вполне может быть изменчивой; Вы не знаете и не можете это контролировать.

Чтобы иметь неизменные коллекции, они должны быть классами , а не интерфейсами!

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

Таким образом, чтобы иметь полный набор коллекций на языке Java (или на любом другом декларативном императивном языке), нам потребуется следующее:

  1. Набор неизменяемых коллекционных интерфейсов .

  2. Набор интерфейсов изменяемой коллекции , расширяющих неизменяемые.

  3. Набор классов изменяемой коллекции, реализующих изменяемые интерфейсы, а также, кроме того, немодифицируемые интерфейсы.

  4. Набор неизменяемых классов коллекций , реализующих неизменяемые интерфейсы, но в основном передаваемых как классы, чтобы гарантировать неизменность.

Я реализовал все вышеперечисленное для удовольствия, и я использую их в проектах, и они работают как шарм.

Причина, по которой они не являются частью среды выполнения Java, вероятно, заключается в том, что считалось, что это будет слишком / слишком сложно / слишком сложно для понимания.

Лично я думаю, что то, что я описал выше, даже недостаточно; Еще одна вещь, которая кажется необходимой, это набор изменяемых интерфейсов и классов для структурной неизменности . (Который может быть просто назван "Жестким", потому что префикс "StructurallyImmutable" слишком длинный).

Майк Накис
источник
Хорошие моменты. Две детали: 1. Для неизменяемых коллекций требуются определенные сигнатуры методов, в частности (с использованием списка в качестве примера): List<T> add(T t)- все методы-мутаторы должны возвращать новую коллекцию, которая отражает изменение. 2. К счастью или хуже, интерфейсы часто представляют собой контракт в дополнение к подписи. Сериализуемый является одним из таких интерфейсов. Точно так же Comparable требует, чтобы вы правильно реализовали свой compareTo()метод для правильной работы и в идеале были совместимы с equals()и hashCode().
ГленПетерсон
О, я даже не имел в виду неизменяемость при копировании. То, что я написал выше, относится к простым простым неизменным коллекциям, у которых действительно нет подобных методов add(). Но я полагаю, что если бы методы-мутаторы были добавлены в неизменяемые классы, то они должны были бы также возвращать неизменяемые классы. Так что, если там скрывается проблема, я ее не вижу.
Майк Накис
Является ли ваша реализация общедоступной? Я должен был спросить это несколько месяцев назад. Во всяком случае, моя: github.com/GlenKPeterson/UncleJim
ГленПетерсон
4
Suppose someone hands you such a read-only collection interface; is it safe to pass it to another thread?Предположим, кто-то передает вам экземпляр изменяемого интерфейса коллекции. Безопасно ли вызывать какой-либо метод для него? Вы не знаете, что реализация не зацикливается вечно, не генерирует исключение или полностью игнорирует контракт интерфейса. Почему двойной стандарт специально для неизменных коллекций?
Довал
1
ИМХО, ваши рассуждения против изменчивых интерфейсов неверны. Вы можете написать изменяемую реализацию неизменяемых интерфейсов, и тогда она сломается. Конечно. Но это твоя вина, так как ты нарушаешь контракт. Просто прекрати это делать. Это ничем не отличается от разбиения SortedSetна подклассы набора с несоответствующей реализацией. Или мимоходом непоследовательным Comparable. При желании можно сломать почти все. Я думаю, именно это @Doval подразумевал под "двойными стандартами".
Maaartinus
2

Неизменяемые коллекции могут быть глубоко рекурсивными, по сравнению с другими, и не чрезмерно неэффективными, если равенство объектов осуществляется с помощью secureHash. Это называется меркльский лес. Это может быть для каждой коллекции или внутри их частей, например (самобалансирующееся двоичное) дерево AVL для отсортированной карты.

Если все java-объекты в этих коллекциях не имеют уникального идентификатора или какой-либо цепочки битов для хэширования, коллекция не имеет хэша для уникального имени.

Пример: на моем ноутбуке 4x1,6 ГГц я могу запускать 200K sha256s в секунду наименьшего размера, который умещается в 1 цикле хеширования (до 55 байт), по сравнению с 500K-операциями HashMap или 3M-операциями в хеш-таблице long. 200K / log (collectionSize) новых коллекций в секунду достаточно быстры для некоторых вещей, где важна целостность данных и анонимная глобальная масштабируемость.

Бен Рэйфилд
источник
-3

Представление. Коллекции по своей природе могут быть очень большими. Копирование 1000 элементов в новую структуру с 1001 элементом вместо вставки одного элемента просто ужасно.

Параллелизм. Если у вас запущено несколько потоков, они могут захотеть получить текущую версию коллекции, а не версию, которая была передана 12 часов назад, когда поток начался.

Место хранения. С неизменными объектами в многопоточной среде вы можете получить десятки копий «одного и того же» объекта в разные моменты его жизненного цикла. Не имеет значения для объекта «Календарь» или «Дата», но когда он содержит коллекцию из 10 000 виджетов, это убьет вас.

Джеймс Андерсон
источник
12
Неизменяемые коллекции требуют копирования только в том случае, если вы не можете поделиться ими из-за распространяющейся изменчивости, как в Java. Параллельность обычно проще с неизменяемыми коллекциями, потому что они не требуют блокировки; и для наглядности у вас всегда может быть изменяемая ссылка на неизменяемую коллекцию (обычно в OCaml). Благодаря обмену обновления могут быть практически бесплатными. Вы можете сделать логарифмически больше выделений, чем с изменяемой структурой, но при обновлении многие устаревшие подобъекты могут быть немедленно освобождены или использованы повторно, так что вы не обязательно будете иметь более высокие затраты памяти.
Джон Перди
4
Пара проблем. Коллекции в Clojure и Scala являются неизменными, но поддерживают легкие копии. Добавление элемента 1001 означает копирование менее 33 элементов, а также создание нескольких новых указателей. Если вы разделяете изменяемую коллекцию между потоками, при ее изменении у вас возникают проблемы с синхронизацией. Операции типа "удалить ()" кошмарны. Кроме того, неизменяемые коллекции могут создаваться изменчиво, а затем копироваться один раз в неизменяемую версию, безопасную для совместного использования в потоках.
ГленПетерсон
4
Использование параллелизма в качестве аргумента против неизменности необычно. Дублирует также.
Том Хотин - tackline
4
Немного недоволен голосами против. ОП спросила, почему они не внедрили неизменные коллекции, и я предоставил взвешенный ответ на этот вопрос. Предположительно, единственный приемлемый ответ среди модников - «потому что они допустили ошибку». На самом деле у меня есть некоторый опыт в том, чтобы реструктурировать большие куски кода, используя в противном случае отличный класс BigDecimal, просто из-за плохой производительности из-за неизменности в 512 раз по сравнению с использованием двойного плюс некоторого бездействия для исправления десятичных знаков.
Джеймс Андерсон
3
@JamesAnderson: Мои проблемы с вашим ответом: «Производительность» - вы могли бы сказать, что реальные неизменяемые коллекции всегда реализуют некоторую форму совместного использования и повторного использования, чтобы точно избежать проблемы, которую вы описываете. «Параллельность» - аргумент сводится к «Если вам нужна изменчивость, то неизменный объект не работает». Я имею в виду, что если существует понятие «последняя версия того же самого», то что-то должно мутировать, либо сама вещь, либо что-то, что владеет вещью. А в «Хранилище» вы, похоже, говорите, что изменчивость иногда нежелательна.
jhominal