Bagaimana Java HashMap menangani objek yang berbeda dengan kode hash yang sama?

Sesuai pemahaman saya, saya pikir:

1. Sangat sah untuk dua objek memiliki kode hash yang sama.
2. Jika dua objek sama (menggunakan metode equals ()) maka mereka memiliki kode hash yang sama.
3. Jika dua objek tidak sama maka mereka tidak dapat memiliki kode hash yang sama

Apakah saya benar?

Sekarang jika benar, saya memiliki pertanyaan berikut: Secara HashMapinternal menggunakan kode hash objek. Jadi jika dua objek dapat memiliki kode hash yang sama, lalu bagaimana cara HashMapmelacak kunci yang digunakannya?

Bisakah seseorang menjelaskan bagaimana HashMapinternal menggunakan kode hash objek?

Hashmap berfungsi seperti ini (ini sedikit disederhanakan, tetapi menggambarkan mekanisme dasarnya):

Ia memiliki sejumlah "ember" yang digunakannya untuk menyimpan pasangan nilai kunci. Setiap ember memiliki nomor unik - itulah yang mengidentifikasi ember. Saat Anda menempatkan pasangan nilai kunci ke dalam peta, peta hash akan melihat kode hash kunci, dan menyimpan pasangan dalam ember yang pengenalnya adalah kode hash kunci. Misalnya: Kode hash kunci adalah 235 -> pasangan disimpan dalam nomor ember 235. (Perhatikan bahwa satu ember dapat menyimpan lebih dari satu pasangan nilai kunci).

Saat Anda mencari nilai dalam hashmap, dengan memberinya kunci, pertama-tama ia akan melihat kode hash kunci yang Anda berikan. Hashmap kemudian akan melihat ke dalam ember yang sesuai, dan kemudian akan membandingkan kunci yang Anda berikan dengan kunci semua pasangan dalam ember, dengan membandingkannya dengan equals().

Sekarang Anda dapat melihat bagaimana ini sangat efisien untuk mencari pasangan kunci-nilai di peta: dengan kode hash kunci, hashmap segera tahu di mana ember harus dilihat, sehingga hanya perlu menguji terhadap apa yang ada di ember itu.

Melihat mekanisme di atas, Anda juga dapat melihat persyaratan apa yang diperlukan pada hashCode()dan equals()metode kunci:

• Jika dua kunci adalah sama ( equals()kembali trueketika Anda membandingkannya), hashCode()metode mereka harus mengembalikan nomor yang sama. Jika kunci melanggar ini, maka kunci yang sama mungkin disimpan dalam ember yang berbeda, dan hashmap tidak akan dapat menemukan pasangan nilai kunci (karena akan terlihat di ember yang sama).

• Jika dua kunci berbeda, maka tidak masalah apakah kode hashnya sama atau tidak. Mereka akan disimpan dalam ember yang sama jika kode hash mereka sama, dan dalam kasus ini, hashmap akan digunakan equals()untuk membedakan mereka.

Penegasan ketiga Anda tidak benar.

Sangat sah untuk dua objek yang tidak sama memiliki kode hash yang sama. Ini digunakan HashMapsebagai "filter akses pertama" sehingga peta dapat dengan cepat menemukan entri yang mungkin dengan kunci yang ditentukan. Kunci dengan kode hash yang sama kemudian diuji untuk kesetaraan dengan kunci yang ditentukan.

Anda tidak akan ingin persyaratan bahwa dua benda yang tidak sama tidak bisa memiliki kode hash yang sama, karena kalau tidak itu akan membatasi Anda untuk 2 ³² objek mungkin. (Ini juga berarti bahwa tipe yang berbeda bahkan tidak bisa menggunakan bidang objek untuk menghasilkan kode hash, karena kelas lain dapat menghasilkan hash yang sama.)

HashMapadalah array dari Entryobjek.

Pertimbangkan HashMaphanya sebagai array objek.

Lihatlah apa ini Object:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

Setiap Entryobjek mewakili pasangan nilai kunci. Bidang nextmerujuk ke Entryobjek lain jika ember memiliki lebih dari satu Entry.

Terkadang mungkin terjadi bahwa kode hash untuk 2 objek berbeda adalah sama. Dalam hal ini, dua objek akan disimpan dalam satu ember dan akan disajikan sebagai daftar tertaut. Titik masuk adalah objek yang baru ditambahkan. Objek ini merujuk ke objek lain dengan nextbidang dan sebagainya. Entri terakhir mengacu pada null.

Ketika Anda membuat HashMapdengan konstruktor default

HashMap hashMap = new HashMap();

Array dibuat dengan ukuran 16 dan keseimbangan beban standar 0,75.

Menambahkan pasangan nilai kunci baru

1. Hitung kode hash untuk kunci tersebut
2. Hitung posisi di hash % (arrayLength-1)mana elemen harus ditempatkan (nomor ember)
3. Jika Anda mencoba menambahkan nilai dengan kunci yang telah disimpan HashMap, maka nilai akan ditimpa.
4. Jika tidak, elemen ditambahkan ke ember.

Jika ember sudah memiliki setidaknya satu elemen, yang baru akan ditambahkan dan ditempatkan di posisi pertama dari ember. Bidangnya nextmengacu pada elemen lama.

Penghapusan

1. Hitung kode hash untuk kunci yang diberikan
2. Hitung nomor ember hash % (arrayLength-1)
3. Dapatkan referensi ke objek Entri pertama dalam ember dan dengan cara yang sama, ulangi semua entri dalam ember yang diberikan. Akhirnya kita akan menemukan yang benar Entry. Jika elemen yang diinginkan tidak ditemukan, kembalinull

Anda dapat menemukan informasi yang sangat baik di http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Untuk meringkas:

HashMap bekerja berdasarkan prinsip hashing

put (key, value): HashMap menyimpan objek key dan value sebagai Map.Entry. Hashmap menerapkan kode hash (kunci) untuk mendapatkan ember. jika ada tabrakan, HashMap menggunakan LinkedList untuk menyimpan objek.

dapatkan (kunci): HashMap menggunakan kode hash Objek Kunci untuk mengetahui lokasi bucket dan kemudian memanggil metode keys.equals () untuk mengidentifikasi simpul yang benar di LinkedList dan mengembalikan objek nilai terkait untuk kunci tersebut di Java HashMap.

Berikut ini penjelasan kasar tentang HashMapmekanisme, untuk Java 8versi, (mungkin sedikit berbeda dengan Java 6) .

Struktur data

• Tabel
  hash Nilai hash dihitung melalui hash()tombol, dan itu menentukan ember hashtable mana yang akan digunakan untuk kunci yang diberikan.
• Daftar tertaut (tunggal)
  Saat jumlah elemen dalam ember kecil, daftar tertaut tunggal digunakan.
• Pohon Merah-Hitam
  Ketika jumlah elemen dalam ember besar, pohon merah-hitam digunakan.

Kelas (internal)

• Map.Entry
  Mewakili satu entitas dalam peta, entitas kunci / nilai.

• HashMap.Node
  Versi simpul daftar tautan.

  Itu bisa mewakili:

  • Ember hash.
    Karena memiliki properti hash.
  • Node dalam daftar tertaut tunggal, (dengan demikian juga kepala tertaut ) .
• HashMap.TreeNode
  Versi pohon dari node.

Bidang (internal)

• Node[] table
  Tabel ember, (kepala daftar yang ditautkan).
  Jika ember tidak mengandung elemen, maka itu nol, sehingga hanya mengambil ruang referensi.
• Set<Map.Entry> entrySet Set entitas.
• int size
  Jumlah entitas.
• float loadFactor
  Tunjukkan seberapa penuh tabel hash diizinkan, sebelum mengubah ukuran.
• int threshold
  Ukuran selanjutnya untuk mengubah ukuran.
  Rumus:threshold = capacity * loadFactor

Metode (internal)

• int hash(key)
  Hitung hash dengan kunci.

• Bagaimana cara memetakan hash ke bucket?
  Gunakan logika berikut:

  static int hashToBucket(int tableSize, int hash) {
      return (tableSize - 1) & hash;
  }

Tentang kapasitas

Dalam tabel hash, kapasitas berarti jumlah bucket, bisa didapat dari table.length.
Juga dapat dihitung melalui thresholddan loadFactor, dengan demikian tidak perlu didefinisikan sebagai bidang kelas.

Dapat memperoleh kapasitas efektif melalui: capacity()

Operasi

• Temukan entitas dengan kunci.
  Pertama temukan ember berdasarkan nilai hash, lalu lingkar daftar yang ditautkan atau cari pohon yang diurutkan.
• Tambahkan entitas dengan kunci.
  Pertama menemukan ember sesuai dengan nilai kunci.
  Kemudian coba cari nilainya:
  • Jika ditemukan, ganti nilainya.
  • Jika tidak, tambahkan simpul baru di awal daftar tertaut, atau masukkan ke pohon yang diurutkan.
• Ubah ukuran
  Ketika thresholdtercapai, akan menggandakan kapasitas hashtable ( table.length), kemudian melakukan hash ulang pada semua elemen untuk membangun kembali tabel.
  Ini bisa menjadi operasi yang mahal.

Performa

• Dapatkan & pakai
  Kompleksitas waktu adalah O(1), karena:
  • Bucket diakses melalui indeks array, dengan demikian O(1).
  • Daftar yang ditautkan dalam setiap ember memiliki panjang yang kecil, sehingga dapat dilihat sebagai O(1).
  • Ukuran pohon juga terbatas, karena akan menambah kapasitas & re-hash ketika jumlah elemen meningkat, sehingga bisa melihatnya sebagai O(1)tidak O(log N).

Kode hash menentukan ember mana yang harus diperiksa oleh hashmap. Jika ada lebih dari satu objek dalam bucket maka pencarian linier dilakukan untuk menemukan item mana dalam bucket yang sama dengan item yang diinginkan (menggunakan equals()metode).

Dengan kata lain, jika Anda memiliki kode hash yang sempurna maka akses hashmap konstan, Anda tidak akan perlu mengulangi melalui ember (secara teknis Anda juga harus memiliki ember MAX_INT, implementasi Java dapat berbagi beberapa kode hash dalam ember yang sama untuk mengurangi persyaratan ruang). Jika Anda memiliki kode hash terburuk (selalu mengembalikan nomor yang sama) maka akses hashmap Anda menjadi linier karena Anda harus mencari melalui setiap item di peta (mereka semua dalam ember yang sama) untuk mendapatkan apa yang Anda inginkan.

Sebagian besar kode hash yang ditulis dengan baik tidak sempurna tetapi cukup unik untuk memberi Anda akses yang lebih atau kurang konstan.

Anda salah pada poin tiga. Dua entri dapat memiliki kode hash yang sama tetapi tidak sama. Lihatlah implementasi HashMap.get dari OpenJdk . Anda dapat melihat bahwa itu memeriksa bahwa hash sama dan kunci sama. Jika koma tiga benar, maka tidak perlu untuk memeriksa bahwa kunci sama. Kode hash dibandingkan sebelum kunci karena yang pertama adalah perbandingan yang lebih efisien.

Jika Anda tertarik untuk belajar lebih banyak tentang ini, lihat artikel Wikipedia tentang Open Collision Resolution Collision , yang saya percaya adalah mekanisme yang digunakan oleh implementasi OpenJdk. Mekanisme yang agak berbeda dari pendekatan "ember" salah satu jawaban lain menyebutkan.

import java.util.HashMap;

public class Students  {
    String name;
    int age;

    Students(String name, int age ){
        this.name = name;
        this.age=age;
    }

    @Override
    public int hashCode() {
        System.out.println("__hash__");
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println("__eq__");
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Students other = (Students) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    public static void main(String[] args) {

        Students S1 = new Students("taj",22);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Output:

__ hash __

116232

__ hash __

116201

__ hash __

__ hash __

2

Jadi di sini kita melihat bahwa jika kedua objek S1 dan S2 memiliki konten yang berbeda, maka kami cukup yakin bahwa metode Hashcode kami yang ditimpa akan menghasilkan Hashcode yang berbeda (116232.1111601) untuk kedua objek. SEKARANG karena ada kode hash yang berbeda, sehingga tidak akan repot memanggil metode EQUALS. Karena Hashcode yang berbeda MENJAMIN konten yang BERBEDA dalam suatu objek.

    public static void main(String[] args) {

        Students S1 = new Students("taj",21);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Now lets change out main method a little bit. Output after this change is 

__ hash __

116201

__ hash __

116201

__ hash __

__ hash __

__ eq __

1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally  calls Equal method to verify this. 


Conclusion 
If hashcode is different , equal method will not get called. 
if hashcode is same, equal method will get called.

Thanks , hope it helps. 

dua objek sama, menyiratkan bahwa mereka memiliki kode hash yang sama, tetapi tidak sebaliknya.

2 objek yang sama ------> mereka memiliki kode hash yang sama

2 objek memiliki kode hash yang sama ---- xxxxx -> mereka TIDAK sama

Pembaruan Java 8 di HashMap-

Anda melakukan operasi ini dalam kode Anda -

myHashmap.put("old","old-value");
myHashMap.put("very-old","very-old-value");

jadi, anggap kode hash Anda dikembalikan untuk kedua tombol "old"dan "very-old"sama. Lalu apa yang akan terjadi.

myHashMapadalah HashMap, dan misalkan pada awalnya Anda tidak menentukan kapasitasnya. Jadi kapasitas default sesuai java adalah 16. Jadi sekarang segera setelah Anda menginisialisasi hashmap menggunakan kata kunci baru, itu menciptakan 16 ember. sekarang ketika Anda mengeksekusi statement- pertama

myHashmap.put("old","old-value");

kemudian kode hash "old"dihitung, dan karena kode hash bisa berupa bilangan bulat yang sangat besar juga, jadi, java melakukan ini secara internal - (hash adalah kode hash di sini dan >>> adalah pergeseran yang benar)

hash XOR hash >>> 16

jadi untuk memberikan gambar yang lebih besar, itu akan mengembalikan beberapa indeks, yang akan menjadi antara 0 hingga 15. Sekarang pasangan nilai kunci Anda "old"dan "old-value"akan dikonversi ke kunci objek Entry dan variabel instance nilai. dan kemudian objek entri ini akan disimpan dalam ember, atau Anda dapat mengatakan bahwa pada indeks tertentu, objek entri ini akan disimpan.

FYI- Entri adalah kelas di antarmuka Peta- Peta. Masukkan, dengan tanda tangan / definisi ini

class Entry{
          final Key k;
          value v;
          final int hash;
          Entry next;
}

sekarang ketika Anda menjalankan pernyataan berikutnya -

myHashmap.put("very-old","very-old-value");

dan "very-old"memberikan kode hash yang sama dengan "old", sehingga pasangan nilai kunci baru ini dikirim lagi ke indeks yang sama atau ember yang sama. Tetapi karena bucket ini tidak kosong, maka nextvariabel objek Entry digunakan untuk menyimpan pasangan nilai kunci baru ini.

dan ini akan disimpan sebagai daftar tertaut untuk setiap objek yang memiliki kode hash yang sama, tetapi TRIEFY_THRESHOLD ditentukan dengan nilai 6. jadi setelah mencapai ini, daftar tertaut dikonversi ke pohon seimbang (pohon merah-hitam) dengan elemen pertama sebagai akar.

Setiap objek entri mewakili pasangan nilai kunci. Bidang selanjutnya merujuk ke objek Entri lainnya jika ember memiliki lebih dari 1 Entri.

Terkadang mungkin terjadi bahwa kode hash untuk 2 objek berbeda adalah sama. Dalam hal ini 2 objek akan disimpan dalam satu ember dan akan disajikan sebagai LinkedList. Titik masuk adalah objek yang baru ditambahkan. Objek ini merujuk ke objek lain dengan bidang selanjutnya dan seterusnya. Entri terakhir mengacu pada nol. Saat Anda membuat HashMap dengan konstruktor default

Array dibuat dengan ukuran 16 dan keseimbangan beban standar 0,75.

(Sumber)

Peta hash bekerja berdasarkan prinsip hashing

Metode HashMap get (Key k) memanggil metode hashCode pada objek kunci dan menerapkan hashValue yang dikembalikan ke fungsi hash statisnya sendiri untuk menemukan lokasi bucket (array backing) di mana kunci dan nilai disimpan dalam bentuk kelas bersarang yang disebut Entri (Peta. Masuk) . Jadi Anda telah menyimpulkan bahwa dari baris sebelumnya bahwa Kedua kunci dan nilai disimpan dalam ember sebagai bentuk objek Entri. Jadi berpikir bahwa nilai Hanya disimpan dalam ember tidak benar dan tidak akan memberikan kesan yang baik pada pewawancara.

• Setiap kali kita memanggil metode get (Key k) pada objek HashMap. Pertama memeriksa apakah kunci adalah nol atau tidak. Perhatikan bahwa hanya ada satu kunci nol di HashMap.

Jika kunci nol, maka kunci kosong selalu memetakan ke hash 0, dengan demikian indeks 0.

Jika kunci bukan nol maka akan memanggil fungsi pada objek kunci, lihat baris 4 pada metode di atas yaitu key.hashCode (), jadi setelah key.hashCode () mengembalikan hashValue, baris 4 terlihat seperti

            int hash = hash(hashValue)

dan sekarang, ini berlaku hashValue dikembalikan ke fungsi hashing sendiri.

Kita mungkin bertanya-tanya mengapa kita menghitung nilai hash lagi menggunakan hash (hashValue). Jawabannya adalah itu membela terhadap fungsi hash kualitas buruk.

Sekarang nilai hash akhir digunakan untuk menemukan lokasi bucket tempat objek Entri disimpan. Objek entri disimpan dalam bucket seperti ini (hash, key, value, bucketindex)

Saya tidak akan masuk ke rincian tentang cara kerja HashMap, tetapi akan memberikan contoh sehingga kita bisa mengingat bagaimana HashMap bekerja dengan menghubungkannya dengan kenyataan.

Kami memiliki Key, Value, HashCode, dan bucket.

Untuk beberapa saat, kami akan menghubungkan mereka masing-masing dengan yang berikut:

• Bucket -> A Society
• HashCode -> alamat Society (selalu unik)
• Nilai -> Rumah di Masyarakat
• Kunci -> alamat rumah.

Menggunakan Map.get (kunci):

Stevie ingin pergi ke rumah temannya (Josse) yang tinggal di sebuah vila di sebuah masyarakat VIP, biarlah itu JavaLovers Society. Alamat Josse adalah SSN-nya (yang berbeda untuk semua orang). Ada indeks yang dipertahankan di mana kami menemukan nama Society berdasarkan SSN. Indeks ini dapat dianggap sebagai algoritma untuk mengetahui HashCode.

• Nama Masyarakat SSN
• 92313 (Josse's) - JavaLovers
• 13214 - AngularJSLovers
• 98080 - JavaLovers
• 53808 - Pecinta Biologi

1. SSN (kunci) ini pertama memberi kita HashCode (dari tabel indeks) yang tidak lain adalah nama Society.
2. Sekarang, rumah mulitple dapat berada di masyarakat yang sama, sehingga HashCode bisa menjadi umum.
3. Misalkan, Masyarakat adalah umum untuk dua rumah, bagaimana kita akan mengidentifikasi rumah yang akan kita kunjungi, ya, dengan menggunakan kunci (SSN) yang tidak lain adalah alamat rumah

Menggunakan Map.put (kunci, Nilai)

Ini menemukan masyarakat yang cocok untuk Nilai ini dengan menemukan HashCode dan kemudian nilainya disimpan.

Saya harap ini membantu dan ini terbuka untuk modifikasi.

Ini akan menjadi jawaban yang panjang, minum dan baca terus ...

Hashing adalah tentang menyimpan pasangan nilai kunci dalam memori yang dapat dibaca dan ditulis lebih cepat. Ini menyimpan kunci dalam array dan nilai-nilai dalam LinkedList.

Katakanlah saya ingin menyimpan 4 pasangan nilai kunci -

{
“girl” => “ahhan” , 
“misused” => “Manmohan Singh” , 
“horsemints” => “guess what”, 
“no” => “way”
}

Jadi untuk menyimpan kunci, kita membutuhkan array 4 elemen. Sekarang bagaimana cara memetakan salah satu dari 4 kunci ini ke 4 indeks array (0,1,2,3)?

Jadi java menemukan kode hash kunci individu dan memetakannya ke indeks array tertentu. Rumus Hashcode adalah -

1) reverse the string.

2) keep on multiplying ascii of each character with increasing power of 31 . then add the components .

3) So hashCode() of girl would be –(ascii values of  l,r,i,g are 108, 114, 105 and 103) . 

e.g. girl =  108 * 31^0  + 114 * 31^1  + 105 * 31^2 + 103 * 31^3  = 3173020

Hash and girl !! Saya tahu apa yang Anda pikirkan. Ketertarikan Anda tentang duet liar itu mungkin membuat Anda kehilangan hal penting.

Mengapa java mengalikannya dengan 31?

Itu karena, 31 adalah prime aneh dalam bentuk 2 ^ 5 - 1. Dan prime prime mengurangi kemungkinan Hash Collision

Sekarang bagaimana kode hash ini dipetakan ke indeks array?

jawabannya adalah Hash Code % (Array length -1) ,. Jadi “girl”dipetakan ke (3173020 % 3) = 1dalam kasus kami. yang merupakan elemen kedua dari array.

dan nilai "ahhan" disimpan dalam LinkedList yang terkait dengan indeks array 1.

HashCollision - Jika Anda mencoba menemukan hasHCodekunci “misused”dan “horsemints”menggunakan formula yang dijelaskan di atas Anda akan melihat keduanya memberi kami sama 1069518484. Whooaa !! pelajaran yang dipetik -

2 objek yang sama harus memiliki kode hash yang sama tetapi tidak ada jaminan jika kode hash cocok dengan objek yang sama. Jadi itu harus menyimpan kedua nilai yang sesuai dengan "disalahgunakan" dan "horsemints" ke bucket 1 (1069518484% 3).

Sekarang peta hash terlihat seperti -

Array Index 0 –
Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”)
Array Index 2 – LinkedList (“way”)
Array Index 3 – 

Sekarang jika beberapa badan mencoba menemukan nilai untuk kunci “horsemints”, java dengan cepat akan menemukan kode hash itu, modul itu dan mulai mencari nilainya di LinkedList yang sesuai index 1. Jadi dengan cara ini kita tidak perlu mencari semua indeks 4 array sehingga membuat akses data lebih cepat.

Tapi, tunggu, sebentar. ada 3 nilai dalam tertaut terkait Array indeks 1, bagaimana ia mengetahui mana yang merupakan nilai untuk "horsemints" kunci?

Sebenarnya saya berbohong, ketika saya mengatakan HashMap hanya menyimpan nilai dalam LinkedList.

Ini menyimpan kedua pasangan nilai kunci sebagai entri peta. Jadi sebenarnya Map terlihat seperti ini.

Array Index 0 –
Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>)
Array Index 2 – LinkedList (<”no” => “way”>)
Array Index 3 – 

Sekarang Anda dapat melihat Saat melintasi melalui LinkedList yang sesuai dengan ArrayIndex1, ia sebenarnya membandingkan kunci dari setiap entri dari LinkedList itu dengan “horsemints” dan ketika ia menemukannya, ia hanya mengembalikan nilai itu.

Semoga Anda bersenang-senang saat membacanya :)

Seperti yang dikatakan, gambar bernilai 1000 kata. Saya katakan: beberapa kode lebih baik dari 1000 kata. Berikut kode sumber HashMap. Dapatkan metode:

/**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

Jadi menjadi jelas bahwa hash digunakan untuk menemukan "ember" dan elemen pertama selalu diperiksa dalam ember itu. Jika tidak, maka equalskunci tersebut digunakan untuk menemukan elemen aktual dalam daftar tertaut.

Mari kita lihat put()metodenya:

  /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

Ini sedikit lebih rumit, tetapi menjadi jelas bahwa elemen baru diletakkan di tab pada posisi yang dihitung berdasarkan hash:

i = (n - 1) & hashdi sini iadalah indeks di mana elemen baru akan diletakkan (atau itu adalah "ember"). nadalah ukuran tabarray (array "ember").

Pertama, dicoba untuk dimasukkan sebagai elemen pertama dalam "ember" itu. Jika sudah ada elemen, maka tambahkan node baru ke daftar.