Triển khai Bộ sưu tập Java (ví dụ: HashMaps vs HashSet vs HashTable ...), chi phí của việc chọn sai là gì?

Question

Trong mã của tôi, tôi mặc định sử dụng ArrayList cho tất cả các Danh sách, HashMap cho tất cả các bản đồ, HashSet cho tất cả các bộ.

Từ quan điểm thực tế, tôi mất đi tính linh hoạt, khả năng mở rộng, khả năng đọc và hiệu suất bằng cách chọn triển khai sai? Khi nào nó có ý nghĩa để dành thời gian để quyết định sử dụng cái này chứ không phải cái khác?

Tôi chắc chắn sẽ thấy một trường hợp cắt rất rõ ràng vì sao một người nào đó sẽ sử dụng LinkedList thay vì một ArrayList trong một số trường hợp nhất định. Khi nào một người nào đó cảm thấy rằng nó là rất quan trọng họ sử dụng một HashMap chứ không phải là một TreeMap hoặc một HashTable? Điều gì về Sets?

Câu hỏi:

1. chi phí của việc lựa chọn kém là bao nhiêu?
2. Có ai có câu chuyện về thảm họa về việc chọn triển khai sai và trung tâm dữ liệu bắt lửa không?
3. Bất kỳ quy tắc ngón tay cái nào tốt?
4. Có bất kỳ triển khai bộ sưu tập tối nghĩa nào mà bạn không thể sống mà không có không?

Tôi đã đọc qua:

• http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeMap.html
• http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html
• Java: ArrayList for List, HashMap for Map, and HashSet for Set? vv ...

tôi thấy this câu hỏi có liên quan từ một quan điểm lý thuyết của xem, nhưng tôi quan tâm nhiều hơn đến một thế giới thực, trong phần renches trả lời.

Answer 1

Đây là một câu hỏi rất chung chung, nhưng tôi sẽ ném vào một vài vấn đề khó khăn.

Nếu bạn đang lập trình hướng đến giao diện, thì tính linh hoạt sẽ không ảnh hưởng lớn. Ví dụ

void foo(List<E> list); 

Chi phí của việc lựa chọn kém có thể được nhìn thấy trong hình phạt hiệu suất. Ví dụ, chọn một LinkedList khi truy cập trực tiếp (như trong ArrayList) là những gì bạn đang tìm kiếm.

Bộ có vấn đề tương tự. Nếu bạn muốn giữ các bộ sưu tập được sắp xếp mà không có bản sao, một SortedSet sẽ là một sự lựa chọn khôn ngoan hơn một HashSet. Trong một sau, you'd phải sắp xếp toàn bộ Set bằng tay (điều này là, một lời kêu gọi Collections.sort())

<EDIT>

Đối với maps, có rất nhiều hiện thực khác nhau . Mỗi người có một mục đích khác nhau. Ví dụ: có SortedMap, tương tự với SortedSet. Sau đó, có WeakHashMap, không hoạt động giống như HashMap, theo nghĩa là các khóa có thể được xóa bởi bộ thu gom rác. Như bạn có thể hình dung, sự lựa chọn giữa HashMap và WeakHashMap không phải là tầm thường. Như mọi khi, phụ thuộc vào những gì bạn muốn thực hiện với họ.

</EDIT>

Về những câu chuyện, trong dự án hiện tại của tôi, chúng tôi thay thế một HashSet với một SortedSet vì hiệu suất bị ảnh hưởng. DataCenter đã không bắt lửa mặc dù.

Hai xu của tôi.

Answer 2

Vì vậy, miễn là bạn tuân theo thực hành OO tốt của tùy thuộc vào loại trừu tượng, điều gì quan trọng?

Nếu bạn thấy mình đã sử dụng sai Map bạn chỉ cần thay đổi triển khai bạn đang sử dụng và bởi vì tất cả phụ thuộc của bạn là trên Map mọi thứ hoạt động như trước đây chỉ với các đặc tính hiệu suất khác nhau.

Answer 3

Tôi nghĩ bạn nên sử dụng HashMap, HashSet và ArrayList làm triển khai chính của mình. Khi bạn cần một bộ sắp xếp, bạn nên biết rằng TreeSet có sẵn; khi bạn đang thực hiện các kiểu đệ quy, tương tự, thật tuyệt khi có LinkedList trong túi sau của bạn. Nhưng chương trình để giao diện và sau đó bạn có thể trao đổi các triển khai thực hiện khi cần thiết. Và nếu cùng một bộ sưu tập cần xử lý như (ví dụ) cả một LinkedList và một ArrayList, sẽ không có vấn đề gì lớn khi xây dựng một cái từ cái kia.

Làm việc với các triển khai mặc định mà bạn đã liệt kê. Khi có các vấn đề về hiệu suất, và có lý do để tin rằng một triển khai thay thế sẽ tốt hơn, trao đổi nó - và đo sự khác biệt. Khi bạn cần hành vi đặc biệt (ví dụ như các bộ sắp xếp), hãy sử dụng các lớp đặc biệt.

Cách tiếp cận này chưa đốt cháy tôi.