Cấu trúc dữ liệu trong Java có hoạt động nhanh nhất cho contains() là gì?Cấu trúc dữ liệu nhanh nhất cho hàm contains() trong Java?
ví dụ: tôi có một tập hợp các số {1, 7, 12, 14, 20 ...}
Cho một số tùy ý khác x, cách nhanh nhất (trung bình) để tạo giá trị boolean cho dù x được chứa trong đặt hay không? Xác suất cho! Contains() cao hơn khoảng 5x.
Tất cả các cấu trúc bản đồ có cung cấp hoạt động o (1) không? HashSet là cách nhanh nhất để đi?
xem tập hợp (Hashset, enumset) và hàm băm (HashMap, linkedhash ..., idnetityhash ..) dựa trên việc triển khai. họ có O (1) cho chứa()
This cheatsheet là sự trợ giúp tuyệt vời.
băm (hash bộ) là tốt nhất với O (1)
Có 8 phút giữa câu trả lời của bạn và Pangea's. Yours không thêm giá trị nào, vậy tại sao lại đăng nó? –
@bart kết nối internet chậm thực sự – Will
@Có lẽ. Nếu vậy, thì bây giờ @Satish có đủ thời gian để loại bỏ câu trả lời dư thừa của mình. Tuy nhiên, anh ta chọn để cho nó lủng lẳng. Có lẽ với hy vọng thu thập một số điểm? Có lẽ đó là ý định bắt đầu, ai mà biết được? –
Đối với trường hợp cụ thể của bạn các số với mật độ tương đối cao Tôi muốn sử dụng một BitSet, nó sẽ nhanh hơn và nhỏ hơn nhiều so với một băm bộ.
Cấu trúc dữ liệu duy nhất nhanh hơn HashSet có thể là TIntHashSet từ Trove4J. Điều này sử dụng nguyên thủy tránh sự cần thiết phải sử dụng các đối tượng Integer.
Nếu số lượng số nguyên là nhỏ, bạn có thể tạo một boolean [] trong đó mỗi giá trị hiện tại được chuyển thành "true". Đây sẽ là O (1). Lưu ý: HashSet không phải là guarenteed là O (1) và có nhiều khả năng là O (log (log (N))).
Bạn sẽ chỉ nhận được O (1) cho một bản phân phối băm lý tưởng. Tuy nhiên, có nhiều khả năng bạn sẽ nhận được va chạm của các nhóm băm và một số tra cứu sẽ cần phải kiểm tra nhiều hơn một giá trị.
Đối với những gì nó có giá trị, bản đồ băm nói chung không O (1) tra cứu khi va chạm băm xảy ra (và chúng có thể xảy ra khá thường xuyên, nếu rất ít tại một thời điểm). Trường hợp xấu nhất là O (n) trong tra cứu. – Blindy
Tôi đồng ý với Blindy. Hiệu suất của bộ sưu tập dựa trên băm bị giới hạn bởi hiệu suất của hàm băm. – sbidwai
Khi tôi mới đi, trang web đã ngừng hoạt động. Nếu điều này xảy ra với bạn, bạn có thể sử dụng [link] này (http://web.archive.org/web/20120105103844/http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2. pdf) – EasilyBaffled