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ó:
Độ phức tạp thời gian của Bảng băm trong Ký hiệu Big O | ||
---|---|---|
thuật toán | Trung bình | Trường hợp xấu nhất |
Khoảng trống | Trên) | Trên) |
Tìm kiếm | Ô(1) | Trên) |
Chèn | Ô(1) | Trên) |
Xóa bỏ | Ô(1) | Trê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ớitable
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ó đượcindex
giá trị. - Các
[key, value]
cặp sẽ được gán chotable
tại quy địnhindex
- 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ữaindex
- 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ỉ địnhundefined
giá trị bên phảiindex
và giảmsize
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ục1
và dừng bất kỳ thực hiện nào nữa vớireturn
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ăngsize
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.