Как использовать Sets как ключи в Java-картах

У меня есть карта, которая использует набор для типа ключа, например:

Map<Set<Thing>, Val> map;

Когда я запрашиваю map.containsKey(myBunchOfThings), он возвращает false, и я не понимаю, почему. Я могу перебирать каждую клавишу в наборе ключей и проверять, есть ли ключ, который (1) имеет тот же hashCode, и (2) равен() для myBunchOfThings.

System.out.println(map.containsKey(myBunchOfThings)); // false.
for (Set<Thing> k : map.keySet()) {
  if (k.hashCode() == myBunchOfThings.hashCode() && k.equals(myBunchOfThings) {
     System.out.println("Fail at life."); // it prints this.
  }
}

Я просто принципиально неправильно понимаю контракт на containsKey? Есть ли секрет использования наборов (или, более общо, коллекций) в качестве ключей к картам?

Ответы

Ответ 1

Ключ не должен быть мутирован при использовании на карте. В java-документе Map говорится:

Примечание: следует проявлять большую осторожность, если изменяемые объекты используются в качестве ключей карты. Поведение карты не указано если значение объекта изменено таким образом, сравнение, в то время как объект является ключом на карте. Частный случай этого запрет заключается в том, что он не допустимо, чтобы карта содержала как ключ. Хотя это допустимо, чтобы карта содержала само по себе как ценность, крайне осторожно советовали: equals и hashCode методы более не определены такое отображение.

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

   Map<Set<String>, Object> map  = new HashMap<Set<String>, Object>();

   Set<String> key1 = new HashSet<String>();
   key1.add( "hello");

   Set<String> key2 = new HashSet<String>();
   key2.add( "hello2");

   Set<String> key2clone = new HashSet<String>();
   key2clone.add( "hello2");

   map.put( key1, new Object() );
   map.put( key2, new Object() );

   System.out.println( map.containsKey(key1)); // true
   System.out.println( map.containsKey(key2)); // true
   System.out.println( map.containsKey(key2clone)); // true

   key2.add( "mutate" );

   System.out.println( map.containsKey(key1)); // true
   System.out.println( map.containsKey(key2)); // false
   System.out.println( map.containsKey(key2clone)); // false (*)

   key2.remove( "mutate" );

   System.out.println( map.containsKey(key1)); // true
   System.out.println( map.containsKey(key2)); // true
   System.out.println( map.containsKey(key2clone)); // true

После того как key2 мутирован, карта больше не содержит его. Мы могли бы подумать, что карта "индексирует" данные при их добавлении, и тогда мы ожидаем, что она все еще содержит клон key2 (строка помечена *). Но достаточно смешно, это не так.

Итак, как говорит java-документ, ключи не должны быть мутированными, иначе поведение неуказано. Период.

Я предполагаю, что то, что происходит в вашем случае.

Ответ 2

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

Если вы хотите использовать многие ключевые значения в качестве ключа Map, вы должны использовать реализацию класса, предназначенную для этой цели, например Apache Commons Collections MultiKey.

Если вы действительно должны использовать Set или Collection в качестве ключа, сначала сделайте его неизменным (Collections.unmodifiableSet(...)), а затем не сохраните ссылку на изменяемый поддерживающий объект.

Еще одна трудность с использованием Collections как ключей заключается в том, что они могут быть построены в другом порядке. Только отсортированная коллекция будет иметь высокую вероятность совпадения. Например, если вы используете последовательно упорядоченный ArrayList, но создаете список по-другому, во второй раз он не будет соответствовать ключу - хеш-код и порядок значений различны.

РЕДАКТИРОВАТЬ: я исправляю это утверждение ниже, никогда не используя Set для ket. Я просто прочитал часть реализации hashCode в AbstractHashSet. Это использует простую совокупность всех значений, поэтому не зависит от порядка. Equals также проверяет, что один набор содержит все значения в другом наборе. Однако это все еще верно для других видов коллекций в Java (порядок ArrayList имеет значение).

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

Ответ 3

Вы изменили набор после вставки? Если это так, возможно, набор был отсортирован в другое ведро, чем тот, в котором он находится. Когда он повторяется, он находит ваш набор, потому что он выглядит на всей карте.

Я считаю, что контракт для HashMap утверждает, что вам запрещено изменять хэш-код для объектов, используемых в качестве ключа,

Ответ 4

Передаете ли вы точный набор (набор, который хотите найти) при сравнении для ключа?