변경 가능한 해시 맵 키는 위험한 행위입니까?

변경 가능한 해시 맵 키는 위험한 행위입니까?

---

변경 가능한 객체를 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)어떻게 되나요? 이것이 안전하거나 권장 되는가? 아니면 언어에 따라 행동이 달라 집니까?

---

Brian Goetz 및 Josh Bloch와 같은 존경받는 많은 개발자들은 다음과 같은 점을 지적했습니다.

객체의 hashCode () 값이 상태에 따라 변경 될 수있는 경우 해시 기반 컬렉션의 키와 같은 객체를 사용할 때 해시 키로 사용될 때 상태가 변경되지 않도록주의해야합니다. . 모든 해시 기반 컬렉션은 컬렉션에서 키로 사용되는 동안 개체의 해시 값이 변경되지 않는다고 가정합니다. 키의 해시 코드가 컬렉션에있는 동안 변경되면 예측할 수없고 혼란스러운 결과가 발생할 수 있습니다. 이것은 일반적으로 실제로 문제가되지 않습니다. HashMap의 키로 List와 같은 변경 가능한 객체를 사용하는 것은 일반적인 관행이 아닙니다.

---

이것은 안전하거나 권장하지 않습니다. 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 ()는 이제 해시 테이블의 잘못된 버킷을 가리키며 key1을 사용하여 value1을 검색 할 수 없습니다.

당신이 뭔가를했다면

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

이것은 또한 key1과 key2가 더 이상 같지 않기 때문에 value1을 검색하지 않습니다.

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

실패합니다.

---

해시 맵은 해시 코드와 같음 비교를 사용하여 주어진 키로 특정 키-값 쌍을 식별합니다. 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"

다른 기술에는 다른 동작이있을 수 있습니다. 그러나 거의 대부분은 변경 가능한 키를 사용한 결과가 결정적이지 않은 상황에 이르게 될 것입니다. 이는 애플리케이션에서 매우 나쁜 상황입니다. 디버깅하기 어렵고 이해하기 더 어렵습니다.

---

작동하지 않습니다. 키 값을 변경하고 있으므로 기본적으로 버리는 것입니다. 실제 열쇠와 자물쇠를 만든 다음 열쇠를 바꾸고 자물쇠에 다시 넣으려는 것과 같습니다.

---

키-값 쌍 (Entry)이 HashMap에 저장된 후 키의 해시 코드가 변경되면 맵에서 항목을 검색 할 수 없습니다.

키 개체가 변경 가능한 경우 키의 해시 코드가 변경 될 수 있습니다. HahsMap의 변경 가능한 키로 인해 데이터가 손실 될 수 있습니다.

---

다른 사람들이 설명했듯이 위험합니다.

A way to avoid that is to have a const field giving explicitly the hash in your mutable objects (so you would hash on their "identity", not their "state"). You might even initialize that hash field more or less randomly.

Another trick would be to use the address, e.g. (intptr_t) reinterpret_cast<void*>(this) as a basis for hash.

In all cases, you have to give up hashing the changing state of the object.

---

Behaviour of a Map is not specified if value of an object is changed in a manner that affects equals comparision while object(Mutable) is a key. Even for Set also using mutable object as key is not a good idea.

Lets see a example here :

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;

}

}

Here we are trying to add mutable object "Employee" to a map. It will work good if all keys added are distinct.Here I have overridden equals and hashcode for employee class.

See first I have added "e" and then "e1". For both of them equals() will be true and hashcode will be same. So map sees as if the same key is getting added so it should replace the old value with e1's value. Then we have added e2,e3,e4 we are fine as of now.

But when we are changing the value of an already added key i.e "e2" as one ,it becomes a key similar to one added earlier. Now the map will behave wired. Ideally e2 should replace the existing same key i.e e1.But now map takes this as well. And you will get this in 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

See here both keys having one showing same value also. So its unexpected.Now run the same programme again by changing e2.setName("diffnt"); which is e2.setName("one"); here ...Now the o/p will be this :

 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

So by adding changing the mutable key in a map is not encouraged.

참고URL : https://stackoverflow.com/questions/7842049/are-mutable-hashmap-keys-a-dangerous-practice