Dường như kiến thức chung là các bảng băm có thể đạt được O (1), nhưng điều đó chưa bao giờ có ý nghĩa đối với tôi. Ai đó có thể vui lòng giải thích nó? Dưới đây là hai tình huống cần lưu ý:Bảng băm thực sự có thể là O (1)?
A. Giá trị là một int nhỏ hơn kích thước của bảng băm. Do đó, giá trị là giá trị băm của chính nó, do đó không có bảng băm. Nhưng nếu có, nó sẽ là O (1) và vẫn không hiệu quả.
B. Bạn phải tính giá trị băm của giá trị. Trong trường hợp này, thứ tự là O (n) cho kích thước của dữ liệu được tra cứu. Việc tra cứu có thể là O (1) sau khi bạn thực hiện công việc O (n), nhưng điều đó vẫn xuất hiện với O (n) trong mắt tôi.
Và trừ khi bạn có băm hoàn hảo hoặc bảng băm lớn, có thể có một số mục trên mỗi nhóm. Vì vậy, nó biến thành một tìm kiếm tuyến tính nhỏ tại một số điểm anyway.
Tôi nghĩ bảng băm là tuyệt vời, nhưng tôi không nhận được chỉ định O (1) trừ khi nó được cho là lý thuyết.
Wikipedia article for hash tables liên tục tham chiếu thời gian tra cứu liên tục và bỏ qua hoàn toàn chi phí của hàm băm. Đó có thực sự là một biện pháp công bằng không?
Edit: Để tóm tắt những gì tôi đã học:
Đó là về mặt kỹ thuật đúng bởi vì các hàm băm không cần phải sử dụng tất cả các thông tin trong khóa và do đó có thể là thời gian liên tục, và bởi vì một chiếc bàn đủ lớn có thể mang va chạm xuống gần thời gian không đổi.
Điều này đúng trong thực tế bởi vì theo thời gian nó chỉ hoạt động miễn là hàm băm và kích thước bảng được chọn để giảm thiểu xung đột, mặc dù điều đó thường có nghĩa là không sử dụng hàm băm thời gian cố định.
Nó khấu hao (1), không phải O (1). – kennytm
Hãy nhớ rằng O() là giới hạn cho một số lượng lớn các hoạt động. Trên 'trung bình' bạn sẽ không có nhiều va chạm - nó không cần thiết mà một hoạt động cá nhân không có va chạm. –
Tùy thuộc vào việc thực hiện chuỗi, chuỗi có thể mang theo giá trị băm của chúng với chúng, vì vậy điều này sẽ không đổi. Vấn đề là, nó không liên quan đến sự phức tạp tra cứu hash. –