Làm cách nào để cải thiện hiệu suất của một hashtable với 1 triệu thành phần và 997 nhóm?

Question

Đây là câu hỏi phỏng vấn.

Giả sử có 1 triệu phần tử trong bảng và 997 nhóm danh sách không theo thứ tự. Giả sử rằng hàm băm phân phối các khóa có xác suất bằng nhau (nghĩa là, mỗi nhóm có 1000 phần tử).

Thời gian trường hợp xấu nhất để tìm một phần tử không có trong bảng là gì? Để tìm cái nào nằm trong bàn? Làm thế nào bạn có thể cải thiện điều này?

Giải pháp của tôi: Thời gian trường hợp xấu nhất khi tìm kiếm phần tử không có trong bảng và trong bảng đều là O (1000). 1000 là độ dài của danh sách chưa được phân loại.

Cải thiện: (0) đơn giản, tăng số lượng thùng> 1 triệu. (1) mỗi nhóm giữ một hashtable thứ hai, trong đó sử dụng một hàm băm khác nhau để tính toán giá trị băm cho bảng thứ hai. nó sẽ là O (1) (2) mỗi thùng chứa một cây tìm kiếm nhị phân. Nó sẽ là O (lg n).

là có thể thực hiện sự cân bằng giữa không gian và thời gian. Giữ cho cả hai người trong số họ trong một phạm vi hợp lý.

Bất kỳ ý tưởng nào tốt hơn? cảm ơn !

Answer 1

Cải thiện đơn giản nhất và rõ ràng nhất là tăng số lượng nhóm trong bảng băm lên 1,2 triệu - ít nhất giả sử hàm băm của bạn có thể tạo ra các số trong phạm vi đó (thông thường).

Answer 2

Nếu bạn không thể sử dụng một cấu trúc dữ liệu hoặc một bảng lớn hơn vẫn còn lựa chọn:

Nếu tập tích cực của các yếu tố là gần hơn đến 1000 hơn 1M bạn có thể cải thiện thời gian tra cứu thành công bình quân bằng cách di chuyển từng phần tử bạn tìm thấy mặt trước của danh sách của nó. Điều đó sẽ cho phép nó được tìm thấy một cách nhanh chóng khi nó được tái sử dụng.

Tương tự, nếu có một tập hợp các lỗi xảy ra thường xuyên, bạn có thể lưu vào bộ nhớ cache kết quả tiêu cực (đây có thể chỉ là một kiểu nhập đặc biệt trong bảng băm).

Answer 3

Giả sử có 1 triệu phần tử trong bảng và 997 nhóm danh sách không theo thứ tự. Giả sử rằng hàm băm phân phối các khóa có xác suất bằng nhau (nghĩa là, mỗi nhóm có 1000 phần tử).

Điều đó không khá thêm lên, nhưng chúng ta hãy chạy với nó ....

thời trường hợp xấu nhất để tìm một yếu tố mà không phải là trong bảng là gì? Để tìm cái nào nằm trong bàn? Làm thế nào bạn có thể cải thiện điều này?

Điều tồi tệ nhất (và tốt nhất = only) Trường hợp cho các yếu tố còn thiếu là bạn băm để một xô sau đó đi qua kiểm tra tất cả các yếu tố trong đó danh sách cụ thể (ví dụ: 1000) sau đó thất bại. Nếu họ muốn ký hiệu big-O, theo định nghĩa mô tả hiệu suất thay đổi như thế nào với số lượng phần tử N, vì vậy chúng ta phải đưa ra giả thiết về cách # xô thay đổi với N: đoán của tôi là 997 xô là một số cố định và sẽ không tăng lên nếu số lượng phần tử tăng lên. Do đó, số lượng so sánh là N/997, là yếu tố tuyến tính - vẫn là O (N).

Giải pháp của tôi: Trường hợp xấu nhất khi tìm phần tử không có trong bảng và trong bảng đều là O (1000). 1000 là độ dài của danh sách chưa được phân loại.

Không - bạn đang nghĩ đến số lượng so sánh - nhưng ký hiệu big-O là về khả năng mở rộng.

Cải thiện: (0) đơn giản, tăng số lượng thùng> 1 triệu. (1) mỗi nhóm giữ một hashtable thứ hai, trong đó sử dụng một hàm băm khác nhau để tính toán giá trị băm cho bảng thứ hai. nó sẽ là O (1) (2) mỗi thùng chứa một cây tìm kiếm nhị phân. Nó sẽ là O (lg n).

là có thể thực hiện sự cân bằng giữa không gian và thời gian. Giữ cho cả hai người trong số họ trong một phạm vi hợp lý.

Vâng có - xung đột trung bình liên quan đến số lượng mục nhập và nhóm. Nếu bạn muốn có rất ít va chạm, bạn sẽ có hơn 1 triệu mục trong bảng, nhưng điều đó sẽ lãng phí bộ nhớ, mặc dù đối với các đối tượng lớn, bạn có thể có chỉ mục hoặc con trỏ tới đối tượng thực. Một cách khác là tìm kiếm các cơ chế xử lý va chạm nhanh hơn, chẳng hạn như thử một loạt các bù đắp từ nhóm được băm (sử dụng% để ánh xạ các chuyển vị trở lại kích thước bảng), thay vì sử dụng một số đống bằng cách sử dụng các danh sách liên kết. Phục hồi là một lựa chọn khác, với tỷ lệ va chạm thấp hơn nhưng thường cần nhiều CPU hơn, và có một danh sách dài các thuật toán băm tùy ý rất có vấn đề.

Bảng băm trong bảng băm hoàn toàn vô nghĩa và lãng phí đáng kể bộ nhớ. Tốt hơn nhiều để sử dụng một phần của không gian đó để giảm va chạm trong bảng băm bên ngoài.

Answer 4

Rõ ràng là tăng số lượng thùng sẽ cải thiện hiệu suất. Giả sử đây không phải là một lựa chọn (vì bất kỳ lý do gì), tôi đề xuất như sau:

Thông thường bảng băm bao gồm các thùng, mỗi danh sách giữ một danh sách liên kết (trỏ vào đầu của nó). Tuy nhiên, bạn có thể tạo một bảng băm, các thùng chứa một cây tìm kiếm nhị phân (con trỏ đến gốc của nó) chứ không phải là danh sách.

Để bạn sẽ có hybrid của bảng băm và cây nhị phân. Một khi tôi đã thực hiện điều đó. Tôi đã không có một giới hạn về số lượng các thùng trong bảng băm, tuy nhiên tôi không biết số lượng các yếu tố ngay từ đầu, cộng với tôi không có thông tin về chất lượng của hàm băm. Do đó, tôi đã tạo ra một bảng băm với số lượng hợp lý của các thùng, và phần còn lại của sự mơ hồ đã được giải quyết bởi cây nhị phân.

Nếu N là số phần tử và M là số nhóm, thì độ phức tạp sẽ tăng lên dưới dạng O [log (N/M)], trong trường hợp phân phối bằng nhau.