Bảng băm, một công cụ quen thuộc trong khoa học máy tính từ những năm 1950, đóng vai trò quan trọng trong việc tìm kiếm, bổ sung và loại bỏ thông tin trong các cơ sở dữ liệu lớn, cũng như quản lý mật khẩu và bộ nhớ đệm của máy tính.
Năm 1985, nhà khoa học máy tính Andrew Yao đưa ra một giả thuyết về bảng băm. Ông cho rằng, trong tình huống xấu nhất, số bước cần thiết để tìm một ô trống trong bảng băm tương ứng với số lượng ô có trong bảng.
Tuy nhiên, một nghiên cứu gần đây đã thách thức quan điểm này. Andrew Krapivin, một nghiên cứu sinh 22 tuổi tại Đại học Cambridge (Anh), cùng với Giáo sư Martín Farach-Colton của Đại học New York và Phó giáo sư William Kuszmaul tại Đại học Carnegie Mellon (Mỹ), đã phát triển một loại bảng băm mới. Phát hiện này cho thấy, ngay cả trong trường hợp xấu nhất, số bước cần thiết để tìm một ô trống vẫn ít hơn đáng kể so với tổng số ô trong bảng băm.
Công trình đột phá này đã được công bố trên arXiv, một kho lưu trữ trực tuyến các bài báo khoa học, vào tháng 1 năm nay.
Trong nhiều năm, phần lớn giới khoa học máy tính đều tin vào giả thuyết của Yao. Phát hiện mới này được các chuyên gia trong ngành đánh giá là một bước tiến lớn. Phó giáo sư Kuszmaul nhận xét: “Krapivin không chỉ tạo ra một bảng băm thú vị, mà còn thực sự bác bỏ một giả thuyết đã tồn tại suốt 40 năm.”
Alex Conway, một chuyên gia từ Viện nghiên cứu sau đại học Cornell Tech của Đại học Cornell, cho biết: “Bảng băm là một trong những cấu trúc dữ liệu lâu đời nhất và vẫn là một phương pháp lưu trữ dữ liệu hiệu quả. Tuy nhiên, vẫn còn nhiều câu hỏi chưa được giải đáp về cách chúng hoạt động, và bài báo này đã trả lời một số câu hỏi đó một cách đáng ngạc nhiên.”
Krapivin, cựu sinh viên Đại học Rutgers, Mỹ, đã có được khám phá này trong quá trình nghiên cứu về cách tiết kiệm bộ nhớ máy tính để tăng tốc độ truy vấn thông tin thông qua việc tổ chức lại dữ liệu.
Ban đầu, Giáo sư Martín Farach-Colton, người hướng dẫn Krapivin, đã hoài nghi về thiết kế mới này. Ông cho rằng bảng băm là một trong những cấu trúc dữ liệu được nghiên cứu kỹ lưỡng nhất trong khoa học máy tính. Để đảm bảo tính chính xác, ông đã nhờ Phó giáo sư William Kuszmaul kiểm tra lại.
Nhờ phát hiện quan trọng này, Krapivin đã được trao học bổng Goldwater vào năm 2023, một trong những học bổng danh giá nhất tại Mỹ, nhằm khuyến khích các nghiên cứu trong lĩnh vực STEM (Khoa học, Kỹ thuật và Toán học). Năm ngoái, Krapivin cũng trở thành sinh viên đầu tiên của Đại học Rutgers trong vòng 10 năm nhận được học bổng Churchill, cho phép anh theo học tại Đại học Cambridge, một trong những trường đại học hàng đầu thế giới.
Admin
Nguồn: VnExpress
