Bảng băm trong JavaScript là gì?

Bảng băm có thể được sử dụng để giải quyết các vấn đề mà bạn cần theo dõi các biến khác nhau mà không cần viết chúng một cách rõ ràng

Hãy sử dụng một ví dụ. Giả sử bạn có chuỗi sau, “abgcddcccfmlk”

Bây giờ hãy tưởng tượng bạn được yêu cầu đảm bảo rằng chuỗi không có bất kỳ chữ cái nào lặp lại quá 3 lần

Bạn sẽ làm điều này như thế nào?

Câu trả lời ngây thơ sẽ là sử dụng hai vòng lặp lồng nhau để so sánh từng chữ cái với phần còn lại và đảm bảo chữ cái đó không lặp lại quá 3 lần

Mặc dù giải pháp này hiệu quả nhưng phải mất n² thao tác để hoàn thành, trong đó n bằng kích thước của mảng. Chúng ta có thể thấy giải pháp này có thể trở nên kém hiệu quả như thế nào

Bây giờ, giả sử chúng ta có một bảng băm để theo dõi thời gian mỗi chữ cái lặp lại

Bảng băm của chúng tôi sẽ trông giống như thế này

[ Một. 1 ]

Khi chúng tôi lặp qua chuỗi, chúng tôi sẽ cập nhật tất cả các giá trị mà chúng tôi tìm thấy và thêm 1 vào số lượng tương ứng của chúng khi chúng tôi thực hiện. Sau một lần lặp lại chuỗi, bảng băm của chúng ta sẽ trông như thế này ngay trước khi lặp qua chữ 'c' cuối cùng trong mảng của chúng ta

[ Một. 1, b. 1,g. 1, c. 3, đ. 2]

Chúng ta có thể thấy rằng nếu chúng ta thêm 1 vào c thì nó sẽ trở thành 4, do đó làm cho chuỗi của chúng ta trở nên “không hợp lệ”. Chúng ta chỉ cần dừng ở đây và trả về false mà không cần nhìn vào phần còn lại của mảng vì chúng ta biết chuỗi của mình đã không hợp lệ do “c” lặp lại hơn 3 lần. Điều này sẽ mất tối đa n thao tác, tốt hơn nhiều so với giải pháp trước đây của chúng tôi

Hy vọng rằng bây giờ bạn có thể hiểu tại sao một bảng băm có thể hữu ích cho loại vấn đề này và tất cả các trường hợp sử dụng có thể có của nó.

Bây giờ chúng ta đã hiểu rõ hơn về cách hoạt động của bảng băm trong thực tế, hãy bắt đầu triển khai nó trong JavaScript/TypeScript

Ghi chú. Sự khác biệt duy nhất giữa TypeScript và JavaScript là khai báo các loại biến. Trong các đoạn mã bên dưới, mã được viết bằng TypeScript, nhưng có thể dễ dàng biến nó thành javascript bằng cách xóa định nghĩa loại

Ví dụ

//in typescript
var addOne(num: number): number {
     return num++;
}//in javascript
var addOne(num) {
     return num++;
}

Không phải là chúng tôi đã làm điều đó theo cách của chúng tôi, hãy đào sâu vào

Ở đây chúng ta có thể thấy rằng lớp của chúng ta có hai thuộc tính. Kích thước và bảng. Bảng băm của chúng tôi sẽ chỉ là một mảng thông thường và kích thước sẽ là chiều dài của nó. Thêm về điều đó sau

Hàm băm phải luôn trả về cùng một đầu ra cho đầu vào cụ thể. Kết quả của chúng tôi không nên ngẫu nhiên

Ở đây, chúng tôi lặp qua chuỗi của mình và biến từng ký tự thành số ASCII của nó * 100. Sau đó, chúng tôi sử dụng toán tử mô đun (%) để làm cho id được tạo phù hợp với phạm vi của chúng tôi (kích thước của mảng của chúng tôi);

Điều này có nghĩa là bất kỳ id nào chúng tôi tạo sẽ là một số từ 0 đến giá trị kích thước được chỉ định của chúng tôi;

Để chèn một giá trị, chúng tôi chỉ cần băm khóa của mình và lưu giá trị của nó bên trong bảng bằng cách sử dụng id làm chỉ mục

Để truy xuất giá trị của khóa, chúng ta chỉ cần băm khóa mà chúng ta muốn tìm và truy cập mảng bằng cách sử dụng id làm chỉ mục

Đợi một chút, điều gì sẽ xảy ra nếu hai khóa khác nhau dẫn đến cùng một id?

Ví dụ: giả sử kích thước của chúng tôi = 2;

Rất có khả năng hàm băm của chúng ta sẽ trả về 1 hoặc 2

Vì vậy, nếu chúng ta lưu một giá trị với khóa “cat” và một giá trị khác với “dog” thì các giá trị của chúng ta có thể bị ghi đè, vì chúng ta chỉ có hai khoảng trắng trong mảng của mình

Khi hai lần băm hai khóa khác nhau dẫn đến cùng một id. Chúng tôi có những gì chúng tôi gọi là một vụ va chạm

Có nhiều cách khác nhau để giải quyết vấn đề này, nhưng chúng ta sẽ sử dụng danh sách liên kết để giải quyết vấn đề “nhỏ” của mình

Để thực hiện điều này, chúng ta cần nén một danh sách được liên kết bên trong mỗi chỉ mục của mảng bên trong hàm tạo của chúng ta. Chúng ta cũng sẽ phải cập nhật các phương thức insert() và get() để

Triển khai Danh sách liên kết trong Javascript

Hôm nay chúng ta sẽ tạo triển khai Cây tìm kiếm nhị phân của riêng mình, nhưng trước khi chúng ta viết một dòng mã, nó…

trung bình. com

Bây giờ chúng tôi đã triển khai thành công bảng băm giải quyết xung đột bằng cách sử dụng danh sách được liên kết

Tìm hiểu cây tìm kiếm nhị phân (Phần 1)

Cho đến giờ chúng ta đã tìm hiểu về LinkedList và Hash Tables, nhưng đã đến lúc nâng cao nó bằng cách tìm hiểu về Cây nhị phân…

trung bình. com

đây là kết quả cuối cùng

Và danh sách liên kết được sử dụng cho việc thực hiện này

Ghi chú. Nếu kích thước bảng băm của chúng ta quá nhỏ hoặc nếu hàm băm không đủ tốt, thì bảng băm của chúng ta có thể làm suy giảm hai danh sách được liên kết rất lớn, điều này sẽ làm giảm lợi thế hiệu suất tổng thể đạt được bằng cách sử dụng một danh sách ngay từ đầu

Điều này có nghĩa là thời gian truy cập của O(1) có thể giảm xuống 0(n);

Nếu bạn thích hướng dẫn này, đừng quên theo dõi tôi để biết thêm nội dung về cấu trúc dữ liệu và thuật toán trong tương lai

Hashtable trong JS là gì?

Bảng băm là gì và tại sao nó được sử dụng?

Bảng băm với ví dụ là gì?

Băm hoạt động như thế nào trong JavaScript?