Hashtable là gì?

Trong khoa học máy tính, một hashtable là một cấu trúc dữ liệu để lưu trữ dữ liệu bao gồm một danh sách các giá trị, được gọi là các khóa, được ghép nối với một danh sách các giá trị tương ứng, được gọi là một mảng.Ví dụ, một tên doanh nghiệp có thể được ghép nối với địa chỉ của nó.Thông thường, mỗi giá trị trong mảng có số vị trí được gọi là băm.Hàm băm thường là một tập hợp các hướng dẫn hoặc thuật toán ánh xạ từng giá trị chính thành một băm mdash;Ví dụ, kết nối tên doanh nghiệp với địa chỉ, số điện thoại và danh mục kinh doanh của nó.Mục đích của hàm băm là gán từng khóa cho một giá trị tương ứng duy nhất trong mảng;Điều này thường được gọi là băm.Các hàm băm phải được định dạng đúng cho một hashtable để hoạt động đúng.Hiệu suất của một hashtable trên một tập hợp dữ liệu phụ thuộc vào hiệu quả của hàm băm của nó.Một hàm băm tốt thường cung cấp cho việc tra cứu đồng đều các phím và phân phối đồng đều các ánh xạ trong mảng tương ứng.Va chạm băm xảy ra khi hai khóa được gán cho cùng một giá trị tương ứng.Khi xảy ra va chạm băm, hàm băm thường được thực hiện lại cho đến khi tìm thấy giá trị tương ứng duy nhất;Điều này thường dẫn đến thời gian băm dài hơn.Mặc dù số lượng khóa trong hashtable thường được cố định, đôi khi có thể có các phím trùng lặp.Mặc dù vậy, một hashtable được thiết kế tốt có các hàm băm hiệu quả ánh xạ từng khóa cho một giá trị tương ứng duy nhất trong mảng.Đôi khi, các hàm băm không hiệu quả trong hashtable cũng có thể tạo ra một cụm ánh xạ.Nếu hàm băm tạo ra một cụm ánh xạ cho các khóa hiện có, điều này có thể tăng thời gian cần thiết để tra cứu các giá trị tương ứng.Điều này có thể làm chậm băm cho các khóa trong tương lai vì hầu hết các hàm băm thường tìm kiếm vị trí có sẵn tiếp theo trong mảng.Nếu một cụm lớn các giá trị đã được gán, thông thường sẽ mất nhiều thời gian hơn để tìm kiếm một giá trị không được chỉ định cho một khóa mới.Hệ số tải là một khái niệm khác liên quan đến hiệu quả của hàm băm;Hệ số tải là lượng băm đã có liên quan đến kích thước tổng thể của mảng tương ứng trong một hashtable.Nó thường được xác định bằng cách chia số lượng các khóa đã được gán cho kích thước của mảng tương ứng.Khi hệ số tải tăng lên, một hàm băm tốt thường sẽ vẫn duy trì số lượng va chạm và cụm liên tục lên đến một điểm nhất định.Thông thường, ngưỡng này có thể được sử dụng để xác định hàm băm hiệu quả như thế nào với một số khóa nhất định và khi có thể cần một hàm băm mới. Nhiều nhà nghiên cứu khoa học máy tính đã cố gắng tạo ra chức năng băm hoàn hảo mdash;một trong đó không tạo ra va chạm hoặc cụm được đưa ra một hệ số tải ngày càng tăng.Về lý thuyết, chìa khóa để tạo ra một hashtable hoàn hảo là tạo ra một hàm băm hoàn hảo.Nói chung, các nhà nghiên cứu tin rằng một hàm băm hoàn hảo nên có hiệu suất không đổi mdash;số lượng va chạm và cụm mdash;với một hệ số tải ngày càng tăng.Trong trường hợp xấu nhất, một hàm băm hoàn hảo vẫn cho phép băm liên tục mà không đạt đến ngưỡng.