Trong hướng dẫn này, bạn sẽ tìm hiểu Hashing là gì.
Hashing là một kỹ thuật ánh xạ một tập hợp lớn dữ liệu tùy ý vào các chỉ mục dạng bảng bằng cách sử dụng một hàm băm. Nó là một phương pháp để biểu diễn từ điển cho các tập dữ liệu lớn.
Nó cho phép hoạt động tra cứu, cập nhật và truy xuất diễn ra trong một thời gian không đổi O(1).
Tại sao cần băm?
Sau khi lưu trữ một lượng lớn dữ liệu, chúng ta cần thực hiện nhiều thao tác khác nhau trên những dữ liệu này. Việc tra cứu là không thể tránh khỏi đối với bộ dữ liệu. Tìm kiếm tuyến tính và tìm kiếm nhị phân thực hiện tra cứu / tìm kiếm theo thời gian phức tạp của O(n)và O(log n)tương ứng. Khi kích thước của tập dữ liệu tăng lên, những phức tạp này cũng trở nên cao đáng kể và không thể chấp nhận được.
Chúng ta cần một kỹ thuật không phụ thuộc vào kích thước của dữ liệu. Việc băm cho phép việc tra cứu diễn ra trong thời gian không đổi tức là O(1).
Hàm băm
Một hàm băm được sử dụng để ánh xạ từng phần tử của tập dữ liệu với các chỉ mục trong bảng.
Để biết thêm thông tin về bảng băm, kỹ thuật giải quyết xung đột và các hàm băm, vui lòng truy cập Bảng băm.
