7
Tôi biết nguyên tắc cơ bản của cấu trúc dữ liệu bảng băm. Nếu tôi có một bảng băm có kích thước N, tôi phải phân phối dữ liệu của mình vào các nhóm N này càng đồng đều càng tốt.Làm cách nào để triển khai bảng băm kích thước động?
Nhưng thực tế, hầu hết các ngôn ngữ đều có các loại bảng băm tích hợp sẵn. Khi tôi sử dụng chúng, tôi không cần phải biết kích thước của bảng băm trước. Tôi chỉ cần đặt bất cứ điều gì tôi muốn vào nó. Ví dụ: trong Ruby:
h = {}
10000000.times{ |i| h[i]=rand(10000) }
Làm cách nào để thực hiện việc này?
phương pháp phục hồi tốt đẹp là tăng gấp đôi kích thước của bảng và sau đó khi bạn tìm kiếm giá trị, bạn băm khóa của nó và thực hiện tìm kiếm modulu trong bảng băm bắt đầu bằng 'hash% current_size', rồi 'băm % current_size/2', v.v. Khi bạn tìm thấy giá trị, bạn có thể khôi phục nó. Bằng cách đó bạn có thể làm việc phục hồi lười biếng mà không làm mất hiệu suất quá nhiều, bởi vì các giá trị thường truy cập được tự động phục hồi. –
@DvirVolk, phục hồi lười biếng thật tuyệt. Bạn đã biết mục nhập trong bảng băm nhiều nhất và biết nơi để diễn giải từ các bảng băm thấp hơn. Nhưng bạn có thể có tình huống khi một số mục nhập sẽ giữ toàn bộ các thùng trống. Đó là "thay đổi kích thước tăng dần" từ wiki là giải pháp tốc độ trao đổi dữ liệu cho kích thước dữ liệu như tôi hiểu (cuối cùng bạn giữ 2 * N nhóm trong đó N là kích thước của bảng băm nhiều nhất). Kích thước gấp đôi là tốt cho "sao chép tất cả các mục" bởi thực tế là bạn phải chia thùng đơn thành hai hoặc hợp nhất hai thành một (không tính toán lại hàm băm) với việc sử dụng lại danh sách liên kết các nhóm cũ. – ony