Bagaimana HashTables menangani tabrakan?

Saya pernah mendengar di kelas gelar saya bahwa a HashTableakan menempatkan entri baru ke dalam ember 'berikutnya yang tersedia' jika entri Kunci baru bertabrakan dengan yang lain.

Bagaimana HashTablemasih mengembalikan Nilai yang benar jika tabrakan ini terjadi saat memanggil satu punggung dengan kunci tabrakan?

Saya berasumsi bahwa tipe Keysare Stringdan hashCode()mengembalikan default yang dihasilkan oleh katakanlah Java.

Jika saya menerapkan fungsi hashing saya sendiri dan menggunakannya sebagai bagian dari tabel pencarian (yaitu a HashMapatau Dictionary), strategi apa yang ada untuk menangani tabrakan?

Saya bahkan pernah melihat not yang berhubungan dengan bilangan prima! Informasi tidak begitu jelas dari pencarian Google.

Tabel hash menangani tabrakan dengan salah satu dari dua cara.

Opsi 1: Dengan membuat setiap keranjang berisi daftar elemen tertaut yang di-hash ke keranjang itu. Inilah sebabnya mengapa fungsi hash yang buruk dapat membuat pencarian di tabel hash menjadi sangat lambat.

Opsi 2: Jika entri tabel hash semuanya penuh maka tabel hash dapat menambah jumlah keranjang yang dimilikinya dan kemudian mendistribusikan kembali semua elemen dalam tabel. Fungsi hash mengembalikan integer dan tabel hash harus mengambil hasil dari fungsi hash dan memodifikasinya dengan ukuran tabel sehingga dapat dipastikan akan masuk ke keranjang. Jadi dengan meningkatkan ukuran, itu akan mengulangi dan menjalankan perhitungan modulo yang jika Anda beruntung dapat mengirim objek ke keranjang yang berbeda.

Java menggunakan opsi 1 dan 2 dalam implementasi tabel hash-nya.

Ketika Anda berbicara tentang "Tabel Hash akan menempatkan entri baru ke dalam keranjang 'berikutnya yang tersedia' jika entri Kunci baru bertabrakan dengan yang lain.", Anda berbicara tentang strategi pengalamatan terbuka resolusi tabrakan dari tabel hash.

Ada beberapa strategi untuk tabel hash untuk mengatasi tabrakan.

Jenis metode besar pertama mengharuskan kunci (atau penunjuk ke mereka) disimpan dalam tabel, bersama dengan nilai terkait, yang selanjutnya mencakup:

• Rantai terpisah

• Buka pengalamatan

• Hashing yang digabungkan
• Cuckoo hashing
• Robin Hood melakukan hashing
• Pencirian 2 pilihan
• Mencirikan hopscotch

Metode penting lainnya untuk menangani tabrakan adalah dengan mengubah ukuran dinamis , yang selanjutnya memiliki beberapa cara:

• Mengubah ukuran dengan menyalin semua entri
• Perubahan ukuran tambahan
• Kunci monotonik

EDIT : yang di atas dipinjam dari wiki_hash_table , di mana Anda harus melihat-lihat untuk mendapatkan info lebih lanjut.

Ada beberapa teknik yang tersedia untuk menangani tabrakan. Saya akan menjelaskan beberapa di antaranya

Chaining: Dalam chaining kita menggunakan indeks array untuk menyimpan nilai. Jika kode hash dari nilai kedua juga menunjuk ke indeks yang sama maka kami mengganti nilai indeks itu dengan daftar tertaut dan semua nilai yang menunjuk ke indeks itu disimpan dalam daftar tertaut dan poin indeks larik aktual ke kepala daftar tertaut. Tetapi jika hanya ada satu kode hash yang menunjuk ke indeks array maka nilainya langsung disimpan dalam indeks itu. Logika yang sama diterapkan saat mengambil nilai. Ini digunakan di Java HashMap / Hashtable untuk menghindari tabrakan.

Linear probing: Teknik ini digunakan ketika kita memiliki lebih banyak indeks dalam tabel daripada nilai yang akan disimpan. Teknik probing linier bekerja pada konsep terus bertambah sampai Anda menemukan slot kosong. Kode pseudo terlihat seperti ini:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Teknik hashing ganda: Dalam teknik ini kita menggunakan dua fungsi hashing h1 (k) dan h2 (k). Jika slot pada h1 (k) terisi maka fungsi hashing kedua h2 (k) digunakan untuk menaikkan indeks. Pseudo-code terlihat seperti ini:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

Teknik probing linier dan hashing ganda adalah bagian dari teknik pengalamatan terbuka dan hanya dapat digunakan jika slot yang tersedia lebih dari jumlah item yang akan ditambahkan. Dibutuhkan lebih sedikit memori daripada chaining karena tidak ada struktur tambahan yang digunakan di sini tetapi lambat karena banyak pergerakan terjadi hingga kami menemukan slot kosong. Juga dalam teknik pengalamatan terbuka ketika sebuah item dikeluarkan dari slot kami meletakkan batu nisan untuk menunjukkan bahwa item tersebut dihapus dari sini itulah mengapa itu kosong.

Untuk informasi lebih lanjut lihat situs ini .

Saya sangat menyarankan Anda untuk membaca posting blog ini yang muncul di HackerNews baru-baru ini: Bagaimana HashMap bekerja di Java

Singkatnya, jawabannya adalah

Apa yang akan terjadi jika dua objek kunci HashMap yang berbeda memiliki kode hash yang sama?

Mereka akan disimpan dalam keranjang yang sama tetapi tidak ada simpul berikutnya dari daftar tertaut. Dan metode kunci sama dengan () akan digunakan untuk mengidentifikasi pasangan nilai kunci yang benar di HashMap.

Saya pernah mendengar di kelas gelar saya bahwa HashTable akan menempatkan entri baru ke dalam ember 'berikutnya yang tersedia' jika entri Kunci baru bertabrakan dengan yang lain.

Ini sebenarnya tidak benar, setidaknya untuk Oracle JDK (ini adalah detail implementasi yang dapat bervariasi antara implementasi API yang berbeda). Sebaliknya, setiap keranjang berisi daftar entri yang ditautkan sebelum Java 8, dan pohon yang seimbang di Java 8 atau lebih tinggi.

lalu bagaimana HashTable masih mengembalikan Nilai yang benar jika tabrakan ini terjadi saat memanggil satu bagian belakang dengan kunci tabrakan?

Ini menggunakan equals()untuk menemukan entri yang benar-benar cocok.

Jika saya menerapkan fungsi hashing saya sendiri dan menggunakannya sebagai bagian dari tabel pencarian (yaitu HashMap atau Kamus), strategi apa yang ada untuk menangani tabrakan?

Ada berbagai strategi penanganan tabrakan dengan kelebihan dan kekurangan yang berbeda. Entri Wikipedia tentang tabel hash memberikan gambaran yang bagus.

Pembaruan sejak Java 8: Java 8 menggunakan pohon yang seimbang untuk penanganan tabrakan, meningkatkan kasus terburuk dari O (n) ke O (log n) untuk pencarian. Penggunaan self-balanced tree diperkenalkan di Java 8 sebagai perbaikan atas chaining (digunakan hingga java 7), yang menggunakan linked-list, dan memiliki kasus terburuk O (n) untuk pencarian (karena perlu melintasi Daftar)

Untuk menjawab bagian kedua dari pertanyaan Anda, penyisipan dilakukan dengan memetakan elemen tertentu ke indeks tertentu dalam larik yang mendasari dari hashmap, namun, saat tabrakan terjadi, semua elemen harus tetap dipertahankan (disimpan dalam struktur data sekunder , dan tidak hanya diganti dalam larik yang mendasari). Ini biasanya dilakukan dengan membuat setiap komponen-array (slot) menjadi struktur data sekunder (alias keranjang), dan elemen ditambahkan ke keranjang yang berada di indeks-array yang diberikan (jika kunci belum ada di keranjang, di yang mana itu diganti).

Selama pencarian, kunci di-hash ke indeks-array yang sesuai, dan pencarian dilakukan untuk elemen yang cocok dengan kunci (tepat) dalam keranjang yang diberikan. Karena bucket tidak perlu menangani tabrakan (membandingkan kunci secara langsung), ini memecahkan masalah tabrakan, tetapi melakukannya dengan biaya harus melakukan penyisipan dan pencarian pada struktur data sekunder. Poin kuncinya adalah bahwa dalam peta hash, baik kunci maupun nilainya disimpan, dan bahkan jika hash bertabrakan, kunci akan dibandingkan secara langsung untuk persamaan (dalam keranjang), dan karenanya dapat diidentifikasi secara unik dalam keranjang.

Penanganan-benturan membawa kinerja penyisipan dan pencarian kasus terburuk dari O (1) dalam kasus tidak ada penanganan-tabrakan ke O (n) untuk rantai (daftar tertaut digunakan sebagai struktur data sekunder) dan O (log n) untuk pohon yang seimbang.

Referensi:

Java 8 telah hadir dengan perbaikan / perubahan objek HashMap berikut jika terjadi tabrakan tinggi.

• Fungsi hash String alternatif yang ditambahkan di Java 7 telah dihapus.

• Bucket yang berisi sejumlah besar kunci yang bertabrakan akan menyimpan entri mereka di pohon seimbang, bukan di daftar tertaut setelah ambang tertentu tercapai.

Perubahan di atas memastikan kinerja O (log (n)) dalam skenario terburuk ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 )

Ini akan menggunakan metode sama dengan untuk melihat apakah kunci ada bahkan dan terutama jika ada lebih dari satu elemen dalam keranjang yang sama.

Karena ada beberapa kebingungan tentang algoritma mana yang digunakan HashMap Java (dalam implementasi Sun / Oracle / OpenJDK), berikut cuplikan kode sumber yang relevan (dari OpenJDK, 1.6.0_20, di Ubuntu):

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

Metode ini (kutipan dari baris 355 hingga 371) dipanggil saat mencari entri dalam tabel, misalnya dari get(), containsKey()dan beberapa lainnya. Perulangan for di sini melewati daftar tertaut yang dibentuk oleh objek entri.

Berikut kode untuk objek entri (baris 691-705 + 759):

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

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

  // (methods left away, they are straight-forward implementations of Map.Entry)

}

Tepat setelah ini muncul addEntry()metode:

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Ini menambahkan Entri baru di depan keranjang, dengan tautan ke entri pertama yang lama (atau nol, jika tidak ada). Demikian pula, removeEntryForKey()metode ini menelusuri daftar dan menangani hanya menghapus satu entri, membiarkan sisa daftar tetap utuh.

Jadi, berikut adalah daftar entri yang ditautkan untuk setiap keranjang, dan saya sangat ragu ini berubah dari _20menjadi _22, karena ini seperti ini dari 1.2 ke atas.

(Kode ini adalah (c) 1997-2007 Sun Microsystems, dan tersedia di bawah GPL, tetapi untuk menyalin lebih baik gunakan file asli, yang terdapat di src.zip di setiap JDK dari Sun / Oracle, dan juga di OpenJDK.)

berikut adalah implementasi tabel hash yang sangat sederhana di java. hanya dalam implementasi put()dan get(), tetapi Anda dapat dengan mudah menambahkan apa pun yang Anda suka. itu bergantung pada hashCode()metode java yang diimplementasikan oleh semua objek. Anda dapat dengan mudah membuat antarmuka Anda sendiri,

interface Hashable {
  int getHash();
}

dan memaksanya untuk diterapkan oleh tombol jika Anda mau.

public class Hashtable<K, V> {
    private static class Entry<K,V> {
        private final K key;
        private final V val;

        Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int BUCKET_COUNT = 13;

    @SuppressWarnings("unchecked")
    private List<Entry>[] buckets = new List[BUCKET_COUNT];

    public Hashtable() {
        for (int i = 0, l = buckets.length; i < l; i++) {
            buckets[i] = new ArrayList<Entry<K,V>>();
        }
    }

    public V get(K key) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        for (Entry e: entries) {
            if (e.key.equals(key)) {
                return e.val;
            }
        }
        return null;
    }

    public void put(K key, V val) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        entries.add(new Entry<K,V>(key, val));
    }
}

Ada berbagai metode untuk resolusi tabrakan, beberapa di antaranya adalah Rantai Terpisah, Pengalamatan terbuka, hashing Robin Hood, Cuckoo Hashing, dll.

Java menggunakan Rangkaian Terpisah untuk menyelesaikan tabrakan dalam tabel Hash. Berikut ini tautan bagus tentang bagaimana hal itu terjadi: http://javapapers.com/core-java/java-hashtable/