Peta Hash menggunakan Javascript

pengenalan

• Peta Hash, juga dikenali sebagai Jadual Hash, ialah struktur data yang melaksanakan jenis data abstrak tatasusunan bersekutu, struktur yang boleh memetakan kunci kepada nilai.

• Ia menggunakan fungsi cincang untuk mengira indeks ke dalam tatasusunan baldi atau slot, yang daripadanya nilai yang diingini boleh didapati.

• Kelebihan utama Peta Hash ialah kecekapannya. Operasi seperti memasukkan pasangan nilai kunci baharu, memadamkan pasangan nilai kunci dan mencari nilai yang diberi kunci semuanya sangat pantas, selalunya mengambil masa yang berterusan secara purata.

Melaksanakan Peta Hash Mudah dalam JavaScript

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

Mengendalikan Perlanggaran

• Mengendalikan perlanggaran ialah aspek penting dalam melaksanakan Peta Hash. Perlanggaran berlaku apabila dua kekunci berbeza menghasilkan cincang yang sama. Terdapat beberapa strategi untuk mengendalikan perlanggaran, tetapi dua yang paling biasa ialah rantaian berasingan dan probing linear.

Perantaian Berasingan: Dalam rantaian berasingan, setiap slot dalam tatasusunan jadual cincang mengandungi senarai terpaut (atau struktur data lain yang boleh memuatkan berbilang item). Apabila perlanggaran berlaku, pasangan nilai kunci baharu ditambahkan pada penghujung senarai terpaut pada indeks yang sepadan.

Berikut ialah pelaksanaan ringkas Peta Hash menggunakan rantaian berasingan dalam JavaScript:

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}

Probing Linear: Dalam probing linear, apabila perlanggaran berlaku, peta cincang menyemak slot seterusnya dalam tatasusunan (dan meneruskan ke yang seterusnya jika itu juga penuh, dan seterusnya) sehingga ia menemui slot kosong di mana ia boleh menyimpan pasangan nilai kunci baharu.

Berikut ialah pelaksanaan ringkas Peta Hash menggunakan probing linear dalam JavaScript:

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index + 1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.table.length;
    }
    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}

Dalam kedua-dua contoh, kaedah cincang ialah fungsi cincang mudah yang menukar kunci kepada integer yang digunakan sebagai indeks dalam tatasusunan. Dalam senario dunia sebenar, anda mungkin akan menggunakan fungsi cincang yang lebih kompleks untuk mengurangkan kemungkinan perlanggaran.

Atas ialah kandungan terperinci Peta Hash menggunakan Javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!