Khi chúng ta nói về phức tạp tiệm cận, chúng ta thường tính đến rất lớn n. Bây giờ để xử lý va chạm trong một bảng băm một số phương pháp được băm chuỗi băm & thăm dò tuyến tính. Trong cả hai trường hợp, hai điều có thể xảy ra (điều đó sẽ giúp trả lời câu hỏi của bạn): 1. Bạn có thể yêu cầu thay đổi kích thước của bảng băm do nó nhận được đầy đủ 2. Va chạm có thể xảy ra.
Trong trường hợp xấu nhất nó sẽ phụ thuộc vào cách bạn đã triển khai bảng băm của bạn, nói trong thăm dò tuyến tính bạn không tìm thấy số, bạn tiếp tục di chuyển và số bạn đang tìm kiếm ở cuối. Ở đây có O (n) trường hợp xấu nhất chạy thời gian. Đến với kỹ thuật băm chuỗi, khi một va chạm xảy ra, để xử lý chúng nói rằng chúng ta đã lưu trữ các khóa trong cây nhị phân cân bằng nên thời gian chạy trường hợp xấu nhất sẽ là O (log n).
Bây giờ đến thời gian chạy trường hợp tốt nhất, tôi nghĩ không có nhầm lẫn, trong cả hai trường hợp, nó sẽ là O (1).
O (n) sẽ xảy ra trong trường hợp xấu nhất và không phải trong trường hợp trung bình của bảng băm được thiết kế tốt. Nếu điều đó bắt đầu xảy ra trong trường hợp bảng băm trung bình sẽ không tìm thấy một vị trí trong Cấu trúc dữ liệu bởi vì sau đó cây cân bằng trung bình sẽ cung cấp cho bạn O (log n) luôn và ON TOP THAT sẽ bảo toàn thứ tự.
Rất tiếc khi nói điều này nhưng không may là bạn của bạn là đúng. Trường hợp của bạn sẽ xảy ra trong trường hợp xấu nhất.
Ngoài ra nhìn vào đây để thứ thông tin mới hơn ví dụ: thời gian chạy khấu hao: Time complexity of Hash table
Tôi muốn thêm vào Yavar câu trả lời: nhớ, rằng O (1) không phải là một op. Nó có thể là một hằng số lớn, nhưng điều đó không quan trọng nếu nó không có nguồn gốc từ một biến như n. Thậm chí nếu bạn cần phải đi qua 20 nút để đặt một băm, nó vẫn là một O (1). Tất nhiên, điều đó làm việc cho bảng băm chỉ khi một số điều kiện là đúng, nhưng đối với bảng băm được thiết kế tốt là O (1) trung bình – Archeg