Баг в дизайне коллекций
В этой статье речь пойдёт о фреймворке коллекций в Java. Относительно недавно (в 3 кв. 2023 года) эта библиотека вновь слегка обновилась. Я ознакомился с обновлениями, и скажу, что они меня разочаровали.
Далее идёт разбор того, что именно я считаю концептуально неверными архитектурным решением в коллекциях, и предложение своего способа их организации.
Итак случившееся обновление — добавление последовательных версий интерфейсов в коллекции, а именно SequencedCollection, SequencedSet и SequencedMap. Такие последовательные коллекции ещё во времена Рапиры, кажется, называли кортежами.
Контракты Sequenced в Java
Казалось бы, замечательное изменение, все его давно ждали. Действительно, общего интерфейса, который бы описывал строго последовательную коллекцию, не было. Ну то есть при желании можно было пользоваться Списком, Двойной очередью или NavigableSet/NavigableMap. Но передать что-то более универсальное было сложно.
Сразу же обращает на себя внимание странная логика внедренцев изменения если касаться SequencedSet: множество, или Set, — это изначально неупорядоченный набор со свойством единственности вхождения элементов. Прямо как в математическом смысле. List — упорядоченный список, Queue по идее тоже последовательна.
Что в таком случае может значить SequencedSet, то есть последовательный неупорядоченный набор?
В принципе, есть же NavigableSet/SortedSet, в которых есть порядок. Но опять же каков этот порядок? Если смотреть на основную реализацию NavigableMap, то это красно-черное дерево, и упорядочивается оно либо натуральным порядком (линейным), либо компаратором. И основное ограничение на компаратор, насколько я помню — частичный порядок, а вовсе не линейная последовательность. Это первая несуразица.
Второе. Поскольку порядок элементов во многих реализациях Set никак не зависит от способа их помещения в коллекцию, то и соответствующие методы addFirst(), addLast() просто по дизайну не обязаны работать и кидают исключение.
Исключение здесь (простите за каламбур — он не мой) составляют LinkedHashMap / LinkedHashSet. Они действительно честно помещают элемент в начало/конец.
Такой принцип дизайна классов коллекций не нов. В принципе в той же Collection метод add(Object el); опционален, то есть кидает исключение. И такой подход я считаю крайне некорректным. Мало того что выкидывается ошибка, так она ещё и непроверяемая (unchecked UnsupportedOperationException). Это часто приводит к появлению неприятных непредсказуемых ошибок в программе уже во время выполнения. Так что при использовании коллекций, особенно при их изменении в Яве всегда нужно быть на чеку: фактически все операции нужно проверять, если вы не знаете, откуда конкретно была собрана ваша коллекция.
Ну и теперь по поводу собственно этого дизайна опциональных операций: в JRE принято, что Collection.add может быть не реализован, то же самое с Iterator.remove. Причём узнать сработает или нет, нет никакой возможности кроме как попробовав их вызвать. Нормальным подходом по моему был бы такой: если метод контракта не выполняется, то этого метода в контракте просто не должно быть. И тут встаёт давняя застарелая проблема библиотеки — в ней нет интерфейсов для неизменемых коллекций, то есть все коллекции имеют контракт модифицируемых, хотя по факту его не выполняют. Причём эта тенденция повторяется и в более поздних версиях Явы. В 17, кажется версии добавили неизменяемые коллекции, получаемые через фабрики List.of(), Set.of(). Но так и не добавили соответствующий интерфейс для них.
В таком случае правильным решением, на мой взгляд, было бы внесение именно таких неизменяемых версий основных коллекций. То есть для каждой коллекции 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
