Являются ли изменяемые ключи hashmap опасной практикой?

Question

Плохо ли использовать изменяемые объекты в качестве ключей Hashmap? Что происходит, когда вы пытаетесь получить значение из Hashmap, используя ключ, который был достаточно изменен, чтобы изменить его хэш-код?

Например, учитывая

class Key
{
    int a; //mutable field
    int b; //mutable field

    public int hashcode()
        return foo(a, b);
    // setters setA and setB omitted for brevity
}

с кодом

HashMap<Key, Value> map = new HashMap<Key, Value>();

Key key1 = new Key(0, 0);
map.put(key1, value1); // value1 is an instance of Value

key1.setA(5);
key1.setB(10);

Что произойдет, если мы сейчас позвоним map.get(key1)? Это безопасно или желательно? Или поведение зависит от языка?

Answer 1

Многие уважаемые разработчики, такие как Брайан Гетц и Джош Блох, отметили, что:

Если значение hashCode() объекта может изменяться в зависимости от его состояния, то мы должны быть осторожны при использовании таких объектов в качестве ключей в коллекциях на основе хеша, чтобы не допустить изменения их состояния при использовании в качестве ключей хеша, Все основанные на хэше коллекции предполагают, что хеш-значение объекта не изменяется, пока оно используется в качестве ключа в коллекции. Если бы хэш-код ключа изменился, пока он находился в коллекции, это может привести к непредсказуемым и запутанным последствиям. На практике это обычно не является проблемой - не является обычной практикой использование изменяемого объекта, такого как List, в качестве ключа в HashMap.

Answer 2

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

Object get(Object key) {
    int hash = key.hashCode();
    //simplified, ignores hash collisions,
    Entry entry = getEntry(hash);
    if(entry != null && entry.getKey().equals(key)) {
        return entry.getValue();
    }
    return null;
}

В этом примере key1.hashcode() теперь указывает на неправильный сегмент хеш-таблицы, и вы не сможете получить значение1 с помощью ключа key1.

Если бы вы сделали что-то вроде,

Key key1 = new Key(0, 0);
map.put(key1, value1);
key1.setA(5);
Key key2 = new Key(0, 0);
map.get(key2);

Это также не будет извлекать значение1, поскольку ключи key1 и key2 больше не равны, поэтому эта проверка

    if(entry != null && entry.getKey().equals(key)) 

не удастся.

Answer 3

Хеш-карты используют хэш-код и сравнения на равенство, чтобы идентифицировать определенную пару ключ-значение с данным ключом. Если карта has хранит ключ как ссылку на изменяемый объект, он будет работать в тех случаях, когда один и тот же экземпляр используется для получения значения. Рассмотрим, однако, следующий случай:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances and 
// keyOne.equals(keyTwo) is true.

HashMap myMap = new HashMap();

myMap.push(keyOne, "Hello");

String s1 = (String) myMap.get(keyOne); // s1 is "Hello"
String s2 = (String) myMap.get(keyTwo); // s2 is "Hello" 
                                        // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap.get(keyOne); // returns "Hello"
s2 = myMap.get(keyTwo); // not found

Вышесказанное верно, если ключ хранится в качестве ссылки. В Java это обычно так. Например, в.NET, если ключ является типом значения (всегда передается по значению), результат будет другим:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances 
// and keyOne.equals(keyTwo) is true.

Dictionary myMap = new Dictionary();

myMap.Add(keyOne, "Hello");

String s1 = (String) myMap[keyOne]; // s1 is "Hello"
String s2 = (String) myMap[keyTwo]; // s2 is "Hello"
                                    // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap[keyOne]; // not found
s2 = myMap[keyTwo]; // returns "Hello"

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

Answer 4

Если хеш-код ключа изменится после того, как пара ключ-значение (Entry) сохранена в HashMap, карта не сможет получить Entry.

Хэш-код ключа может измениться, если объект ключа изменчив. Изменяемые ключи в HahsMap могут привести к потере данных.

Answer 5

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

Answer 6

Как объяснили другие, это опасно.

Чтобы избежать этого, нужно иметь поле const, дающее явно хэш в ваших изменяемых объектах (чтобы вы могли хешировать их "идентичность", а не "их состояние"). Вы можете даже инициализировать это хеш-поле более или менее случайным образом.

Другой трюк будет использовать адрес, например, (intptr_t) reinterpret_cast<void*>(this) в качестве основы для хеширования.

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

Answer 7

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

Первая проблема: (вероятно, самая тривиальная, но, черт возьми, это дало мне проблемы, о которых я не думал!)

Вы пытаетесь разместить пары ключ-значение на карте, обновляя и изменяя один и тот же ключевой объект. Вы могли бы сделать что-то вроде Map<Integer, String> и просто скажите:

      int key = 0;
loop {
    map.put(key++, newString);
}

Я повторно использую «объект» для создания карты. Это отлично работает в Java из-за автобокса, при котором каждое новое значение автоматически упаковывается в новый объект Integer. Что бы не сработало, если бы я создал свой собственный (изменяемый) объект Integer:

      MyInteger {
   int value;

   plusOne(){
      value++;
   }
}

Затем попробовал тот же подход:

      MyInteger key = new MyInteger(0);
loop{
   map.put(key.plusOne(), newString)
}

Я ожидаю, что, например, я сопоставлю и. В первом примере, если я изменю int key = 0, карта (правильно) даст мне. Для простоты предположим MyIntegerпросто всегда возвращает одно и то же (если вам каким-то образом удастся создать уникальные значения hashCode для всех возможных состояний объекта, это не будет проблемой, и вы заслуживаете награды). В этом случае я вызываю, так что теперь карта содержит мой и сопоставляет его, затем я изменяю key = 1и попробуй поставить. У нас есть проблемы! То же самое, и единственный ключ в HashMap - это мой MyInteger key объект, который был только что изменен, чтобы он был равен 1, поэтому он перезаписывает значение этого ключа, так что теперь вместо карты с и у меня есть только! Еще хуже, если я вернусь к key = 0, hashCode указывает на, но поскольку единственным ключом HashMap является мой ключевой объект, он удовлетворяет проверке равенства и возвращает не так, как ожидалось.

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

Совет:

Чтобы найти этот тип проблемы, измените метод, даже тривиально (т.е. = 0- очевидно, при этом имейте в виду, что значения хэша должны быть одинаковыми для двух равных объектов *), и посмотрите, получите ли вы одинаковые результаты - потому что вы должны, а если вы этого не сделаете, вероятно, есть семантическая ошибка с вашей реализацией, использующей хеш-таблицу.

* Не должно быть опасности (если есть - у вас есть семантическая проблема) в том, чтобы всегда возвращать 0 из hashCode() (хотя это нарушило бы цель хеш-таблицы). Но в том-то и дело:hashCode - это «быстрый и простой» показатель равенства, который не является точным. Таким образом, два очень разных объекта могут иметь одинаковый hashCode (), но не равны. С другой стороны, два одинаковых объекта всегда должны иметь одно и то же значение hashCode() .

ps В Java, насколько я понимаю, если вы сделаете такую ​​ужасную вещь (например, у вас будет много конфликтов hashCode() ), она начнет использовать красно-черное дерево, а не ArrayList. Поэтому, когда вы ожидаете поиска O(1), вы получите O(log(n))- что лучше, чем ArrayList, который даст O(n).

Вторая проблема:

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

Ожидание: key -> value отображается, затем я изменяю и пытаюсь get(key). Я ожидаю, что это даст мне value.

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

Вот почему очень нецелесообразно использовать коллекции в качестве ключей. Я предполагаю, что если вы делаете это, вы пытаетесь установить отношения «многие к одному». Итак, у меня есть класс (как в преподавании), и я хочу, чтобы две группы выполняли два разных проекта. Я хочу, чтобы у группы был ее проект? Просто, я делю класс на два, и у меня group1 -> project1 а также group2 -> project2. Но ждать! Приходит новый студент, и я их зачисляю. Проблема в том, что group1 теперь был изменен и, вероятно, его хеш-значение изменилось, поэтому пытаюсь сделать get(group1) скорее всего, потерпит неудачу, потому что он будет искать в неправильном или несуществующем сегменте HashMap.

Очевидным решением вышеизложенного является объединение вещей в цепочку - вместо использования групп в качестве ключей, дайте им метки (которые не меняются), которые указывают на группу и, следовательно, на проект: g1 -> group1 а также g1 -> project1, так далее.

пс

Убедитесь, что вы определили и equals(...) для любого объекта, который вы собираетесь использовать в качестве ключа (eclipse и, я полагаю, большинство IDE могут сделать это за вас).

Пример кода:

Вот класс, который демонстрирует два разных «проблемных» поведения. В этом случае я пытаюсь отобразить 0 -> "a", 1 -> "b", а также 2 -> "c"(в каждом случае). В первой задаче я делаю это, изменяя один и тот же объект, во второй я использую уникальные объекты, а во второй проблеме «исправлено» я клонирую эти уникальные объекты. После этого я беру один из «уникальных» ключей () и модифицирую его, чтобы попытаться получить доступ к карте. Я ожидаю, что это даст мне a, b, c и когда ключ 3.

Однако происходит следующее:

      map.get(0) map1: 0 -> null, map2: 0 -> a, map3: 0 -> a
map.get(1) map1: 1 -> null, map2: 1 -> b, map3: 1 -> b
map.get(2) map1: 2 -> c, map2: 2 -> a, map3: 2 -> c
map.get(3) map1: 3 -> null, map2: 3 -> null, map3: 3 -> null

Первая карта («первая проблема») терпит неудачу, потому что она содержит только один ключ, который был обновлен последним и помещен в равный 2, поэтому он правильно возвращается, но возвращает nullдля двух других (единственный ключ не равен 0 или 1). Вторая карта терпит неудачу дважды: наиболее очевидным является то, что она возвращает "b"когда я попросил (потому что он был изменен - ​​это «вторая проблема», которая кажется очевидной, когда вы делаете что-то подобное). Он терпит неудачу во второй раз, когда возвращается после изменения k0 = 2(чего я и ожидал). Это больше из-за «первой проблемы»: есть конфликт хэш-кода, а разрешение конфликтов - это проверка равенства, но карта выполняется, и она (очевидно, для меня - теоретически может быть другой для кого-то другого) проверяется первой и, следовательно, вернул первое значение, "a" даже если бы он продолжал проверять, "c"тоже был бы матч. Наконец, третья карта работает отлично, потому что я требую, чтобы карта содержала уникальные ключи, независимо от того, что я еще делаю (путем клонирования объекта во время вставки).

Я хочу прояснить, что согласен, клонирование - это не решение! Я просто добавил это в качестве примера того, почему карте нужны уникальные ключи и как применение уникальных ключей «решает» проблему.

      public class HashMapProblems {

   private int value = 0;

   public HashMapProblems() {
       this(0);
   }

   public HashMapProblems(final int value) {
       super();
       this.value = value;
   }

   public void setValue(final int i) {
       this.value = i;
   }

   @Override
   public int hashCode() {
       return value % 2;
   }

   @Override
   public boolean equals(final Object o) {
       return o instanceof HashMapProblems
            && value == ((HashMapProblems) o).value;
   }

   @Override
   public Object clone() {
       return new HashMapProblems(value);
   }

   public void reset() {
       this.value = 0;
   }

   public static void main(String[] args) {
       final HashMapProblems k0 = new HashMapProblems(0);
       final HashMapProblems k1 = new HashMapProblems(1);
       final HashMapProblems k2 = new HashMapProblems(2);
       final HashMapProblems k = new HashMapProblems();
       final HashMap<HashMapProblems, String> map1 = firstProblem(k);
       final HashMap<HashMapProblems, String> map2 = secondProblem(k0, k1, k2);
       final HashMap<HashMapProblems, String> map3 = secondProblemFixed(k0, k1, k2);

       for (int i = 0; i < 4; ++i) {
           k0.setValue(i);
           System.out.printf(
                "map.get(%d) map1: %d -> %s, map2: %d -> %s, map3: %d -> %s",
                i, i, map1.get(k0), i, map2.get(k0), i, map3.get(k0));
           System.out.println();
       }
   }

   private static HashMap<HashMapProblems, String> firstProblem(
        final HashMapProblems start) {
       start.reset();
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       map.put(start, "a");
       start.setValue(1);
       map.put(start, "b");
       start.setValue(2);
       map.put(start, "c");
       return map;
   }

   private static HashMap<HashMapProblems, String> secondProblem(
        final HashMapProblems... keys) {
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       IntStream.range(0, keys.length).forEach(
            index -> map.put(keys[index], "" + (char) ('a' + index)));
       return map;
   }

   private static HashMap<HashMapProblems, String> secondProblemFixed(
        final HashMapProblems... keys) {
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       IntStream.range(0, keys.length)
            .forEach(index -> map.put((HashMapProblems) keys[index].clone(),
                    "" + (char) ('a' + index)));
       return map;
   }
}

Некоторые примечания:

Выше следует отметить, что map1 содержит только два значения из-за того, как я настроил hashCode() функция разделения шансов и эвенов. k = 0 и поэтому иметь такой же hashCode из 0. Итак, когда я изменяю k = 2 и попытаться k -> "c" отображение k -> "a" перезаписывается - k -> "b"это еще там , потому что она существует в другом ведре.

Также есть много разных способов исследовать карты в приведенном выше коде, и я бы посоветовал людям, которым любопытно, делать такие вещи, как распечатка значений карты, а затем ключ к сопоставлениям значений (вы можете быть удивлены результатами ты получаешь). Поиграйте с изменением различных "уникальных" ключей (т. Е. k0, k1, а также k2), попробуйте изменить единственный ключ k. Вы также могли видеть, как даже secondProblemFixedна самом деле не исправлено, потому что вы также можете получить доступ к ключам (например, через Map::keySet) и измените их.

Answer 8

Я не буду повторять то, что сказали другие. Да, это нецелесообразно. Но, на мой взгляд, не совсем очевидно, где это говорится в документации.

Вы можете найти его в JavaDoc для интерфейса карты :

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

Answer 9

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

Давайте посмотрим пример здесь:

public class MapKeyShouldntBeMutable {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Employee,Integer> map=new HashMap<Employee,Integer>();

    Employee e=new Employee();
    Employee e1=new Employee();
    Employee e2=new Employee();
    Employee e3=new Employee();
    Employee e4=new Employee();
    e.setName("one");
    e1.setName("one");
    e2.setName("three");
    e3.setName("four");
    e4.setName("five");
    map.put(e, 24);
    map.put(e1, 25);
    map.put(e2, 26);
    map.put(e3, 27);
    map.put(e4, 28);
    e2.setName("one");
    System.out.println(" is e equals e1 "+e.equals(e1));
    System.out.println(map);
    for(Employee s:map.keySet())
    {
        System.out.println("key : "+s.getName()+":value : "+map.get(s));
    }
}

  }
 class Employee{
String name;

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

@Override
public boolean equals(Object o){
    Employee e=(Employee)o;
    if(this.name.equalsIgnoreCase(e.getName()))
            {
        return true;
            }
    return false;

}

public int hashCode() {
    int sum=0;
    if(this.name!=null)
    {
    for(int i=0;i<this.name.toCharArray().length;i++)
    {
        sum=sum+(int)this.name.toCharArray()[i];
    }
    /*System.out.println("name :"+this.name+" code : "+sum);*/
    }
    return sum;

}

}

Здесь мы пытаемся добавить изменяемый объект "Сотрудник" на карту. Это будет работать хорошо, если все добавленные ключи различны. Здесь я переопределил equals и hashcode для класса сотрудника.

Смотрите сначала я добавил "е", а затем "е1". Для обоих из них equals() будет истинным, а хеш-код будет одинаковым. Таким образом, карта видит, как будто добавляется тот же ключ, поэтому она должна заменить старое значение значением e1. Затем мы добавили e2,e3,e4 у нас все хорошо на данный момент.

Но когда мы меняем значение уже добавленного ключа, то есть "e2", как единое целое, оно становится ключом, похожим на тот, который был добавлен ранее. Теперь карта будет вести себя как проводная. В идеале e2 должен заменить существующий тот же ключ, т. Е. E1. Но теперь карта принимает и это. И вы получите это в o/p:

 is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@142=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : one:value : 25

Смотрите здесь обе клавиши, имеющие одну и ту же величину. Так что это неожиданно. Теперь снова запустите ту же программу, изменив e2.setName("diffnt"); который e2.setName("one"); вот... Теперь о / п будет таким:

 is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@27b=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : diffnt:value : null

Таким образом, добавление изменения изменяемого ключа на карте не рекомендуется.

Answer 10

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

Все остальные операции по навигации по карте выполняются с помощью этого предварительно рассчитанного внутреннего хэша.

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

Но HashMapВнутренний хэш, конечно, не будет пересчитан, и он будет старым, сохраненным, и карта не сможет найти ваши данные по предоставленному измененному ключевому объекту новый хэш-код. (например, HashMap.get() или же HashMap.containsKey()).

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

Обратите внимание, что вы также не сможете получить данные обратно с помощью измененного ключевого объекта, взятого прямо из HashMap.keySet().