Tôi đã triển khai các hàm bảng băm của riêng mình trong C, nhưng hiện tại nó không hỗ trợ thay đổi kích thước. Tôi đã tự hỏi những thuật toán nào tồn tại ngoài cách brute-force của việc tạo ra một bảng băm rỗng mới và di chuyển mọi thứ ở đó?Thuật toán nào có sẵn để thay đổi kích thước bảng băm?
Có thay đổi kích thước gia tăng.
Từ Wikipedia:
Incremental thay đổi kích thước
Triển khai một số bảng băm, đáng chú ý là trong các hệ thống thời gian thực, có thể không trả giá của mở rộng bảng băm tất cả cùng một lúc, bởi vì nó có thể hoạt động gián đoạn thời gian quan trọng. Nếu người ta không thể tránh thay đổi kích thước động, một giải pháp là để thực hiện các thay đổi kích thước dần:
Trong thay đổi kích thước, bố trí bảng băm mới, nhưng giữ bảng cũ không thay đổi. Trong mỗi hoạt động tìm kiếm hoặc xóa, hãy kiểm tra cả hai bảng. Chỉ thực hiện thao tác chèn trong bảng mới. Tại mỗi lần chèn cũng di chuyển các phần tử r từ bảng cũ sang bảng mới. Khi tất cả các phần tử được xóa khỏi bảng cũ, hãy xử lý nó.
Để đảm bảo rằng bảng cũ sẽ hoàn toàn sao chép kết thúc trước khi các bảng mới bản thân cần phải được mở rộng, nó là cần thiết để tăng kích thước của bảng bằng một yếu tố tối thiểu (r + 1)/r trong khi thay đổi kích thước.
Vì vậy, đây không phải là cách thông minh để di chuyển tất cả các phần tử từ bảng cũ sang bảng mới (và nếu có, tôi chưa thấy); thay vào đó, nó giúp giảm bớt gánh nặng thay đổi kích thước bằng cách cho phép di chuyển diễn ra dần dần.
Wikipedia có một số words of wisdom về chủ đề này.
Ngoài ra, nó không phải là một giải pháp, nhưng có thể là một phần của một - nếu bạn đang ở dưới cửa sổ, bạn có thể sử dụng họ VirtualAlloc chức năng cho phép bạn đặt không gian địa chỉ mà không thực sự cam kết các trang bộ nhớ. Đó là, trong thuật ngữ laymans, bạn sẽ làm một cái gì đó giống như một "malloc" và nói với nó để "dự trữ 1000MB, nhưng chỉ làm cho 10 đầu tiên có sẵn". Vì vậy, nếu bạn viết quá 10MB, bạn sẽ nhận được sự cố thông thường. Nhưng khi thời gian đến để mở rộng, bạn chỉ cần nói "OK, cho tôi thêm 10MB sau những cái đầu tiên". Và 10MB tiếp theo được cung cấp tại địa chỉ trực tiếp sau 10MB đầu tiên. Nó giống như thay đổi kích thước một mảng. RAM thực tế đang sử dụng sẽ chỉ nhiều như bạn cần, nhưng địa chỉ bộ nhớ sẽ được đặt trước để các hoạt động phân bổ bộ nhớ khác không sử dụng chúng.
Cảnh báo thông thường là để mã này lên mã khách hàng để đoán số lượng nhóm tốt nhất lên phía trước. Đó là hữu ích, khách hàng thường có một dự đoán hợp lý là có bao nhiêu yếu tố sẽ kết thúc trong bảng. Nếu bạn muốn tự động làm điều đó thì trước tiên bạn phải khai báo một mảng các số nguyên tố cho kích thước thùng. Khi bạn thấy hệ số tải của một thùng quá cao, hãy chọn nguyên tố tiếp theo trong mảng, tạo lại danh sách nhóm và di chuyển các phần tử từ các nhóm cũ sang bảng mới.
Đó là một cách khá thông minh để thay đổi kích thước mảng - nếu bạn có không gian địa chỉ để ghi (x64) - nhưng nó sẽ không hoạt động cho hashtables, bạn vẫn phải khôi phục mọi thứ (và nó phức tạp hơn khi làm điều đó trong nơi.) – Eloff
@Eloff - Vâng, như tôi đã nói - nó không phải là một giải pháp riêng của mình, chỉ là một phần của một. Và bạn không cần phải dành nhiều không gian địa chỉ đó nữa. Chỉ cần một số tiền hợp lý. Nó không phải là một viên đạn bạc, nó chỉ làm cho hoạt động thay đổi kích thước nhanh hơn. –
Tôi thấy bạn đang đi đâu với điều này ngay bây giờ, nhưng nó không rõ ràng là nó thực sự sẽ thay đổi kích thước nhanh hơn. Chi phí chính ở đây không phải là phân bổ bộ nhớ, mà hầu như không có tính năng. Tất cả thời gian đi vào các lỗi trang mềm để đưa bộ nhớ mới vào không gian địa chỉ tiến trình (thường xảy ra trong bộ cấp phát bộ nhớ của bạn khi nó bộ nhớ) và trong chi phí cần thiết để băm lại và chèn lại tất cả các phần tử trong Hashtable . Nhưng đối với mảng động, bạn không cần phải sao chép bất kỳ thứ gì và bạn có thể trả từng lỗi trang mềm một lần (tăng lên một trang tại một thời điểm). – Eloff