Contoh analisis jadual hash dalam Java

1. Konsep

Dalam struktur berjujukan dan pokok seimbang, tiada hubungan yang sepadan antara kod kunci elemen dan lokasi penyimpanannya, jadi apabila mencari untuk elemen , mesti melalui pelbagai perbandingan kod utama. Kerumitan masa carian berjujukan ialah O(N) Dalam pokok seimbang, ia adalah ketinggian pokok, iaitu, O( ).

Kaedah carian yang ideal: anda boleh mendapatkan elemen untuk dicari terus dari jadual sekaligus tanpa sebarang perbandingan. Jika anda membina struktur storan dan menggunakan fungsi tertentu (hashFunc) untuk mewujudkan hubungan pemetaan satu dengan satu antara lokasi storan elemen dan kod utamanya, maka anda boleh mencari elemen dengan cepat melalui fungsi ini semasa carian.

Apabila memasukkan elemen ke dalam struktur:

Mengikut kod kunci elemen yang akan dimasukkan, fungsi ini mengira lokasi penyimpanan elemen dan menyimpannya di lokasi ini

Elemen carian

Lakukan pengiraan yang sama pada kod kunci elemen, gunakan nilai fungsi yang diperoleh sebagai lokasi penyimpanan elemen dan bandingkan elemen mengikut ini. lokasi dalam struktur. Jika kod kunci sama , carian berjaya

Contohnya: set data {1, 7, 6, 4, 5, 9}

Fungsi cincang ditetapkan kepada: hash(key) = kapasiti % kunci Ia ialah jumlah saiz ruang asas untuk menyimpan elemen.

2. Pengelakan konflik

Pertama sekali, kita perlu menjelaskan bahawa kerana kapasiti tatasusunan asas jadual cincang kita selalunya lebih kecil daripada kunci sebenar untuk disimpan Bilangan perkataan menyebabkan masalah Berlakunya konflik tidak dapat dielakkan, tetapi apa yang boleh kita lakukan ialah mengurangkan kadar konflik sebanyak mungkin.

3. Reka bentuk fungsi cincang-pengelak konflik

Fungsi cincang biasa

Kaedah penyesuaian langsung--(biasa digunakan)

Mengambil kata kunci Fungsi linear ialah alamat cincang: Hash (Key) = A*Key + B Kelebihan: Mudah dan seragam Kelemahan: Perlu mengetahui pengedaran kata kunci lebih awal Senario penggunaan: Sesuai untuk mencari situasi yang agak kecil dan berterusan

Pembahagian dengan kaedah baki--(biasa digunakan)

Andaikan bilangan alamat yang dibenarkan dalam jadual cincang ialah m, ambil nombor perdana p yang tidak lebih besar daripada m, tetapi paling hampir atau sama dengan m sebagai pembahagi , mengikut fungsi cincang: Hash(key) = key% p(p

kaedah langkah tengah segi empat sama--(faham)

Anggapkan kuncinya ialah 1234, Kuadratkan ialah 1522756, mengekstrak 3 digit tengah 227 sebagai alamat cincang contoh lain ialah kata kunci 4321, menduakannya ialah 18671041, mengekstrak 3 digit tengah 671 (atau 710) sebagai alamat hash; , kaedah segi empat sama lebih sesuai : Taburan kata kunci tidak diketahui, dan bilangan digit tidak terlalu besar

4 Pelarasan faktor beban-penghindaran konflik

<. . dengan mengurangkan faktor beban. adalah diketahui bahawa bilangan kata kunci dalam jadual cincang tidak berubah maka semua yang boleh kita laraskan ialah saiz tatasusunan cincang.>

5, pencincangan tertutup penyelesaian konflik

Pencincangan tertutup: juga dipanggil kaedah pengalamatan terbuka Apabila konflik cincang berlaku, jika jadual cincang tidak penuh, ini bermakna jadual cincang adalah tidak penuh. Mesti ada kedudukan kosong dalam jadual Yunani, jadi kunci boleh disimpan dalam kedudukan kosong "seterusnya" dalam kedudukan bercanggah.

① Pengesanan linear

Sebagai contoh, dalam senario di atas, anda kini perlu memasukkan elemen 44. Mula-mula, hitung alamat cincang melalui fungsi cincangan adalah 4, jadi 44 sepatutnya secara teorinya akan disisipkan pada kedudukan ini , tetapi elemen dengan nilai 4 telah diletakkan pada kedudukan ini, iaitu konflik cincang berlaku. Pengesanan linear: Bermula dari kedudukan di mana konflik berlaku, kesan ke belakang sehingga kedudukan kosong seterusnya ditemui.

Sisipkan

Dapatkan kedudukan elemen yang hendak disisipkan dalam jadual cincang melalui fungsi cincang Jika tiada elemen dalam kedudukan, masukkan elemen baharu secara langsung elemen dalam kedudukan, konflik cincang berlaku , gunakan pengesanan linear untuk mencari kedudukan kosong seterusnya, masukkan elemen baharu

Apabila menggunakan pencincangan tertutup untuk mengendalikan konflik cincang, anda tidak boleh. padam secara fizikal unsur-unsur yang sedia ada dalam jadual cincang , jika anda memadamkan unsur secara langsung, ia akan menjejaskan carian unsur-unsur lain. Sebagai contoh, jika anda memadamkan elemen 4 secara langsung, carian untuk 44 mungkin terjejas. Oleh itu, probing linear menggunakan pemadaman pseudo bertanda untuk memadam elemen.

②Pengesanan Sekunder

Kecacatan pengesanan linear ialah data yang bercanggah ditimbun bersama, yang berkaitan dengan mencari kedudukan kosong seterusnya, kerana cara untuk mencari kedudukan kosong adalah dengan mencarinya satu demi satu , jadi untuk mengelakkan masalah ini dalam pengesanan sekunder, kaedah untuk mencari kedudukan kosong seterusnya ialah: = ( + )% m, atau: = ( - )% m. Antaranya: i = 1,2,3..., ialah kedudukan yang dikira oleh fungsi cincang Hash(x) pada kod kunci elemen, dan m ialah saiz jadual. Untuk 2.1, jika anda ingin memasukkan 44, konflik berlaku Situasi yang diselesaikan ialah:

Penyelidikan menunjukkan bahawa apabila panjang jadual ialah nombor perdana dan jadual. loading factor a tidak melebihi 0.5 , entri baru pasti akan dimasukkan, dan tiada kedudukan akan disiasat dua kali. Oleh itu, selagi terdapat separuh kedudukan kosong dalam jadual, tidak akan ada masalah penuh jadual. Semasa mencari, anda tidak perlu menganggap jadual penuh, tetapi apabila memasukkan, anda mesti memastikan faktor beban a jadual tidak melebihi 0.5 Jika melebihi, anda mesti mempertimbangkan untuk meningkatkan kapasiti.

6. Conflict-Resolution-Open Hash/Hash Bucket

Kaedah cincang terbuka juga dipanggil kaedah alamat rantai (kaedah rantaian terbuka Pertama, set kod kunci dikira menggunakan a fungsi hash. Kod kunci dengan alamat yang sama tergolong dalam sub-set yang sama dipanggil baldi disimpan dalam jadual hash.

 
     static class Node {
         public int key;
         public int val;
         public Node next;
 
         public Node(int key, int val) {
             this.key = key;
             this.val = val;
         }
     }
 
     private Node[] array;
     public int usedSize;
 
     public HashBucket() {
         this.array = new Node[10];
         this.usedSize = 0;
     }

 public void put(int key,int val){
        int index = key % this.array.length;
        Node cur = array[index];
        while (cur != null){
            if(cur.val == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //头插法
         Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        if(loadFactor() >= 0.75){
            resize();
        }
    }

rrree

rreee

7, kod lengkap

public int get(int key) {
         //以什么方式存储的  那就以什么方式取
         int index = key % this.array.length;
         Node cur = array[index];
         while (cur != null) {
             if(cur.key == key) {
                 return cur.val;
             }
             cur = cur.next;
         }
         return -1;//
     }

Atas ialah kandungan terperinci Contoh analisis jadual hash dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!