Когда мне понадобилось реализовать ярлыки для Java «как в веб-два-ноль», гугление не помогло найти ни одной библиотеки, содержащей в себе подобный тип коллекции.

Решил сделать сам.

Итак, нам надо хранить объекты в коллекции данного типа (назовем его, скажем, LabelsMultiMap). Как объекты, так и ярлыки могут быть произвольного типа. Количество ярлыков сверху не ограничено, равно как и количество объектов. Одним и тем же набором ярлыков могут быть описаны более 1 объекта. У одного объекта один ярлык может встретиться только 1 раз.

Пример валидных ярлыков:

Ярлыки	Объекты
green, wooden, alive	tree
green, wooden, lifeless	bench
green, alive, croak	frog

Коллекция должна позволять:

1. put() — помещать в неё объекты со списком прикрепленных меток
2. getValues() — возвращать объекты, содержащиеся в коллекции
3. findValues() — осуществлять поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков
4. findValuesOnlyIn() — осуществлять поиск только тех объектов, все ярлыки которых входят в запрашиваемый набор ярлыков

Поясню последние 2 пункта на следующей таблице по тем объектам, которые были рассмотрены в предыдущем примере:

Ярлыки, передаваемые в качестве аргумента	findValues()	findValuesOnlyIn()
green, wooden	tree, bench
green, wooden, alive, lifeless		tree, bench
	tree, bench, frog

Поиск должен быть быстрым, поэтому для индексации будем использовать битовые маски. Т.е. сам объект храним в массиве, а его порядковый номер в этом массиве — это порядковый номер бита в битовой маске.

Опять же вернемся к нашему примеру:

Нумерация объектов в массиве: 0 — tree, 1 — bench, 2 — frog.
Тогда битовая маска для ярлыка green будет {1, 1, 1}, для wooden — {1, 1, 0}, для alive — {1, 0, 1}, lifeless — {0, 1, 0}, croak — {0, 0, 1}.

Битовые маски позволяют упростить поиск объектов по ярлыку, просто выполняя двоичные операции: AND, OR, NOT и т.п… В результате, если на определенной позиции останется единичный бит, то по её номеру легко извлечём из массива искомый объект.

Начинаем реализацию:

Здесь V — тип объектов, L — тип ярлыков, labelsBitSets — хранилище битовых масок ярлыков, values — хранилище объектов:

public class LabelsMultiMap<L, V> {
  private final Map<L, BitSet> labelsBitSets = new HashMap<>();
  private final List<V> values = new ArrayList<>();
}

Метод, помещающий новый объект с его описывающими ярлыками в нашу коллекцию:

Здесь мы помещаем наш объект в values в методе addValue(), который вернет индекс новой ячейки массива. Далее по каждому ярлыку проверяем, есть ли битовая маска для данного ярлыка, если нет, то создаем пустую маску, добавляем в labelsBitSets, если уже есть, то возвращаем старую маску, и выставляем единичный бит в ней по позиции объекта в массиве, которая хранится в i:

public void put(Set<L> labels, V value) {
  int i = addValue(value);
  for(L label : labels) {
    BitSet bitSet = getOrCreateLabel(label);
    bitSet.set(i);
  }
}

Метод, возвращающий все объекты из коллекции:

public List<V> getValues() {
  return Collections.unmodifiableList(values);
}

Метод, осуществляющий поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков:

public Collection<V> findValues(Set<L> labels) {
  Iterator<L> it = labels.iterator();

Если список ярлыков в аргументе пуст, то возвращаем весь список:

  if (!it.hasNext()) {
    return getValues();
  }

Если по первому попавшемуся ярлыку не нашли ни одной битовой маски, то возвращаем пустой результат:

  BitSet firstBitSet = labelsBitSets.get(it.next());
  if (firstBitSet == null) {
    return Collections.emptySet();
  }

Инициализируем аккумулятор, куда будем накапливать найденный битовые маски с помощью операции AND. Использовал clone(), т.к. у BitSet отсутствует конструктор копирования:

  BitSet accumulator = (BitSet) firstBitSet.clone();

Накапливаем в accumulator все маски, если не нашли хоть одну битовую маску по одному из последующих ярлыков, то возвращаем пустую коллекцию:

  while (it.hasNext()) {
    BitSet nextBitSet = labelsBitSets.get(it.next());
    if (nextBitSet == null) {
      return Collections.emptySet();
    }
    accumulator.and(nextBitSet);
  }

Возвращаем результат в виде новой коллекции по накопленной маске в accumulator:

  return new ValuesByBitSetCollection<>(accumulator, values);
}

Ну и последний метод, осуществляющий поиск только тех объектов, все ярлыки которых входят в запрашиваемый набор ярлыков:

В inAccumulator накапливаем те битовые маски, которые есть в нашем запросе, а в outAccumulator — которых нет в нашем запросе, если исходный запрос пуст, возвращаем пустое множество:

public Collection<V> findValuesOnlyIn(Set<L> labels) {
  if (labels.isEmpty()) {
    return Collections.emptySet();
  }
  BitSet inAccumulator = new BitSet(values.size());
  BitSet outAccumulator = new BitSet(values.size());

Пробегаем по всем сохраненным ярлыкам в нашей коллекции, откладывая их битовые маски в in-/outAccumulator в зависимости от наличия их в labels, в конце просто вычтем одно множество из другого и вернем результат в виде коллекции по результирующей маске.

  for(Map.Entry<L, BitSet> bitSetEntry : labelsBitSets.entrySet()) {
    BitSet accumulator = labels.contains(bitSetEntry.getKey()) ? inAccumulator : outAccumulator;
    accumulator.or(bitSetEntry.getValue());
  }
  
  inAccumulator.andNot(outAccumulator);

  return new ValuesByBitSetCollection<>(inAccumulator, values);
}