Bảng băm JavaScript – Băm mảng liên kết trong JS

Bảng băm là một cấu trúc dữ liệu cho phép bạn tạo danh sách các giá trị được ghép nối. Sau đó, bạn có thể truy xuất một giá trị nhất định bằng cách sử dụng khóa cho giá trị đó mà bạn đã nhập vào bảng trước đó.

Bảng Hash chuyển đổi khóa thành chỉ mục số nguyên bằng cách sử dụng hàm băm và chỉ mục sẽ quyết định nơi lưu trữ cặp khóa/giá trị trong bộ nhớ:

Bạn sẽ thường sử dụng Bảng băm vì các hoạt động tìm kiếm, chèn và xóa nhanh chóng của nó:

Nguồn từ Wikipedia

Hướng dẫn này sẽ giúp bạn hiểu cách triển khai Bảng băm trong JavaScript cũng như cách bạn có thể xây dựng lớp Bảng băm của riêng mình.

Trước tiên, hãy xem JavaScript Object và Map các lớp học.

Cách sử dụng Bảng băm với các lớp đối tượng và bản đồ trong JavaScript

Ví dụ phổ biến nhất về Bảng băm trong JavaScript là Object kiểu dữ liệu, nơi bạn có thể ghép nối giá trị thuộc tính của đối tượng với khóa thuộc tính.

Trong ví dụ sau, khóa Nathan được ghép nối với giá trị số điện thoại của "555-0182" và chìa khóa Jane được ghép nối với giá trị "315-0322":

let obj = {
  Nathan: "555-0182",
  Jane: "315-0322"
}

Nhưng JavaScript Object type là một kiểu triển khai Bảng băm đặc biệt vì hai lý do:

• Nó có các thuộc tính được thêm vào bởi Object lớp. Các khóa bạn nhập có thể xung đột và ghi đè lên các thuộc tính mặc định được kế thừa từ lớp.
• Kích thước của Bảng băm không được theo dõi. Bạn cần đếm thủ công có bao nhiêu thuộc tính được xác định bởi lập trình viên thay vì kế thừa từ nguyên mẫu.

Ví dụ, các Object nguyên mẫu có hasOwnProperty() phương thức cho phép bạn kiểm tra xem một thuộc tính không được kế thừa hay không:

const obj = {};
obj.name = "Nathan";

console.log(obj.hasOwnProperty("name")); // true

JavaScript không chặn nỗ lực ghi đè lên hasOwnProperty() phương pháp, có thể gây ra lỗi như thế này:

const obj = {};
obj.name = "Nathan";
obj.hasOwnProperty = true;

console.log(obj.hasOwnProperty("name")); 
// Error: obj.hasOwnProperty is not a function

Để xử lý những thiếu sót này, JavaScript đã tạo một triển khai khác của cấu trúc dữ liệu Bảng băm được gọi là Map

Giống như Object, Map cho phép bạn lưu trữ các cặp khóa-giá trị bên trong cấu trúc dữ liệu. Đây là một ví dụ về Map trong hành động:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection.set("Jane", "555-0182");

console.log(collection.get("Nathan")); // 555-0182
console.log(collection.size); // 2

không giống như Object loại, Map yêu cầu bạn sử dụng set() và get() các phương thức để xác định và truy xuất bất kỳ giá trị cặp khóa nào mà bạn muốn thêm vào cấu trúc dữ liệu.

Bạn cũng không thể ghi đè lên Map tài sản kế thừa. Ví dụ: đoạn mã sau đã cố gắng ghi đè lên size giá trị tài sản để false:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection["size"] = false;

console.log(collection.get("size")); // undefined
console.log(collection.size); // 1

Như bạn có thể thấy từ đoạn mã trên, bạn không thể thêm một mục mới vào Map đối tượng mà không sử dụng set() phương pháp.

Các Map cấu trúc dữ liệu cũng có thể lặp lại, có nghĩa là bạn có thể lặp lại dữ liệu như sau:

const myMap = new Map();

myMap.set("Nathan", "555-0182");
myMap.set("Jane", "315-0322");

for (let [key, value] of myMap) {
  console.log(`${key} = ${value}`);
}

Bây giờ bạn đã học cách JavaScript triển khai Bảng băm dưới dạng Object và Map cấu trúc dữ liệu, hãy xem cách bạn có thể tạo triển khai Bảng băm của riêng mình trong phần tiếp theo.

Cách triển khai cấu trúc dữ liệu bảng băm trong JavaScript

Mặc dù JavaScript đã có hai cách triển khai Bảng băm, nhưng viết cách triển khai Bảng băm của riêng bạn là một trong những câu hỏi phỏng vấn JavaScript phổ biến nhất.

Bạn có thể triển khai Bảng băm trong JavaScript theo ba bước:

• Tạo một HashTable lớp với table và size thuộc tính ban đầu
• thêm một hash() chức năng chuyển đổi khóa thành chỉ mục
• thêm set() và get() các phương pháp thêm và truy xuất các cặp khóa/giá trị từ bảng.

Được rồi, hãy bắt đầu với việc tạo HashTable lớp. Đoạn mã dưới đây sẽ tạo một table của xô với kích thước của 127:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }
}

Tất cả các cặp khóa/giá trị của bạn sẽ được lưu trữ bên trong table tài sản.

Cách viết phương thức hash()

Tiếp theo, bạn cần tạo hash() phương pháp sẽ chấp nhận một key giá trị và biến nó thành một chỉ mục.

Một cách đơn giản để tạo hàm băm là tính tổng mã ASCII của các ký tự trong khóa bằng cách sử dụng charCodeAt() phương pháp như sau. Lưu ý rằng phương thức được đặt tên bằng cách sử dụng _ để chỉ ra rằng đó là một lớp riêng tư:

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

Nhưng kể từ khi HashTable lớp chỉ có 127 nhóm, điều này có nghĩa là _hash() phương pháp phải trả về một số giữa 0 and 127.

Để đảm bảo rằng giá trị băm không vượt quá kích thước nhóm, bạn cần sử dụng toán tử modulo như hình bên dưới:

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

Bây giờ bạn đã có _hash() phương pháp đã hoàn thành, đã đến lúc viết set() và get() các phương pháp.

Cách viết phương thức set()

Để đặt cặp khóa/giá trị trong Bảng băm của bạn, bạn cần viết một set() phương pháp chấp nhận (key, value) như các tham số của nó:

• Các set() phương thức sẽ gọi _hash() phương pháp để có được index giá trị.
• Các [key, value] cặp sẽ được gán cho table tại quy định index
• Sau đó, size tài sản sẽ được tăng thêm một

set(key, value) {
  const index = this._hash(key);
  this.table[index] = [key, value];
  this.size++;
}

Bây giờ mà set() phương pháp đã hoàn tất, hãy viết get() phương pháp để lấy một giá trị bằng khóa của nó.

Cách viết phương thức get()

Để lấy một giá trị nhất định từ Bảng băm, bạn cần viết một get() phương pháp chấp nhận một key giá trị như tham số của nó:

• Phương thức sẽ gọi _hash() phương pháp để lấy lại bảng một lần nữa index
• Trả về giá trị được lưu trữ tại table[index]

get(key) {
  const index = this._hash(key);
  return this.table[index];
}

Bằng cách này, các get() phương thức sẽ trả lại cặp khóa/giá trị hoặc undefined khi không có cặp khóa/giá trị nào được lưu trữ trong tệp đã chỉ định index.

Càng xa càng tốt. Tiếp theo, hãy thêm một phương thức khác để xóa cặp khóa/giá trị khỏi Bảng băm.

Cách viết phương thức remove()

Để xóa một cặp khóa/giá trị khỏi Bảng băm, bạn cần viết một remove() phương pháp chấp nhận một key giá trị như tham số của nó:

• Truy xuất quyền index sử dụng _hash() phương pháp
• Kiểm tra xem table[index] có giá trị trung thực và length tài sản lớn hơn không. chỉ định undefined giá trị bên phải index và giảm size tài sản của một nếu nó là.
• Nếu không, chỉ cần quay lại false

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    this.table[index] = undefined;
    this.size--;
    return true;
  } else {
    return false;
  }
}

Với điều đó, bây giờ bạn có một công việc remove() phương pháp. Hãy xem nếu HashTable lớp hoạt động bình thường.

Cách kiểm tra việc triển khai Bảng băm

Đã đến lúc kiểm tra việc triển khai Bảng băm. Đây là mã đầy đủ để triển khai lại Bảng băm:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

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

  set(key, value) {
    const index = this._hash(key);
    this.table[index] = [key, value];
    this.size++;
  }

  get(key) {
    const target = this._hash(key);
    return this.table[target];
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      this.table[index] = [];
      this.size--;
      return true;
    } else {
      return false;
    }
  }
}

Để kiểm tra HashTable lớp, tôi sẽ tạo một phiên bản mới của class và đặt một số cặp khóa/giá trị như hình bên dưới. Các cặp khóa/giá trị bên dưới chỉ là các giá trị số tùy ý được ghép nối với tên quốc gia mà không có bất kỳ ý nghĩa đặc biệt nào:

const ht = new HashTable();
ht.set("Canada", 300);
ht.set("France", 100);
ht.set("Spain", 110);

Sau đó, hãy thử truy xuất chúng bằng cách sử dụng get() phương pháp:

console.log(ht.get("Canada")); // [ 'Canada', 300 ]
console.log(ht.get("France")); // [ 'France', 100 ]
console.log(ht.get("Spain")); // [ 'Spain', 110 ]

Cuối cùng, hãy thử xóa một trong những giá trị này bằng lệnh remove() phương pháp:

console.log(ht.remove("Spain")); // true
console.log(ht.get("Spain")); // undefined

Được rồi, tất cả các phương pháp đều hoạt động như mong đợi. Hãy thử một lần chèn khác với một cái mới HashTable dụ và truy xuất các giá trị đó:

const ht = new HashTable();

ht.set("Spain", 110);
ht.set("ǻ", 192);

console.log(ht.get("Spain")); // [ 'ǻ', 192 ]
console.log(ht.get("ǻ")); // [ 'ǻ', 192 ]

Ối! Có vẻ như chúng tôi đã gặp một số rắc rối ở đây. 😨

Cách xử lý xung đột chỉ mục

Đôi khi, hàm băm trong Bảng băm có thể trả về cùng một index con số. Trong trường hợp thử nghiệm trên, chuỗi "Spain" và "ǻ" cả hai trở lại giống nhau hash giá trị bởi vì số 507 là tổng của cả hai mã ASCII của họ.

Giống nhau hash value sẽ khiến chỉ mục va chạmghi đè mục trước đó bằng mục mới.

Ngay bây giờ, dữ liệu được lưu trữ trong triển khai Bảng băm của chúng tôi trông như sau:

[
    [ "Spain", 110],
    [ "France", 100]
]

để xử lý index xung đột số, bạn cần lưu trữ cặp khóa/giá trị trong một mảng thứ hai để kết quả cuối cùng trông như sau:

[
    [
        [ "Spain", 110 ],
        [ "ǻ", 192 ]
    ],
    [
        ["France", 100]
    ],
]

Để tạo mảng thứ hai, bạn cần cập nhật set() phương pháp để nó sẽ:

• Nhìn vào table[index] và lặp qua các giá trị mảng.
• Nếu khóa tại một trong các mảng bằng với key được truyền cho phương thức, thay thế giá trị tại chỉ mục 1 và dừng bất kỳ thực hiện nào nữa với return bản tường trình.
• Nếu không khớp key được tìm thấy, hãy đẩy một mảng khóa và giá trị mới sang mảng thứ hai.
• Khác, khởi tạo một mảng mới và đẩy cặp khóa/giá trị đến chỉ định index
• Bất cứ khi nào push() phương thức được gọi, tăng size tài sản bằng một.

Hoàn chỉnh set() mã phương thức sẽ như sau:

set(key, value) {
  const index = this._hash(key);
  if (this.table[index]) {
    for (let i = 0; i < this.table[index].length; i++) {
      // Find the key/value pair in the chain
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    // not found, push a new key/value pair
    this.table[index].push([key, value]);
  } else {
    this.table[index] = [];
    this.table[index].push([key, value]);
  }
  this.size++;
}

Tiếp theo, cập nhật get() để nó cũng sẽ kiểm tra mảng cấp hai bằng một for vòng lặp và trả về đúng cặp khóa/giá trị:

get(key) {
  const target = this._hash(key);
  if (this.table[target]) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[target][i][0] === key) {
        return this.table[target][i][1];
      }
    }
  }
  return undefined;
}

Cuối cùng, bạn cần cập nhật remove() để nó sẽ lặp qua mảng cấp hai và loại bỏ mảng bằng quyền key giá trị bằng cách sử dụng splice() phương pháp:

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index].splice(i, 1);
        this.size--;
        return true;
      }
    }
  } else {
    return false;
  }
}

Với điều đó, của bạn HashTable lớp sẽ có thể tránh bất kỳ xung đột số chỉ mục nào và lưu trữ cặp khóa/giá trị bên trong mảng cấp hai.

Như một phần thưởng, hãy thêm một display() phương thức sẽ hiển thị tất cả các cặp khóa/giá trị được lưu trữ trong Bảng băm. Bạn chỉ cần sử dụng forEach() phương pháp để lặp qua bảng và map() các giá trị cho một chuỗi như hình dưới đây:

display() {
  this.table.forEach((values, index) => {
    const chainedValues = values.map(
      ([key, value]) => `[ ${key}: ${value} ]`
    );
    console.log(`${index}: ${chainedValues}`);
  });
}

đây là hoàn chỉnh HashTable mã lớp một lần nữa với việc tránh va chạm được áp dụng để bạn tham khảo:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

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

  set(key, value) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index][i][1] = value;
          return;
        }
      }
      this.table[index].push([key, value]);
    } else {
      this.table[index] = [];
      this.table[index].push([key, value]);
    }
    this.size++;
  }

  get(key) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          return this.table[index][i][1];
        }
      }
    }
    return undefined;
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index].splice(i, 1);
          this.size--;
          return true;
        }
      }
    } else {
      return false;
    }
  }

  display() {
    this.table.forEach((values, index) => {
      const chainedValues = values.map(
        ([key, value]) => `[ ${key}: ${value} ]`
      );
      console.log(`${index}: ${chainedValues}`);
    });
  }
}

Bạn có thể kiểm tra việc thực hiện bằng cách tạo mới HashTable ví dụ và thực hiện một số thao tác chèn và xóa:

const ht = new HashTable();

ht.set("France", 111);
ht.set("Spain", 150);
ht.set("ǻ", 192);

ht.display();
// 83: [ France: 111 ]
// 126: [ Spain: 150 ],[ ǻ: 192 ]

console.log(ht.size); // 3
ht.remove("Spain");
ht.display();
// 83: [ France: 111 ]
// 126: [ ǻ: 192 ]

Bây giờ không có va chạm bên trong HashTable ví dụ. Công việc tuyệt vời!

Phần kết luận

Trong hướng dẫn này, bạn đã học được Bảng Băm là gì và cách JavaScript sử dụng nó để tạo Object và Map cấu trúc dữ liệu.

Bạn cũng đã học cách triển khai của riêng mình HashTable lớp cũng như cách ngăn các chỉ số chính của Bảng băm xung đột bằng cách sử dụng kỹ thuật xâu chuỗi.

Bằng cách sử dụng cấu trúc dữ liệu Bảng băm, bạn sẽ có thể tạo một mảng kết hợp với các thao tác tìm kiếm, chèn và xóa nhanh chóng. 😉

Cảm ơn đã đọc hướng dẫn này

Nếu bạn muốn tìm hiểu thêm về JavaScript, bạn có thể muốn xem trang web của tôi tại sebhastian.com, nơi tôi đã xuất bản hơn 100 hướng dẫn về lập trình với JavaScript, tất cả đều sử dụng các ví dụ mã và giải thích dễ hiểu.

Các hướng dẫn bao gồm thao tác Chuỗi, thao tác Ngày, phương thức Mảng và Đối tượng, giải pháp thuật toán JavaScript, v.v.