it-swarm-id.com

Apakah kunci hash yang bisa berubah menjadi praktik yang berbahaya?

Apakah praktik yang buruk untuk menggunakan objek yang bisa berubah-ubah sebagai kunci Hashmap? Apa yang terjadi ketika Anda mencoba mengambil nilai dari Hashmap menggunakan kunci yang telah cukup dimodifikasi untuk mengubah kode hash-nya?

Misalnya diberikan

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

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

dengan kode

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

Apa yang terjadi jika sekarang kita memanggil map.get(key1)? Apakah ini aman atau disarankan? Atau apakah perilaku tergantung pada bahasa?

50
donnyton

Telah dicatat oleh banyak pengembang terkenal seperti Brian Goetz dan Josh Bloch bahwa:

Jika nilai hashCode () objek dapat berubah berdasarkan kondisinya, maka kami harus berhati-hati saat menggunakan objek seperti kunci di hash berbasis koleksi untuk memastikan bahwa kami tidak mengizinkan negara mereka berubah saat mereka digunakan sebagai kunci hash. Semua koleksi berbasis hash menganggap bahwa nilai hash suatu objek tidak berubah saat sedang digunakan sebagai kunci dalam koleksi. Jika kode hash kunci diubah saat itu berada di koleksi, beberapa konsekuensi yang tidak terduga dan membingungkan bisa mengikuti. Ini biasanya bukan masalah dalam praktek - ini bukan praktik umum untuk menggunakan objek yang bisa berubah seperti Daftar sebagai kunci dalam HashMap.

67
aleroot

Ini tidak aman atau disarankan. Nilai yang dipetakan oleh key1 tidak pernah dapat diambil. Ketika melakukan pengambilan, sebagian besar peta hash akan melakukan sesuatu seperti

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;
}

Dalam contoh ini, key1.hashcode () sekarang menunjuk ke ember yang salah dari tabel hash, dan Anda tidak akan dapat mengambil value1 dengan key1.

Jika Anda melakukan sesuatu seperti,

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

Ini juga tidak akan mengambil value1, karena key1 dan key2 tidak lagi sama, jadi ini periksa

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

akan gagal.

20
sbridges

Ini tidak akan berfungsi. Anda mengubah nilai kunci, jadi pada dasarnya Anda membuangnya. Ini seperti membuat kunci dan kunci kehidupan nyata, dan kemudian mengubah kunci dan mencoba memasukkannya kembali ke dalam kunci. 

5
onit

Peta hash menggunakan kode hash dan perbandingan kesetaraan untuk mengidentifikasi pasangan nilai kunci tertentu dengan kunci yang diberikan. Jika peta memiliki menyimpan kunci sebagai referensi ke objek yang bisa berubah, itu akan bekerja dalam kasus di mana contoh yang sama digunakan untuk mengambil nilai. Namun pertimbangkan kasus berikut: 

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

Di atas adalah benar jika kunci disimpan sebagai referensi. Di Jawa biasanya demikian. Di .NET misalnya, jika kuncinya adalah tipe nilai (selalu dilewati oleh nilai), hasilnya akan berbeda:

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"

Teknologi lain mungkin memiliki perilaku berbeda. Namun, hampir semua dari mereka akan datang ke situasi di mana hasil dari menggunakan kunci yang bisa berubah tidak deterministik, yang merupakan situasi yang sangat sangat buruk dalam aplikasi - sulit untuk di-debug dan bahkan lebih sulit untuk dipahami.

5
Ivaylo Slavov

Jika kode hash kunci berubah setelah pasangan nilai kunci (Entri) disimpan di HashMap, peta tidak akan dapat mengambil Entri tersebut.

Kode hash kunci dapat berubah jika objek kunci dapat berubah. Kunci yang bisa berubah di HahsMap dapat menyebabkan hilangnya data.

4
Vishal

Seperti yang dijelaskan orang lain, itu berbahaya.

Cara untuk menghindarinya adalah dengan memiliki bidang const yang secara eksplisit memberikan hash pada objek yang bisa Anda ubah (jadi Anda akan hash pada "identitas" mereka, bukan "negara" mereka). Anda bahkan dapat menginisialisasi bidang hash lebih atau kurang secara acak. 

Trik lain adalah dengan menggunakan alamat, mis. (intptr_t) reinterpret_cast<void*>(this) sebagai dasar untuk hash.

Dalam semua kasus, Anda harus menyerah hashing perubahan status objek.

2

Perilaku Peta tidak ditentukan jika nilai suatu objek diubah dengan cara yang mempengaruhi sama dengan perbandingan sedangkan objek (Dapat diubah) adalah kunci. Bahkan untuk Set juga menggunakan objek yang bisa berubah karena kunci bukanlah ide yang baik. 

Mari kita lihat contoh di sini:

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;

}

}

Di sini kami mencoba menambahkan objek yang dapat diubah "Karyawan" ke peta. Ini akan bekerja dengan baik jika semua kunci yang ditambahkan berbeda. Di sini saya telah menimpa sama dengan dan kode hash untuk kelas karyawan.

Lihat dulu saya telah menambahkan "e" dan kemudian "e1". Untuk keduanya sama dengan () akan benar dan kode hash akan sama. Jadi peta melihat seolah-olah kunci yang sama ditambahkan sehingga harus mengganti nilai lama dengan nilai e1. Maka kita telah menambahkan e2, e3, e4 kita baik-baik saja seperti sekarang. 

Tetapi ketika kita mengubah nilai kunci yang sudah ditambahkan yaitu "e2" menjadi satu, itu menjadi kunci yang mirip dengan yang ditambahkan sebelumnya. Sekarang peta akan berperilaku kabel. Idealnya e2 harus mengganti kunci yang sama yaitu i.e e1.Tapi sekarang peta mengambil ini juga. Dan Anda akan mendapatkan ini di o/p:

 is e equals e1 true
{[email protected]=28, [email protected]=27, [email protected]=25, [email protected]=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : one:value : 25

Lihat di sini kedua tombol memiliki satu yang menunjukkan nilai yang sama juga. Jadi tidak terduga. Sekarang jalankan program yang sama lagi dengan mengubah e2.setName("diffnt"); yang e2.setName("one"); di sini ... Sekarang o/p akan seperti ini:

 is e equals e1 true
{[email protected]=28, [email protected]=27, [email protected]=25, [email protected]=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : diffnt:value : null

Jadi dengan menambahkan mengubah kunci yang bisa berubah di peta tidak dianjurkan. 

0
smruti ranjan