Являются ли изменяемые ключи hashmap опасной практикой? - PullRequest
53 голосов
/ 21 октября 2011

Плохо ли использовать изменяемые объекты в качестве ключей 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)?Это безопасно или желательно?Или поведение зависит от языка?

Ответы [ 7 ]

71 голосов
/ 30 октября 2011

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

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

21 голосов
/ 24 октября 2011

Это не безопасно и не рекомендуется. Значение, сопоставленное 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 с помощью ключа 1.

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

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)) 

не удастся.

5 голосов
/ 28 октября 2011

Хеш-карты используют хеш-код и сравнения на равенство, чтобы идентифицировать определенную пару ключ-значение с данным ключом. Если карта 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"

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

5 голосов
/ 21 октября 2011

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

4 голосов
/ 14 сентября 2014

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

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

2 голосов
/ 28 октября 2011

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

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

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

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

0 голосов
/ 08 ноября 2016

Поведение карты не указывается, если значение объекта изменяется способом, который влияет на сравнение на равных, а объект (изменяемый) является ключом. Даже для 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"); ... Теперь o / p будет таким:

 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

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

...