apa itu hash javascript

Dalam JavaScript, cincang merujuk kepada jadual cincang, iaitu struktur data yang mengakses lokasi storan memori secara langsung berdasarkan kata kunci melalui jadual cincang, lokasi storan elemen data dan kata kunci data elemen adalah Satu surat-menyurat tertentu ditubuhkan di antara mereka, dan fungsi yang mewujudkan surat-menyurat ini dipanggil fungsi cincang.

Persekitaran pengendalian tutorial ini: sistem Windows 7, versi JavaScript 1.8.5, komputer Dell G3.

Konsep asas cincang javascript:

Jadual cincang (jadual cincang) ialah sejenis data yang mengakses lokasi storan memori secara terus berdasarkan kata kunci Struktur, melalui jadual cincang, surat-menyurat tertentu diwujudkan antara lokasi penyimpanan elemen data dan kunci elemen data Fungsi yang menetapkan surat-menyurat ini dipanggil fungsi cincang.

Kaedah pembinaan jadual hash:

Andaikan bilangan elemen data yang akan disimpan ialah n, tetapkan unit storan berterusan dengan panjang m (m > n), masing-masing Mengambil kata kunci Ki (0

Dari sudut pandangan matematik, fungsi cincang sebenarnya ialah pemetaan kata kunci kepada unit ingatan, jadi kami berharap dapat menggunakan fungsi cincang untuk menjadikan alamat Huaxi dikira oleh fungsi cincang sebagai seragam yang mungkin melalui Operasi yang paling mudah mungkin. Pemetaan belakang kepada satu siri unit memori, terdapat tiga perkara utama dalam membina fungsi cincang: (1) Proses operasi haruslah semudah dan seefisien mungkin untuk meningkatkan kecekapan pemasukan dan pengambilan jadual cincang; 2) Fungsi cincang sepatutnya mempunyai jenis Hash yang lebih baik untuk mengurangkan kebarangkalian perlanggaran cincang ketiga, fungsi cincang harus mempunyai pemampatan yang lebih besar untuk menjimatkan memori.

Kaedah biasa:

• Kaedah alamat langsung: gunakan nilai fungsi linear tertentu kata kunci sebagai alamat cincang, yang boleh dinyatakan sebagai cincang(K)=aK C; kelebihannya ialah ia tidak Konflik akan berlaku, dan kelemahannya ialah kerumitan ruang mungkin lebih tinggi, yang sesuai untuk kes dengan unsur yang lebih sedikit.
• Bagi dengan kaedah baki: Ia membahagikan kata kunci elemen data dengan pemalar tertentu dan selebihnya ialah alamat cincangan Kaedah ini mudah dikira dan mempunyai pelbagai aplikasi Ia adalah fungsi cincang yang kerap digunakan . , boleh dinyatakan sebagai:
  hash(K=K mod C; Kunci kepada kaedah ini ialah pemilihan pemalar. Keperluan umum ialah ia hampir atau sama dengan panjang jadual hash itu sendiri. Penyelidikan teori menunjukkan bahawa pemalar berfungsi paling baik apabila memilih nombor perdana
• Kaedah analisis nombor: Kaedah ini adalah untuk mengambil beberapa nombor seragam dalam kata kunci elemen data sebagai alamat cincangan Ini boleh mengelakkan konflik sebanyak mungkin kaedah ini hanya sesuai untuk semua kata kunci Situasi yang diketahui tidak terpakai kepada mereka yang ingin mereka bentuk jadual cincang yang lebih umum
• Kaedah penjumlahan segi empat sama: tukar rentetan semasa kepada nilai Unikod, cari kuasa dua bagi. nilai ini, dan kuasaikannya nombor yang akan disisipkan mengikut bilangan digit dalam jadual cincang semasa Bahagikan nilai kepada beberapa segmen, tambahkan bahagian, dan buang bit tertinggi :
• dalam pembinaan Apabila menggunakan jadual cincang, terdapat masalah: untuk dua kata kunci yang berbeza, alamat cincang yang sama diperoleh semasa mengira alamat cincang melalui fungsi cincang kami .

Konflik hash terutamanya berkaitan dengan dua faktor

(1) Faktor pengisian, yang merujuk kepada apa yang telah disimpan dalam jadual cincang Nisbah bilangan elemen data yang dimasukkan kepada saiz ruang alamat cincang, a=n/m lebih kecil, lebih kecil kemungkinan konflik, sebaliknya, kemungkinan konflik lebih besar; , lebih baik penggunaan ruang Lebih kecil, lebih besar a, lebih tinggi penggunaan ruang Untuk mengambil kira konflik cincang dan penggunaan ruang storan, a biasanya dikawal antara 0.6-0.9, manakala HashTable dalam .net secara langsung mentakrifkan maksimum. nilai a. ialah 0.72 (Walaupun MSDN rasmi Microsoft menyatakan bahawa faktor pengisian lalai HashTable ialah 1.0, ia sebenarnya adalah gandaan 0.72)
(2) Ia berkaitan dengan fungsi cincang yang digunakan sesuai, fungsi cincang boleh dibuat. ) Pengalamatan terbuka.

Hi=(H(key) di) MOD m i=1,2,…k(k dengan H(key) ialah fungsi cincang; m ialah hash Panjang jadual di ialah jujukan tambahan. Terdapat 3 jujukan tambahan:

①Pengesanan linear dan kemudian pencincangan: di=1,2,3,…,m-1
②Pengesanan kedua dan kemudian pencincangan: di=1

2,- 1

2,2

2,-2

2,…±k^2(k ③Pengesanan pseudo-rawak dan kemudian pencincangan: di=jujukan nombor rawak pseudo

Kelemahan:

Kita boleh melihat fenomena: apabila rekod telah diisi pada kedudukan i, i 1, dan i 2 dalam jadual, rekod seterusnya dengan alamat cincang i, i 1, i 2 dan i 3 akan diisi dalam. Kedudukan i 3. Fenomena dua rekod dengan alamat cincang pertama yang berbeza bersaing untuk alamat cincang berikutnya yang sama semasa proses pengendalian konflik dipanggil "pengagregatan sekunder", iaitu, dalam proses pengendalian konflik sinonim Ditambah konflik yang tidak sinonim. Tetapi sebaliknya, menggunakan pengesanan linear dan kemudian pencincangan untuk mengendalikan konflik boleh menjamin bahawa selagi jadual cincang tidak penuh, alamat Hk yang tidak bercanggah sentiasa boleh ditemui. Pengesanan sekunder dan pencincangan semula hanya boleh dilakukan apabila panjang jadual cincang m ialah nombor perdana bagi bentuk 4j 3 (j ialah integer). Iaitu, kaedah pengalamatan terbuka akan menyebabkan pengagregatan sekunder, yang memudaratkan carian.

2) Kaedah rehash

Hi = RHi (key), i=1,2,...k RHi adalah semua fungsi hash yang berbeza, iaitu, dalam Apabila sinonim menghasilkan konflik alamat, alamat fungsi cincang yang lain dikira sehingga tiada konflik berlaku. Kaedah ini kurang terdedah kepada pengagregatan, tetapi meningkatkan masa pengiraan.

Kelemahan: Peningkatan masa pengiraan.

3) Kaedah alamat rantai (kaedah zip)

Simpan semua rekod yang kata kuncinya sinonim dalam senarai pautan linear yang sama.

Kelebihan:

①Kaedah zip adalah mudah untuk mengendalikan konflik dan tidak mempunyai fenomena pengumpulan, iaitu, bukan sinonim tidak akan pernah bercanggah, jadi purata panjang carian adalah lebih pendek;
②Kerana kaedah zip Ruang nod pada setiap senarai terpaut digunakan secara dinamik, jadi ia lebih sesuai untuk situasi di mana panjang jadual tidak dapat ditentukan sebelum membuat jadual
③ Untuk mengurangkan konflik, kaedah pengalamatan terbuka memerlukan pengisian; faktor α menjadi kecil, jadi apabila saiz nod Apabila lebih besar, banyak ruang terbuang. Dalam kaedah zip, α ≥ 1 boleh diterima, dan apabila nod besar, domain penuding yang ditambahkan dalam kaedah zip boleh diabaikan, dengan itu menjimatkan ruang
④ Dalam jadual cincang yang dibina dengan kaedah zip, operasi memadam nod Mudah dilaksanakan. Hanya padamkan nod yang sepadan pada senarai terpaut. Untuk jadual cincang yang dibina oleh kaedah alamat terbuka, memadamkan nod tidak boleh membiarkan ruang nod yang dipadam kosong, jika tidak, laluan carian nod sinonim yang diisi dalam jadual cincang selepas ia akan dipotong. Ini kerana dalam pelbagai kaedah alamat terbuka, unit alamat kosong (iaitu alamat terbuka) adalah syarat untuk kegagalan carian. Oleh itu, apabila melakukan operasi pemadaman pada jadual cincang yang menggunakan kaedah alamat terbuka untuk mengendalikan konflik, ia hanya boleh menandakan nod yang dipadamkan untuk pemadaman, tetapi sebenarnya tidak boleh memadamkan nod tersebut.

Kelemahan:

Kelemahan kaedah zip ialah penunjuk memerlukan ruang tambahan, jadi apabila saiz nod kecil, kaedah pengalamatan terbuka lebih menjimatkan ruang, dan jika penunjuk yang disimpan ruang digunakan Meningkatkan saiz jadual cincang boleh menjadikan faktor isian lebih kecil, yang seterusnya mengurangkan konflik dalam kaedah pengalamatan terbuka dan dengan itu meningkatkan purata kelajuan carian.

4) Wujudkan kawasan limpahan awam

Dengan mengandaikan bahawa julat nilai fungsi cincang ialah [0,m-1], maka biarkan vektor HashTable[0…m-1] ialah jadual asas, setiap komponen menyimpan rekod, dan vektor OverTable[0…v] disediakan sebagai jadual limpahan. Semua rekod yang kata kuncinya sinonim dengan kata kunci dalam jadual asas, tanpa mengira alamat cincang yang diperolehi oleh fungsi cincang, akan diisi dalam jadual limpahan sekiranya berlaku konflik.

Pelaksanaan jadual cincang bagi fungsi cincang mudah tanpa pengendalian konflik

class Hash {
  constructor() {
    this.table = new Array(1024);
  }
  hash(data) {
    //就将字符串中的每个字符的ASCLL码值相加起来，再对数组的长度取余
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    console.log("Hash Value: " + data + " -> " + total);
    return total % this.table.length;
  }
  insert(key, val) {
    var pos = this.hash(key);
    this.table[pos] = val;
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

Kaedah tengah segi empat sama digunakan untuk membina fungsi cincang dan kaedah alamat terbuka Kaedah probing linear untuk penyelesaian konflik.

class Hash {
  constructor() {
    this.table = new Array(1000);
  }
  hash(data) {
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    //把字符串转化为字符用来求和之后进行平方运算
    var s = total * total + ""
    //保留中间2位
    var index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1
    console.log("Hash Value: " + data + " -> " + index);
    return index;
  }
  solveClash(index, value) {
    var table = this.table
    //进行线性开放地址法解决冲突
    for (var i = 0; index + i < 1000; i++) {
      if (table[index + i] == null) {
        table[index + i] = value;
        break;
      }
    }
  }
  insert(key, val) {
    var index = this.hash(key);
    //把取中当做哈希表中索引
    if (this.table[index] == null) {
      this.table[index] = val;
    } else {
      this.solveClash(index, val);
    }
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

[Pembelajaran yang disyorkan: tutorial lanjutan javascript]

Atas ialah kandungan terperinci apa itu hash javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!