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

Tạo một lớp cho Bảng băm của chúng tôi

Ở đâ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

Quyết định kích thước của bảng băm của chúng tôi

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 và truy xuất các giá trị trong bảng băm 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

Vì vậy, làm thế nào chúng ta có thể khắc phục điều này?

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à 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 băm là gì và tại sao nó được sử dụng?

Đây là một loại dữ liệu trừu tượng ánh xạ các khóa thành các giá trị . Bảng băm sử dụng hàm băm để tính toán một chỉ mục, còn được gọi là mã băm, vào một mảng các nhóm hoặc vị trí, từ đó có thể tìm thấy giá trị mong muốn. Trong quá trình tra cứu, khóa được băm và kết quả băm cho biết vị trí lưu trữ giá trị tương ứng.

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

Bảng băm là cấu trúc dữ liệu lưu trữ dữ liệu theo cách kết hợp . Trong bảng băm, dữ liệu được lưu trữ ở định dạng mảng, trong đó mỗi giá trị dữ liệu có giá trị chỉ mục duy nhất của riêng nó. Truy cập dữ liệu trở nên rất nhanh nếu chúng ta biết chỉ mục của dữ liệu mong muốn.

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

Hàm băm. Hàm băm được sử dụng để chuyển đổi một khóa nhất định thành một chỉ mục vị trí cụ thể . nó được sử dụng để ánh xạ từng khóa có thể vào một chỉ mục vị trí duy nhất. Nếu mọi khóa được ánh xạ vào một chỉ mục vị trí duy nhất, thì hàm băm được gọi là hàm băm hoàn hảo.