Chọn đúng một phần tử ngẫu nhiên từ bảng băm có chuỗi?

Question

Chỉ cần thực hành (và không phải là một bài tập về nhà) Tôi đã cố gắng để giải quyết vấn đề này (CLRS, 3rd edition, tập thể dục 11,2-6):

Giả sử chúng ta đã được lưu trữ phím n trong một bảng băm của kích thước m, với va chạm được giải quyết bằng chuỗi và chúng tôi biết độ dài của mỗi chuỗi , bao gồm độ dài L của chuỗi dài nhất. Mô tả thủ tục chọn ngẫu nhiên đồng nhất khóa từ các phím trong bảng băm và trả về trong thời gian dự kiến ​​O (L * (1 + m/n)).

Điều tôi nghĩ cho đến nay là xác suất của mỗi khóa được trả về là 1/n. Nếu chúng ta cố gắng lấy một giá trị ngẫu nhiên x từ 1 đến n và cố gắng tìm khóa thứ x trong chuỗi đầu tiên được sắp xếp theo nhóm thì dọc theo chuỗi trong thùng, thì sẽ lấy O (m) để tìm nhóm thích hợp bằng cách thông qua xô từng người một và O (L) để có được chìa khóa đúng trong chuỗi.

Answer 1

Lặp lại các bước sau cho đến khi một phần tử được trả về:

• ngẫu nhiên chọn một cái xô. Để k là số phần tử trong nhóm.
• Chọn p đồng nhất ngẫu nhiên từ 1 ... L. Nếu p <= k sau đó trả lại thành phần thứ p trong thùng.

Cần làm rõ rằng thủ tục trả về một phần tử một cách đồng nhất một cách ngẫu nhiên. Chúng tôi sắp xếp áp dụng lấy mẫu từ chối cho các phần tử được đặt trong một mảng 2D.

Số lượng yếu tố dự kiến ​​cho mỗi nhóm là n/m. Xác suất mà nỗ lực lấy mẫu thành công là (n/m)/L. Do đó, số lần thử mong muốn cần tìm một thùng là L * m/n. Cùng với chi phí O(L) truy xuất phần tử từ nhóm, thời gian chạy dự kiến ​​là O(L * (1 + m/n)).