Implementasi HashMap Java 8

93

Sesuai dokumen tautan berikut: Implementasi Java HashMap

Saya bingung dengan implementasi HashMap(atau lebih tepatnya, peningkatan dalam HashMap). Pertanyaan saya adalah:

pertama

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Mengapa dan bagaimana konstanta ini digunakan? Saya ingin beberapa contoh yang jelas untuk ini. Bagaimana mereka mencapai perolehan kinerja dengan ini?

Kedua

Jika Anda melihat kode sumber HashMapdi JDK, Anda akan menemukan kelas dalam statis berikut:

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
    HashMap.TreeNode<K, V> parent;
    HashMap.TreeNode<K, V> left;
    HashMap.TreeNode<K, V> right;
    HashMap.TreeNode<K, V> prev;
    boolean red;

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
        super(arg0, arg1, arg2, arg3);
    }

    final HashMap.TreeNode<K, V> root() {
        HashMap.TreeNode arg0 = this;

        while (true) {
            HashMap.TreeNode arg1 = arg0.parent;
            if (arg0.parent == null) {
                return arg0;
            }

            arg0 = arg1;
        }
    }
    //...
}

Bagaimana cara menggunakannya? Saya hanya ingin penjelasan tentang algoritmanya .

java dictionary java-8 hashmap Hasnain Ali Bohra
sumber

Jawaban:

226

HashMapberisi sejumlah ember. Itu menggunakanhashCode untuk menentukan ember mana untuk memasukkan ini. Demi kesederhanaan, bayangkan itu sebagai modulus.

Jika hashcode kita 123456 dan kita punya 4 bucket, 123456 % 4 = 0maka itemnya masuk ke bucket pertama, Bucket 1.

HashMap

Jika fungsi kode hash kita bagus, itu harus menyediakan distribusi yang merata sehingga semua keranjang akan digunakan secara merata. Dalam kasus ini, keranjang menggunakan daftar tertaut untuk menyimpan nilai.

Keranjang Tertaut

Tapi Anda tidak bisa mengandalkan orang untuk mengimplementasikan fungsi hash yang baik. Orang akan sering menulis fungsi hash yang buruk yang akan menghasilkan distribusi yang tidak merata. Mungkin juga kita bisa saja tidak beruntung dengan masukan kita.

Hashmap buruk

Semakin sedikit distribusi ini, semakin jauh kita bergerak dari operasi O (1) dan semakin dekat kita bergerak menuju operasi O (n).

Penerapan Hashmap mencoba mengurangi hal ini dengan mengatur beberapa keranjang ke dalam pohon daripada daftar terkait jika keranjang menjadi terlalu besar. Ini untuk apa TREEIFY_THRESHOLD = 8. Jika ember berisi lebih dari delapan item, itu harus menjadi pohon.

Bucket Pohon

Pohon ini adalah pohon Merah-Hitam. Ini pertama kali diurutkan berdasarkan kode hash. Jika kode hashnya sama, ia menggunakan compareTometodeComparable jika objek mengimplementasikan antarmuka kode hash identitas.

Jika entri dihapus dari peta, jumlah entri dalam keranjang mungkin berkurang sehingga struktur pohon ini tidak lagi diperlukan. Itulah gunanya UNTREEIFY_THRESHOLD = 6. Jika jumlah elemen dalam keranjang turun di bawah enam, sebaiknya kita kembali menggunakan daftar tertaut.

Terakhir, ada MIN_TREEIFY_CAPACITY = 64.

Saat ukuran peta hash bertambah, ukurannya otomatis diubah untuk memiliki lebih banyak keranjang. Jika kita memiliki peta hash kecil, kemungkinan kita mendapatkan ember yang sangat penuh cukup tinggi, karena kita tidak memiliki banyak ember berbeda untuk memasukkan barang. Jauh lebih baik untuk memiliki peta hash yang lebih besar, dengan lebih banyak ember yang kurang penuh. Konstanta ini pada dasarnya mengatakan untuk tidak mulai membuat keranjang menjadi pohon jika peta hash kita sangat kecil - ukurannya harus diubah terlebih dahulu menjadi lebih besar.

Untuk menjawab pertanyaan Anda tentang perolehan kinerja, pengoptimalan ini ditambahkan untuk meningkatkan kasus terburuk . Saya hanya berspekulasi tetapi Anda mungkin hanya akan melihat peningkatan kinerja yang nyata karena pengoptimalan ini jika hashCodefungsi Anda tidak terlalu baik.

Michael
sumber
3
Distribusi tidak merata tidak selalu merupakan tanda fungsi hash yang buruk. Beberapa tipe data, misalnya String, memiliki ruang nilai yang jauh lebih besar daripada intkode hash, oleh karena itu, tabrakan tidak dapat dihindari. Sekarang tergantung pada nilai aktual, seperti nilai aktual String, yang Anda masukkan ke dalam peta, apakah Anda mendapatkan distribusi yang merata atau tidak. Distribusi yang buruk bisa jadi hanya karena kesialan.
Holger
3
+1, Saya ingin menambahkan bahwa skenario spesifik yang dimitigasi oleh pendekatan pohon ini adalah serangan DOS tabrakan hash . java.lang.Stringmemiliki deterministik, non-kriptografik hashCode, sehingga penyerang dapat dengan mudah membuat String berbeda dengan kode hash yang bertabrakan. Sebelum pengoptimalan ini, ini dapat menurunkan operasi HashMap menjadi O (n) -time, sekarang hanya menurunkannya menjadi O (log (n)).
MikeFHay
1
+1, if the objects implement that interface, else the identity hash code.saya sedang mencari bagian lain ini.
Nomor 945
1
@NateGlenn kode hash default jika Anda tidak menimpanya
Michael
Saya tidak mengerti "Konstanta ini pada dasarnya mengatakan untuk tidak mulai membuat keranjang menjadi pohon jika peta hash kita sangat kecil - ukurannya harus diubah menjadi lebih besar terlebih dahulu." untuk MIN_TREEIFY_CAPACITY. Apakah ini berarti "Setelah kita memasukkan kunci yang akan di-hash ke keranjang yang sudah berisi 8 ( TREEIFY_THRESHOLD) kunci dan jika sudah ada 64 ( MIN_TREEIFY_CAPACITY) kunci HashMap, daftar tertaut dari keranjang itu akan diubah menjadi pohon yang seimbang."
anir
16

Untuk membuatnya lebih sederhana (sebanyak yang saya bisa lebih sederhana) + beberapa detail lainnya.

Properti ini bergantung pada banyak hal internal yang akan sangat keren untuk dipahami - sebelum berpindah ke properti tersebut secara langsung.

TREEIFY_THRESHOLD -> ketika satu keranjang mencapai ini (dan jumlahnya melebihi MIN_TREEIFY_CAPACITY), itu diubah menjadi simpul pohon merah / hitam yang seimbang sempurna . Mengapa? Karena kecepatan pencarian. Pikirkan dengan cara yang berbeda:

itu akan membutuhkan paling banyak 32 langkah untuk mencari Entri dalam bucket / bin dengan entri Integer.MAX_VALUE .

Beberapa intro untuk topik berikutnya. Mengapa jumlah nampan / ember selalu pangkat dua ? Setidaknya dua alasan: lebih cepat dari operasi modulo dan modulo pada bilangan negatif akan menjadi negatif. Dan Anda tidak dapat memasukkan Entri ke dalam keranjang "negatif":

 int arrayIndex = hashCode % buckets; // will be negative

 buckets[arrayIndex] = Entry; // obviously will fail

Sebaliknya, ada trik bagus yang digunakan sebagai pengganti modulo:

 (n - 1) & hash // n is the number of bins, hash - is the hash function of the key

Itu secara semantik sama dengan operasi modulo. Ini akan menjaga bit yang lebih rendah. Ini memiliki konsekuensi yang menarik ketika Anda melakukannya:

Map<String, String> map = new HashMap<>();

Dalam kasus di atas, keputusan kemana entri akan diambil berdasarkan 4 bit terakhir hanya dari kode hash Anda.

Di sinilah mengalikan ember berperan. Dalam kondisi tertentu (akan membutuhkan banyak waktu untuk menjelaskan dengan detail yang tepat ), ukuran bucket menjadi dua kali lipat. Mengapa? Ketika ukuran ember digandakan, ada satu bit lagi yang ikut bermain .

Jadi Anda memiliki 16 ember - 4 bit terakhir dari kode hash memutuskan kemana entri akan dimasukkan. Anda menggandakan ember: 32 ember - 5 bit terakhir memutuskan ke mana entri akan pergi.

Karena itu, proses ini disebut hashing ulang. Ini mungkin lambat. Artinya (untuk orang yang peduli) karena HashMap "bercanda" sebagai: cepat, cepat, cepat, slooow . Ada implementasi lain - cari hashmap yang tidak dijeda ...

Sekarang UNTREEIFY_THRESHOLD mulai berfungsi setelah melakukan hashing ulang. Pada titik itu, beberapa entri mungkin berpindah dari nampan ini ke yang lain (mereka menambahkan satu bit lagi ke (n-1)&hashkomputasi - dan dengan demikian mungkin pindah ke keranjang lain ) dan mungkin mencapai ini UNTREEIFY_THRESHOLD. Pada titik ini, tidak ada gunanya menyimpan tempat sampah sebagai red-black tree node, tetapi sebagai LinkedListgantinya, suka

 entry.next.next....

MIN_TREEIFY_CAPACITY adalah jumlah minimum keranjang sebelum keranjang tertentu diubah menjadi Pohon.

Eugene
sumber
10

TreeNodeadalah cara alternatif untuk menyimpan entri milik satu bin dari file HashMap. Dalam implementasi yang lebih lama, entri bin disimpan dalam daftar tertaut. Di Java 8, jika jumlah entri dalam sebuah bin melewati ambang ( TREEIFY_THRESHOLD), mereka disimpan dalam struktur pohon alih-alih daftar tertaut asli. Ini adalah pengoptimalan.

Dari implementasi:

/*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.
Eran
sumber
tidak sepenuhnya benar. Jika mereka lulus TREEIFY_THRESHOLD DAN jumlah totalnya paling sedikit MIN_TREEIFY_CAPACITY. Saya sudah mencoba untuk menutupi itu dalam jawaban saya ...
Eugene
3

Anda perlu memvisualisasikannya: katakanlah ada Kunci Kelas dengan hanya fungsi hashCode () yang diganti untuk selalu mengembalikan nilai yang sama

public class Key implements Comparable<Key>{

  private String name;

  public Key (String name){
    this.name = name;
  }

  @Override
  public int hashCode(){
    return 1;
  }

  public String keyName(){
    return this.name;
  }

  public int compareTo(Key key){
    //returns a +ve or -ve integer 
  }

}

dan kemudian di tempat lain, saya memasukkan 9 entri ke dalam HashMap dengan semua kunci menjadi contoh dari kelas ini. misalnya

Map<Key, String> map = new HashMap<>();

    Key key1 = new Key("key1");
    map.put(key1, "one");

    Key key2 = new Key("key2");
    map.put(key2, "two");
    Key key3 = new Key("key3");
    map.put(key3, "three");
    Key key4 = new Key("key4");
    map.put(key4, "four");
    Key key5 = new Key("key5");
    map.put(key5, "five");
    Key key6 = new Key("key6");
    map.put(key6, "six");
    Key key7 = new Key("key7");
    map.put(key7, "seven");
    Key key8 = new Key("key8");
    map.put(key8, "eight");

//Since hascode is same, all entries will land into same bucket, lets call it bucket 1. upto here all entries in bucket 1 will be arranged in LinkedList structure e.g. key1 -> key2-> key3 -> ...so on. but when I insert one more entry 

    Key key9 = new Key("key9");
    map.put(key9, "nine");

  threshold value of 8 will be reached and it will rearrange bucket1 entires into Tree (red-black) structure, replacing old linked list. e.g.

                  key1
                 /    \
               key2   key3
              /   \   /  \

Tree traversal lebih cepat {O (log n)} daripada LinkedList {O (n)} dan saat n bertambah, perbedaannya menjadi lebih signifikan.

rentedrainbow
sumber
Itu tidak mungkin membangun pohon yang efisien karena tidak ada cara untuk membandingkan kunci selain kode hash mereka, yang semuanya sama, dan metode yang sama, yang tidak membantu dalam pengurutan.
user253751
@ imibis Kode hash mereka belum tentu sama. Mereka sangat mungkin berbeda. Jika kelas menerapkannya, itu juga akan digunakan compareTodari Comparable. identityHashCodeadalah mekanisme lain yang digunakannya.
Michael
@Michael Dalam contoh ini semua kode hash harus sama dan kelas tidak mengimplementasikan Comparable. identityHashCode tidak akan berguna dalam menemukan node yang benar.
pengguna253751
@ imibis Ah ya, saya hanya membacanya tapi kamu benar. Jadi, karena Keytidak diimplementasikan Comparable, identityHashCodeakan digunakan :)
Michael
@EmonMishra sayangnya, hanya untuk visual tidak akan cukup, saya sudah mencoba untuk menutupi itu dalam jawaban saya.
Eugene
2

Perubahan dalam implementasi HashMap telah ditambahkan dengan JEP-180 . Tujuannya adalah untuk:

Tingkatkan kinerja java.util.HashMap di bawah kondisi tabrakan hash tinggi dengan menggunakan pohon seimbang daripada daftar tertaut untuk menyimpan entri peta. Terapkan peningkatan yang sama di kelas LinkedHashMap

Namun kinerja murni bukanlah satu-satunya keuntungan. Ini juga akan mencegah serangan HashDoS , jika peta hash digunakan untuk menyimpan input pengguna, karena pohon merah-hitam yang digunakan untuk menyimpan data di bucket memiliki kompleksitas penyisipan kasus terburuk di O (log n). Pohon itu digunakan setelah kriteria tertentu terpenuhi - lihat jawaban Eugene .

Anton Krosnev
sumber
-1

Untuk memahami implementasi internal hashmap, Anda perlu memahami hashing. Hashing dalam bentuknya yang paling sederhana, adalah cara untuk menetapkan kode unik untuk variabel / objek apa pun setelah menerapkan rumus / algoritme apa pun pada propertinya.

Fungsi hash yang benar harus mengikuti aturan ini -

“Fungsi hash harus mengembalikan kode hash yang sama setiap kali fungsi diterapkan pada objek yang sama atau sama. Dengan kata lain, dua objek yang sama harus menghasilkan kode hash yang sama secara konsisten. "

Avinash
sumber
Ini tidak menjawab pertanyaan itu.
Stephen C.