Mục tiêu chính của hashmap là lưu trữ một tập dữ liệu và cung cấp các tra cứu thời gian gần như liên tục trên đó bằng một khóa duy nhất. Có hai kiểu triển khai hashmap phổ biến
- chuỗi riêng biệt. một với một mảng các thùng (danh sách được liên kết)
- mở địa chỉ. một mảng duy nhất được phân bổ với không gian bổ sung để xung đột chỉ mục có thể được giải quyết bằng cách đặt mục nhập vào một vị trí liền kề
Chuỗi riêng biệt được ưu tiên hơn nếu hashmap có thể có hàm băm kém, không nên phân bổ trước dung lượng lưu trữ cho các vị trí có khả năng không được sử dụng hoặc các mục nhập có thể có kích thước thay đổi. Loại hashmap này có thể tiếp tục hoạt động tương đối hiệu quả ngay cả khi hệ số tải vượt quá 1. 0. Rõ ràng, cần có thêm bộ nhớ trong mỗi mục để lưu trữ các con trỏ danh sách được liên kết
Hashmap sử dụng địa chỉ mở có lợi thế hiệu suất tiềm năng khi hệ số tải được giữ dưới một ngưỡng nhất định (thường là khoảng 0. 7) và một hàm băm khá tốt được sử dụng. Điều này là do chúng tránh bỏ lỡ bộ nhớ cache tiềm ẩn và nhiều phân bổ bộ nhớ nhỏ được liên kết với danh sách được liên kết và thực hiện tất cả các hoạt động trong một mảng được phân bổ trước liền kề. Lặp lại qua tất cả các yếu tố cũng rẻ hơn. Vấn đề là các hashmap sử dụng địa chỉ mở phải được phân bổ lại thành kích thước lớn hơn và được băm lại để duy trì hệ số tải lý tưởng, nếu không chúng sẽ phải đối mặt với một hình phạt đáng kể về hiệu suất. Hệ số tải của chúng không thể vượt quá 1. 0
Một số chỉ số hiệu suất chính để đánh giá khi tạo hashmap sẽ bao gồm
- hệ số tải tối đa
- Số lần va chạm trung bình khi chèn
- Phân phối va chạm. phân phối không đồng đều (phân cụm) có thể chỉ ra hàm băm kém
- Thời gian tương đối cho các hoạt động khác nhau. đặt, nhận, xóa các mục hiện có và không tồn tại
Đây là một triển khai hashmap linh hoạt mà tôi đã thực hiện. Tôi đã sử dụng địa chỉ mở và thăm dò tuyến tính để giải quyết va chạm
Các điểm chuẩn sau đã được chạy trên Macbook Pro 2019 của tôi (2. Intel Core i9 8 nhân 4 GHz) sử dụng gcc-9. Các mục là số nguyên 4 byte đơn giản. Hàm băm là MurmurHash3. Thử nghiệm với 5.000.000 mục. Kết quả _______________ là các hashmap được tạo với dung lượng ban đầu là 5.000.000