Pengenalan terperinci tentang cara JavaScript melaksanakan jadual cincang

Artikel ini membawa anda pengetahuan yang berkaitan tentang javascript terutamanya memperkenalkan isu berkaitan tentang cara JavaScript melaksanakan jadual cincang dan merangkum keseluruhan struktur tatasusunan yang mana data akhir dimasukkan jadual hash, saya harap ia akan membantu semua orang.

Cadangan berkaitan: Tutorial pembelajaran javascript

Jadual cincang biasanya dilaksanakan berdasarkan tatasusunan mempunyai banyak kelebihan berbanding tatasusunan:

1. Ia boleh menyediakan operasi cari pemadaman-sisipan yang sangat pantas
2. Tidak kira berapa banyak data, pemasukan dan pemadaman perlu hampir kepada pemalar masa: iaitu, O(1) peringkat masa. Malah, ia hanya memerlukan beberapa arahan mesin untuk melakukannya.
3. Jadual cincang lebih pantas daripada pokok, dan pada asasnya anda boleh mencari elemen yang anda inginkan serta-merta
4. Jadual cincang lebih mudah untuk dikodkan daripada pokok

Beberapa kelemahan jadual cincang berbanding tatasusunan:

1. Data dalam jadual cincang tidak disusun, jadi ia tidak boleh dilalui dengan cara tetap Elemen
2. Biasanya , kunci dalam jadual cincang tidak dibenarkan diulang, dan kunci yang sama tidak boleh diletakkan untuk menyimpan elemen yang berbeza
3. Penggunaan ruang tidak tinggi, dan penggunaan asasnya ialah tatasusunan. dan beberapa sel tidak digunakan

Apakah jadual cincang?

• Jadual cincang tidak mudah difahami, tidak seperti tatasusunan, senarai terpaut dan pepohon, yang boleh menyatakan struktur dan prinsipnya melalui grafik. Struktur jadual cincang
• ialah tatasusunan, tetapi keajaibannya terletak pada transformasi nilai subskrip Kita boleh memanggil transformasi ini fungsi Cincang , melalui fungsi cincang, anda boleh mendapatkan Kod Hash.

Beberapa konsep jadual cincang

• Cincang: Tukar nombor besar Proses penukaran subskrip dalam julat tatasusunan dipanggil pencincangan ;
• fungsi cincang: Kami biasanya merujuk kepada Tukar perkataan ke dalam nombor besar, dan letakkan pelaksanaan kod cincang ke dalam fungsi, yang dipanggil fungsi Cincang ; : merangkum keseluruhan struktur
tatasusunan
• yang dimasukkan ke dalam data akhir, dan kami dapat ialah jadual cincang. Masalah yang masih perlu diselesaikan:

Subskrip cincang mungkin masih pendua, bagaimana untuk menyelesaikan ini Apa masalahnya? Keadaan ini dipanggil

konflik

Konflik adalah
• tidak dapat dielakkan dan kita hanya boleh menyelesaikan. Kaedah untuk menyelesaikan konflik
Dua penyelesaian biasa untuk menyelesaikan konflik:

Pilihan 1: Kaedah alamat rantai (

Kaedah zip

);
• Seperti yang ditunjukkan dalam rajah di bawah, kami akan melakukan operasi baki pada 10 untuk setiap nombor, kemudian baki Julat
0~9

digunakan sebagai nilai subskrip tatasusunan. Selain itu, kedudukan yang sepadan dengan setiap nilai subskrip dalam tatasusunan tidak lagi menyimpan nombor, tetapi menyimpan

tatasusunan atau senarai terpaut . Ringkasan: Kaedah alamat rantai

menyelesaikan konflik dengan

menyimpan dalam setiap unit tatasusunan tidak lagi

Satu data

, tetapi rantaian . secara amnya Tidak terlalu banyak). Pilihan 2: Kaedah alamat terbuka; Kaedah kerja utama kaedah alamat terbuka ialah

mencari sel kosong

untuk meletakkan
• bercanggah item data.

Menurut cara yang berbeza untuk mengesan kedudukan sel kosong, ia boleh dibahagikan kepada tiga kaedah:

Pengesanan linear

Pengesanan sekunder

• Kaedah rehashing
• Ia boleh dilihat apabila faktor pengisian meningkat , purata Panjang pengesanan meningkat secara linear dan perlahan-lahan. Kaedah alamat rantaian sering digunakan dalam pembangunan Contohnya, HashMap dalam Java menggunakan kaedah alamat rantai
.
• Fungsi cincang yang sangat baik
Kelebihan jadual cincang ialah kelajuannya, jadi fungsi cincang tidak boleh menggunakan algoritma kompleks yang menggunakan prestasi tinggi. Satu cara untuk meningkatkan kelajuan ialah meminimumkan pendaraban dan pembahagian

dalam fungsi cincang.

Fungsi cincang berprestasi tinggi harus mempunyai dua kelebihan berikut:

• Pengiraan pantas;
• Pengagihan seragam;

Pengiraan pantas

Peraturan Horner: Di China, peraturan Horner juga dipanggil Algoritma Qin Jiu'ao Algoritma khusus ialah:

Apabila mencari nilai. bagi polinomial, Pertama, hitung nilai polinomial linear dalam kurungan paling dalam, dan kemudian hitung nilai polinomial linear lapisan demi lapisan dari dalam ke luar. Algoritma ini menukarkan nilai n darjah polinomial f(x) kepada nilai n darjah polinomial.

Sebelum transformasi:

• Bilangan pendaraban: n (n 1)/2 kali;

Selepas transformasi:

Bilangan darab: n kali;

• Jika O besar digunakan untuk mewakili kerumitan masa, ia dikurangkan secara langsung daripada
O(N2)
• sebelum transformasi kepada
O(N)

.

Teredar secara seragamUntuk memastikan data teredar sama rata

dalam jadual cincang, apabila kita perlu

menggunakan pemalar

, cuba gunakan

Nombor perdana ; contohnya: panjang jadual cincang, asas kuasa N, dsb. HashMap dalam Java menggunakan kaedah alamat rantai, dan kaedah pencincangan menggunakan formula: index = HashCode (kunci) & (Length-1)

Iaitu, tukar data kepada binari dan lakukan operasi

dan dan bukannya mengambil operasi yang selebihnya. Dengan cara ini, komputer secara langsung beroperasi pada data binari, yang lebih cekap. Walau bagaimanapun, JavaScript akan menghadapi masalah apabila melaksanakan operasi dan

yang dipanggil data besar, jadi operasi selebihnya masih akan digunakan apabila menggunakan JavaScript untuk melaksanakan pencincangan.

Cadangan berkaitan:

                    function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍纳算法）
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i  this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 获取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i  7 && this.count  0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i Tutorial pembelajaran javascript<p><pengenalan terperinci tentang cara javascript melaksanakan jadual cincang src="https://Pengenalan%20terperinci%20tentang%20cara%20JavaScript%20melaksanakan%20jadual%20cincang.php.cn/upload/article/000/000/067/4ca10f86d3fe737c57c2ff0ae29c077f-3.png" alt="Pengenalan terperinci tentang cara JavaScript melaksanakan jadual cincang"></pengenalan></p>

Atas ialah kandungan terperinci Pengenalan terperinci tentang cara JavaScript melaksanakan jadual cincang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!