Статьи

Преобразование Коллекций

Март 19, 2019

Вы когда-нибудь хотели заменить методы equals и hashCode используемые HashSet или HashMap ? Или List некоторых элементов типа маскируется под List связанных типов?

Преобразование коллекций делает это возможным, и этот пост покажет, как.

обзор

Преобразование коллекций — это особенность LibFX 0.3.0, которая будет выпущена в любой день. Этот пост представит общую идею, охватит технические детали и завершит некоторые варианты использования, где они могут пригодиться.

Текущий пример представляет собой слегка адаптированный вариант демонстрации возможностей, содержащейся в LibFX . Имейте в виду, что это только пример для демонстрации концепции.

Преобразование Коллекций

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

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

Номенклатура

Коллекцию-трансформер также можно рассматривать как декоратор. Я буду ссылаться на декорированную коллекцию как на внутреннюю коллекцию, а ее общий тип, соответственно, на внутреннюю. Преобразующая коллекция и ее общий тип называются соответственно внешней коллекцией и внешним типом.

пример

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

(Комментарии типа // "[0, 1] ~ [0, 1]" являются консольным выходом System.out.println(innerSet + " ~ " + transformingSet); )

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
Set<String> innerSet = new HashSet<>();
Set<Integer> transformingSet = new TransformingSet<>(
    innerSet,
    /* skipping some details */);
// both sets are initially empty: "[] ~ []"
 
// now let's add some elements to the inner set
innerSet.add("0");
innerSet.add("1");
innerSet.add("2");
// these elements can be found in the view: "[0, 1, 2] ~ [0, 1, 2]"
 
// modifying the view reflects on the inner set
transformingSet.remove(1);
// again, the mutation is visible in both sets: "[0, 2] ~ [0, 2]"

Видите, какими приятными могут быть трансформации?

подробности

Как обычно, дьявол кроется в деталях, поэтому давайте обсудим важные части этой абстракции.

Forwarding

Трансформирующие коллекции — это взгляд на другую коллекцию. Это означает, что они не содержат никаких элементов сами по себе, но перенаправляют все вызовы во внутреннюю / украшенную коллекцию.

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

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

преобразование

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

Функции преобразования должны быть обратными друг к другу в отношении equals , то есть outer.equals(toOuter(toInner(outer)) и inner.equals(toInner(toOuter(inner)) должны быть истинными для всех внешних и внутренних элементов. Если это это не так, коллекции могут вести себя непредсказуемым образом.

То же самое не верно для идентичности, то есть outer == toOuter(toInner(outer)) может быть ложным. Детали зависят от примененного преобразования и, как правило, не определены — это может быть никогда, иногда или всегда верно.

пример

Давайте посмотрим, как функции преобразования выглядят для наших наборов строк и целых чисел:

1
2
3
4
5
6
7
private Integer stringToInteger(String string) {
    return Integer.parseInt(string);
}
 
private String integerToString(Integer integer) {
    return integer.toString();
}

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

1
2
3
4
Set<Integer> transformingSet = new TransformingSet<>(
    innerSet,
    this::stringToInteger, this::integerToString,
    /* still skipping some details */);

Прямо вперед, верно?

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
innerSet.add("010");
innerSet.add("10");
// now the transforming sets contains the same entry twice:
// "[010, 10] ~ [10, 10]"
 
// sizes of different sets:
System.out.println(innerSet.size()); // "2"
System.out.println(transformingSet.size()); // "2"
System.out.println(new HashSet<>(transformingSet).size()); // "1" !
 
// removing is also problematic
transformingSet.remove(10) // the call returns true
// one of the elements could be removed: "[010] ~ [10]"
transformingSet.remove(10) // the call returns false
// indeed, nothing changed: "[010] ~ [10]"
 
// now things are crazy - this returns false:
transformingSet.contains(transformingSet.iterator().next())
// the transforming set does not contain its own elements ~> WAT?

Поэтому при использовании трансформируемых коллекций очень важно тщательно продумывать трансформации. Они должны быть обратными друг другу!

Но этого достаточно, если это ограничено реально возникающими внутренними и внешними элементами. В этом примере проблемы начинаются только тогда, когда вводятся строки с ведущими нулями. Если это было запрещено каким-либо бизнес-правилом, которое должным образом применяется, все будет хорошо.

Тип безопасности

Все операции по преобразованию коллекций являются типобезопасными обычным статическим способом во время компиляции. Но поскольку многие методы из интерфейсов коллекций допускают в качестве аргументов объекты (например, Collection.contains(Object) ) или коллекции неизвестного универсального типа (например, Collection.addAll(Collection<?>) ), Это не охватывает все случаи, которые могут возникать при во время выполнения.

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

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

пример

Наконец, мы можем точно увидеть, как создать набор преобразования:

1
2
3
4
Set<Integer> transformingSet = new TransformingSet<>(
        innerSet,
        String.class, this::stringToInteger,
        Integer.class, this::integerToString);

Конструктор фактически принимает Class<? super I> Class<? super I> так что это также скомпилируется:

1
2
3
4
Set<Integer> transformingSetWithoutTokens = new TransformingSet<>(
        innerSet,
        Object.class, this::stringToInteger,
        Object.class, this::integerToString);

Но поскольку все является объектом, проверка типа по токену становится бесполезной, и вызов функции преобразования может вызвать исключение:

1
2
3
4
Object o = new Object();
innerSet.contains(o); // false
transformingSet.contains(o); // false
transformingSetWithoutTokens.contains(o); // exception

Случаи применения

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

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

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

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

Подставляя Equals And HashCode

Мне всегда нравилось, что в хэш-карте .NET (они называют ее словарем) есть конструктор, который принимает EqualityComparer в качестве аргумента . Все вызовы equals и hashCode , которые обычно вызываются на ключах, вместо этого делегируются этому экземпляру. Таким образом, можно заменить проблемные реализации на лету.

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

С трансформацией коллекций это легко. Чтобы сделать это еще проще, LibFX уже содержит EqualityTransformingSet и EqualityTransformingMap . Они украшают другой набор или реализацию карты и equals и функции hashCode для ключей / элементов могут быть предоставлены во время построения.

пример

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

01
02
03
04
05
06
07
08
09
10
Set<String> lengthSet = EqualityTransformingSet
    .withElementType(String.class)
    .withInnerSet(new HashSet<Object>())
    .withEquals((a, b) -> a.length != b.length)
    .withHash(String::length)
    .build();
 
lengthSet.add("a");
lengthSet.add("b");
System.out.println(lengthSet); // "[a]"

Удаление необязательности из коллекции

Может быть, вы работаете с кем-то, кто взял идею использовать Optional везде , без ума от него, и теперь у вас есть Set<Optional<String>> . В случае, если изменение кода (или вашего коллеги) невозможно, вы можете использовать преобразование коллекций, чтобы получить представление, которое скрывает от вас Optional .

Опять же, реализовать это было просто, поэтому LibFX уже содержит это в форме OptionalTransforming[Collection|List|Set] .

пример

1
2
3
4
5
6
7
8
Set<Optional<String>> innerSet = new HashSet<>();
Set<String> transformingSet =
    new OptionalTransformingSet<String>(innerSet, String.class);
 
innerSet.add(Optional.empty());
innerSet.add(Optional.of("A"));
 
// "[Optional.empty, Optional[A]] ~ [null, A]"

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

1
2
3
4
5
Set<String> transformingSet =
    new OptionalTransformingSet<String>(innerSet, String.class, "DEFAULT");
 
// ... code as above ...
// "[Optional.empty, Optional[A]] ~ [DEFAULT, A]"

Это позволяет избежать как Optional, так и null как элемента, но теперь вы должны быть уверены, что не существует Optional, который содержит DEFAULT . (Если это произойдет, неявные преобразования не обратны друг другу, что мы уже видели выше, чтобы вызвать проблемы.)

Для более подробной информации об этом примере, посмотрите демонстрацию .

отражение

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

Затем мы увидели два конкретных случая использования трансформации коллекций: замена равных и хэш-кода, используемого для хеширования структур данных, и удаление необязательных данных из Collection<Optional<E>> .

Слово о LibFX

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

  • Этот пост представляет идею и некоторые детали, но не заменяет документацию. Проверьте вики для актуального описания и указателей на Javadoc.
  • Я серьезно отношусь к тестированию. Благодаря Guava коллекции-трансформеры проходят около 6,500 юнит-тестов.
  • LibFX распространяется по лицензии GPL. Если это не соответствует вашей модели лицензирования, свяжитесь со мной.
Ссылка: Преобразование коллекций от нашего партнера JCG Николая Парлога в блоге CodeFx .
46
Share: