Quy tắc để chọn triển khai Bộ sưu tập Java?

Question

Bất kỳ ai cũng có một quy tắc tốt để chọn giữa các triển khai khác nhau của các giao diện Bộ sưu tập Java như Danh sách, Bản đồ hoặc Bộ?

Ví dụ: thường là lý do tại sao hoặc trong trường hợp nào tôi muốn sử dụng Vector hoặc ArrayList, Hashtable hoặc HashMap?

Answer 1

Tôi đã luôn luôn làm những quyết định trên cơ sở từng trường hợp, tùy thuộc vào trường hợp sử dụng, chẳng hạn như:

• Tôi có cần phải đặt hàng để duy trì?
• Tôi có khóa/giá trị rỗng không? Dups?
• Nó sẽ được truy cập bởi nhiều chủ đề
• Tôi có cần cặp khóa/giá trị
• Tôi có cần truy cập ngẫu nhiên không?

Và sau đó tôi thoát phiên bản thứ 5 tiện dụng của mình Java trong Nutshell và so sánh ~ 20 tùy chọn. Nó có những bảng nhỏ đẹp trong Chương năm để giúp tìm hiểu xem cái nào là thích hợp.

Ok, có thể nếu tôi biết tắt dải quấn mà một ArrayList đơn giản hoặc HashSet sẽ thực hiện thủ thuật, tôi sẽ không xem xét tất cả. ;) nhưng nếu có bất cứ điều gì từ xa phức tạp về việc sử dụng theo ý muốn của tôi, bạn đặt cược tôi đang ở trong cuốn sách. BTW, tôi mặc dù Vector được cho là 'mũ cũ' - tôi đã không sử dụng trong nhiều năm.

Answer 2

Giới thiệu về câu hỏi đầu tiên của bạn ...

Danh sách, Bản đồ và Đặt phục vụ các mục đích khác nhau. Tôi khuyên bạn nên đọc về Khung công tác Bộ sưu tập Java tại http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

Để được cụ thể hơn một chút:

• Danh sách sử dụng nếu bạn cần một cấu trúc dữ liệu mảng giống như và bạn cần phải lặp qua các yếu tố
• sử dụng Bản đồ nếu bạn cần một cái gì đó giống như một cuốn từ điển
• sử dụng một Set nếu bạn chỉ cần quyết định xem có cái gì đó thuộc về bộ này hay không.

Về câu hỏi thứ hai của bạn ...

Sự khác biệt chính giữa Vector và ArrayList là cựu được đồng bộ, sau này không được đồng bộ hóa. Bạn có thể đọc thêm về đồng bộ hóa trong Java Concurrency in Practice.

Sự khác biệt giữa Hashtable (lưu ý rằng T không phải là chữ cái viết hoa) và HashMap tương tự, trước đây được đồng bộ hóa, sau đó không được đồng bộ hóa.

Tôi có thể nói rằng không có quy tắc chung nào cho việc thực hiện một triển khai này hay cách triển khai khác, nó thực sự phụ thuộc vào nhu cầu của bạn.

Answer 3

Danh sách cho phép các mục trùng lặp, trong khi Bộ chỉ cho phép một phiên bản.

Tôi sẽ sử dụng Bản đồ bất cứ khi nào tôi cần thực hiện tra cứu.

Để triển khai cụ thể, có các biến thể bảo toàn đơn đặt hàng của Bản đồ và Bộ nhưng phần lớn nó giảm tốc độ. Tôi sẽ có xu hướng sử dụng ArrayList cho danh sách nhỏ và HashSet hợp lý cho các bộ hợp lý nhỏ, nhưng có nhiều triển khai (bao gồm cả bất kỳ thứ gì bạn tự viết). HashMap khá phổ biến đối với Maps. Bất cứ điều gì nhiều hơn 'hợp lý nhỏ' và bạn phải bắt đầu lo lắng về bộ nhớ để có cách cụ thể hơn về mặt thuật toán.

This page có lô hình ảnh động cùng với kiểm tra mã mẫu LinkedList vs. ArrayList nếu bạn quan tâm đến số cứng.

EDIT: Tôi hy vọng các liên kết sau đây chứng minh như thế nào những điều này là thực sự chỉ mục trong một hộp công cụ, bạn chỉ cần phải suy nghĩ về những gì nhu cầu của bạn là: Xem Commons-Bộ sưu tập các phiên bản của Map, List và Set.

Answer 4

Tôi giả sử bạn biết sự khác biệt giữa Danh sách, Đặt và Bản đồ từ các câu trả lời ở trên. Tại sao bạn sẽ chọn giữa các lớp thực hiện của họ là một điều khác. Ví dụ:

Danh sách:

1. ArrayList là nhanh chóng về lấy, nhưng chậm trên chèn. Thật tốt cho việc triển khai đọc nhiều nhưng không chèn/xóa nhiều. Nó giữ dữ liệu của nó trong một khối liên tục của bộ nhớ, do đó, mỗi khi nó cần phải mở rộng, nó sao chép toàn bộ mảng.
2. LinkedList chậm khi truy xuất, nhưng nhanh chóng chèn. Tốt cho việc triển khai chèn/xóa rất nhiều nhưng không đọc nhiều. Nó không giữ toàn bộ mảng trong một khối bộ nhớ liên tục.

Set:

1. HashSet không đảm bảo trình tự lặp lại, và do đó là nhanh nhất của bộ. Nó có chi phí cao và chậm hơn ArrayList, vì vậy bạn không nên sử dụng nó ngoại trừ một lượng lớn dữ liệu khi tốc độ băm của nó trở thành một yếu tố.
2. TreeSet giữ dữ liệu được sắp xếp, do đó chậm hơn so với HashSet.

Bản đồ: Hiệu suất và hành vi của HashMap và TreeMap song song với triển khai Đặt.

Không thể sử dụng Vector và Hashtable. Chúng được triển khai đồng bộ hóa, trước khi phát hành phân cấp Bộ sưu tập mới, do đó chậm. Nếu cần đồng bộ hóa, hãy sử dụng Collections.synchronizedCollection().

Answer 5

Tôi thấy suy nghĩ của Bruce Eckel trong Java rất hữu ích. Ông so sánh các bộ sưu tập khác nhau rất tốt. Tôi đã sử dụng để giữ một sơ đồ ông xuất bản cho thấy người thừa kế thừa kế trên bức tường lập phương của tôi như là một tài liệu tham khảo nhanh chóng. Một điều tôi đề nghị bạn làm là ghi nhớ sự an toàn của luồng. Hiệu suất thường có nghĩa là không an toàn.

Answer 6

Để không sắp xếp lựa chọn tốt nhất, hơn chín lần trong số mười lần, sẽ là: ArrayList, HashMap, HashSet.

Vector và Hashtable được đồng bộ hóa và do đó có thể chậm hơn một chút. Thật hiếm khi bạn muốn triển khai đồng bộ hóa và khi bạn thực hiện giao diện của họ không đủ để đồng bộ hóa hữu ích. Trong trường hợp Map, ConcurrentMap bổ sung thêm các hoạt động để làm cho giao diện hữu ích. ConcurrentHashMap là một triển khai tốt của ConcurrentMap.

LinkedList gần như không bao giờ là ý tưởng hay. Ngay cả khi bạn đang làm rất nhiều chèn và loại bỏ, nếu bạn đang sử dụng một chỉ mục để chỉ ra vị trí sau đó yêu cầu lặp qua danh sách để tìm nút chính xác. ArrayList gần như luôn luôn nhanh hơn.

Đối với Bản đồ và Đặt, biến thể băm sẽ nhanh hơn cây/sắp xếp. Hash algortihms có xu hướng có O (1) hiệu suất, trong khi cây sẽ là O (log n).

Answer 7

Về mặt lý thuyết có hữu ích Big-Oh sự cân bằng, nhưng trong thực tế, điều này hầu như không bao giờ quan trọng.

Trong tiêu chuẩn thực tế, ArrayList thực hiện LinkedList ngay cả với danh sách lớn và có các hoạt động như "rất nhiều chèn gần phía trước". Các nhà nghiên cứu bỏ qua thực tế rằng các thuật toán thực sự có các yếu tố liên tục có thể áp đảo đường cong tiệm cận. Ví dụ, danh sách liên kết yêu cầu phân bổ đối tượng bổ sung cho mỗi nút, có nghĩa là chậm hơn để tạo ra một nút và các đặc tính truy cập bộ nhớ lớn hơn rất nhiều.

quy tắc của tôi là:

1. Luôn luôn bắt đầu với ArrayList và HashSet và HashMap (ví dụ: không LinkedList hoặc TreeMap).
2. Tuyên bố loại phải luôn là giao diện (ví dụ: Danh sách, Đặt, Bản đồ) để nếu xem xét hồ sơ hoặc mã chứng minh bạn có thể thay đổi việc triển khai mà không vi phạm bất kỳ điều gì.

Answer 8

Tôi thực sự thích cheat này tấm từ Sergiy Kovalchuk của blog entry:

chi tiết hơn là Alexander Zagniotov's flowchart from his site.

Answer 9

Như được đề xuất trong các câu trả lời khác, có các tình huống khác nhau để sử dụng bộ sưu tập chính xác tùy thuộc vào trường hợp sử dụng. Tôi liệt kê vài điểm,

ArrayList:

• Hầu hết các trường hợp, bạn chỉ cần lưu trữ hoặc lặp thông qua một "bó của những thứ" và sau đó lặp qua chúng. Iterating nhanh hơn như chỉ số của nó dựa.
• Bất cứ khi nào bạn tạo một ArrayList, một số tiền cố định bộ nhớ được phân bổ cho nó và một lần exceeeded, nó sao chép toàn bộ mảng

LinkedList:

• Nó sử dụng gấp đôi danh sách liên kết để chèn và thao tác xóa sẽ nhanh vì nó sẽ chỉ thêm hoặc xóa một nút.
• Truy xuất chậm vì nó sẽ phải lặp qua các nút.

HashSet:

• Làm khác có-không quyết định về một mục, ví dụ "là mục một từ tiếng Anh", "là mục trong cơ sở dữ liệu?" ", là mục trong danh mục này?" v.v.

• Ghi nhớ "những mục bạn đã xử lý", ví dụ: khi thực hiện thu thập thông tin trên web;

HashMap:

• Được sử dụng trong trường hợp bạn cần phải nói "cho một X đã cho thì Y là gì"? Nó thường hữu ích cho việc thực hiện bộ đệm trong bộ nhớ hoặc các chỉ mục i.e cặp giá trị chính Ví dụ: Đối với một ID người dùng nhất định, tên/đối tượng người dùng được lưu trong bộ nhớ cache của họ là gì ?.
• Luôn đi với HashMap để thực hiện tra cứu.

Vector và Hashtable được đồng bộ hóa và do đó hơi chậm hơn và nếu cần đồng bộ hóa, hãy sử dụng Collections.synchronizedCollection(). Kiểm tra This để biết các bộ sưu tập được sắp xếp. Hãy hy vọng điều này sẽ được thực hiện.