Tập Làm Coder
Member
Hơi khó hiểu khi Hashmap tìm kiếm O(1) nhưng các chương trình dạy học vẫn dạy Linear seach O(n) và Binary search O(log(n))
thắc mắc Hash map tìm kiếm nhanh vậy sao còn phải học Linear search và Binary search
- Thread starter Tập Làm Coder
- Start date
nipevt
Senior Member
2 cái kia là algo, cái còn lại là data structure, chẳng thấy mâu thuẫn gì với nhau.
linear search là cái cơ bản rồi, chỉ là duyệt qua mảng.
binary search dùng để duyệt trên mảng đã sắp xếp. không phải mọi lúc đều tạo ra cái hash table được.
Tập Làm Coder
Member
Câu này nghĩa là sao thím
katoshi
Senior Member
Hashmap nào tìm kiếm O(1). học lí thuyết quá nha chú em. O(1) chỉ là best case thôi
nipevt
Senior Member
katoshi
Senior Member
Worst case thì tùy vs các implement ở các sdk mới của Java C#...etc thì ko hẳn là 0(n) nha bác.Average và best case
worst case mới tới O(n).
Tập Làm Coder
Member
Chuyên gia về Java thì đủ uy tín chưa fen, Đoạn dưới có Java 8 wortcase là log(N) ko phải O(N) nhé, toàn phát biểu láo
nipevt
Senior Member
cái O(log(N)) kia là balanced binary search tree rồi chứa hash table nào?
theo lí thuyết thế chứ implementation của mấy ngôn ngữ kia nó tối ưu, heuristic các kiểu nên cũng khó tới O(n).
whateverman
Senior Member
katoshi
Senior Member
Chuyên gia thì đủ tin.
Nhưng cái thằng đọc post của ổng tên Tập làm coder thì ko đủ tin.
Ông đọc mà vẫn chưa hiểu là cái tôi nói vs cái post là như nhau à?
+ Tôi có nói worst case là O(n) bao giờ má
Thanh niên phát biểu láo à
katoshi
Senior Member
Post đó đugns mà thím.
Khi các key trùng hash. Thì dùng 1 cái balanced tree để lưu trữ cấc key trùng hash , để đạt tới 0(logN)
Đây là lý do mình kêu tùy implement , ko hẳn là O(N)đâuá thím.
Bart Simpson
Senior Member
vậy là sau Java 8 thì xử lý đụng độ bằng cây cân bằng thay vì linked list à mấy thím?
Tập Làm Coder
Member
Thế ông kia bảo là O(1) ông còn cãi gì nữaChuyên gia thì đủ tin.
Nhưng cái thằng đọc post của ổng tên Tập làm coder thì ko đủ tin.
Ông đọc mà vẫn chưa hiểu là cái tôi nói vs cái post là như nhau à?
+ Tôi có nói worst case là O(n) bao giờ má
katoshi
Senior Member
Từ ver mấy thì mình ko dám chắc, Nhưng thím có thể hiểu là Java có cải tiến như thế á.
các phiên bản đầu thì có xài linked list, sau thì cải tiến để đạt O(logN)
katoshi
Senior Member
Ông chuyên gia nói best case là O(1) , ko phải lúc nào cũng đảm bảo đạt O(1) có lúc worst case lên đến O(N) hoặc cải tiến hơn là O(logN). Nên khác j tôi nói???
Thanh niên đoc hiểu kém z.
Tập Làm Coder
Member
thế dữ liệu không lớn, ko clash gì thì nó không là O(1) là O mấy
người là nói là "typically" là những trường hợp bình thường, tui đang bảo là bình thường hashmap là O(1), sai chỗ nào
comment bắt bẻ vớ vẩn, sao không bảo Binary search với Linear search có best case là O(1) luôn đi
Last edited:
katoshi
Senior Member
thôi, chán đời thanh niên quá.
Làm engineer mà đù mẹ nói chuyện NẾU nhiều vs lắm điều kiện vs thiếu logic vậy.
Thằng cẹc nào ko biêt , nếu số lượng key ít và không có đụng độ hash thì làm cẹc thì bị nhảy vô worst case?? Cái này ko phải là best case cần thỏa điều kiện "ko đụng độ hash" trước à??
Bart Simpson
Senior Member
Bình tĩnh 2 thanh niên )))))))
)))))))
katoshi
Senior Member
Vì anh học nông vl, nên ko hiểu best case, average case, worst case.
Tôi vô nói rõ cho anh hiểu đừng hiểu vẹt là O(1). Cái tôi sót là ko nói rõ hết BAN ĐẦU cho anh 1 loạt best case, average case, worst case. Làm anh cứ cố chấp ko hiểu rộng ra. Xin lỗi
