Баг в дизайне коллекций

В этой статье речь пойдёт о фреймворке коллекций в Java. Относительно недавно (в 3 кв. 2023 года) эта библиотека вновь слегка обновилась. Я ознакомился с обновлениями, и скажу, что они меня разочаровали.

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

Итак случившееся обновление — добавление последовательных версий интерфейсов в коллекции, а именно SequencedCollection, SequencedSet и SequencedMap. Такие последовательные коллекции ещё во времена Рапиры, кажется, называли кортежами.

Казалось бы, замечательное изменение, все его давно ждали. Действительно, общего интерфейса, который бы описывал строго последовательную коллекцию, не было. Ну то есть при желании можно было пользоваться Списком, Двойной очередью или NavigableSet/NavigableMap. Но передать что-то более универсальное было сложно.

Сразу же обращает на себя внимание странная логика внедренцев изменения, если касаться SequencedSet: множество, или Set, — это изначально неупорядоченный набор со свойством единственности вхождения элементов. Прямо как в математическом смысле. List — упорядоченный список, Queue по идее тоже последовательна.
Что в таком случае может значить SequencedSet, то есть последовательный неупорядоченный набор?

В принципе, есть же NavigableSet/SortedSet, в которых есть порядок. Но опять же каков этот порядок? Если смотреть на основную реализацию NavigableMap, то это красно-черное дерево, и упорядочивается оно либо натуральным порядком (линейным), либо компаратором. И основное ограничение на компаратор, насколько я помню — частичный порядок, а вовсе не линейная последовательность. Это первая несуразица.

Второе. Поскольку порядок элементов во многих реализациях Set никак не зависит от способа их помещения в коллекцию, то и соответствующие методы addFirst(), addLast() просто по дизайну не обязаны работать и кидают исключение.

Исключение здесь (простите за каламбур — он не мой) составляют LinkedHashMap / LinkedHashSet. Они действительно честно помещают элемент в начало/конец.

Такой принцип дизайна классов коллекций не нов. В принципе в той же Collection метод add(Object) опционален, то есть кидает исключение. И такой подход я считаю крайне некорректным. Мало того что выкидывается ошибка, так она ещё и непроверяемая (unchecked UnsupportedOperationException). Это часто приводит к появлению неприятных непредсказуемых ошибок в программе уже во время выполнения. Так что при использовании коллекций, особенно при их изменении в Яве всегда нужно быть на чеку: фактически все операции нужно проверять, если вы не знаете, откуда конкретно была собрана ваша коллекция.

Ну и теперь по поводу собственно этого дизайна опциональных операций: в JRE принято, что AbstractCollection.add() может быть не реализован, то же самое с Iterator.remove. Причём узнать сработает или нет, нет никакой возможности кроме как попробовав их вызвать. Нормальным подходом по моему был бы такой: если метод контракта не выполняется, то этого метода в контракте просто не должно быть. И тут встаёт давняя застарелая проблема библиотеки — в ней нет интерфейсов для неизменяемых коллекций, то есть все коллекции имеют контракт модифицируемых, хотя по факту его не выполняют. Причём эта тенденция повторяется и в более поздних версиях Явы. В 17, кажется, версии добавили неизменяемые коллекции, получаемые через фабрики List.of(), Set.of(). Но так и не добавили соответствующий интерфейс для них.
В таком случае правильным решением, на мой взгляд, было бы внесение именно таких неизменяемых версий основных коллекций. То есть для каждой коллекции Collection имеется пара ей в виде <Collection только для чтения>, например RCollection. Причём в RCollection методы только для чтения состояния и Collection наследует все эти методы, добавляя свои модифицирующие. Картина выглядит примерно так:

Классы для неизменяемых коллекций образуют свою иерархию RCollection -> RSet -> RSortedSet и т.д. Изменяемые коллекции сохраняют свою иерархию. И таким образом получается две параллельных иерархии коллекций. В этом подходе нет контрактов, которые предполагают их невыполнение. Из метода не будет выкинуто рантайм-исключение просто по дизайну.

В целом для базовых классов получается примерно такая картина:

Скрытый текст

Картина с методами будет тогда такой

Скрытый текст

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

Такое я предлагаю дизайн-решение.

Ну и напоследок кину ещё сюда ссылку на мою реализацию префиксного дерева, оно же trie. Судя по первому опыту её использования справляется с основным своим назначением она неплохо. Вот её показатели JMH относительно HashMap:

Benchmark                               (index)              (vocab)   Mode  Cnt       Score       Error   Units TrieBench.benchHashFreshSearchCycle         N/A                  N/A  thrpt    7    6627,915 ±  4699,962  ops/ms TrieBench.benchHashReadySearchCycle         N/A                  N/A  thrpt    7   10195,545 ±   891,684  ops/ms TrieBench.benchHashReadySearchVocab         N/A                  N/A  thrpt    7  335681,210 ±  9875,437  ops/ms TrieBench.benchTrieSearchCycle             FLAT    COMPUTED_FULL_IND  thrpt   15    3380,479 ±   179,434  ops/ms TrieBench.benchTrieSearchCycle             FLAT  COMPUTED_NOCOND_IND  thrpt   15    2643,886 ±   113,154  ops/ms TrieBench.benchTrieSearchCycle             FLAT               CACHED  thrpt   15  155172,599 ±  3353,967  ops/ms TrieBench.benchTrieSearchCycle       COMPRESSED    COMPUTED_FULL_IND  thrpt   15    2033,263 ±    25,904  ops/ms TrieBench.benchTrieSearchCycle       COMPRESSED  COMPUTED_NOCOND_IND  thrpt   15    1436,275 ±   259,338  ops/ms TrieBench.benchTrieSearchCycle       COMPRESSED               CACHED  thrpt   15  130700,170 ±  2305,216  ops/ms TrieBench.benchTrieSearchVocab             FLAT    COMPUTED_FULL_IND  thrpt   15  215942,820 ±  3399,134  ops/ms TrieBench.benchTrieSearchVocab             FLAT  COMPUTED_NOCOND_IND  thrpt   15  152286,323 ± 37999,875  ops/ms TrieBench.benchTrieSearchVocab             FLAT               CACHED  thrpt   15  249261,883 ±  4907,641  ops/ms TrieBench.benchTrieSearchVocab       COMPRESSED    COMPUTED_FULL_IND  thrpt   15  181783,586 ±  4927,024  ops/ms TrieBench.benchTrieSearchVocab       COMPRESSED  COMPUTED_NOCOND_IND  thrpt   15  151407,664 ±  5612,320  ops/ms TrieBench.benchTrieSearchVocab       COMPRESSED               CACHED  thrpt   15  202655,203 ±  3022,410  ops/ms  

SearchCycle — простой поиск containsAll по списку из ~20 слов, SearchVocab тот же containsAll для коллекции из 20 слов но относительно всего английского словаря, что конечно failfast сценарий.

Ссылка: github