ArrayListMultimap khác với LinkedListMultimap như thế nào?

Question

Vì vậy, tôi chỉ đọc javadoc cho ArrayListMultimap và LinkedListMultimap để hiểu cách sử dụng chúng và tôi đã biết rằng cả hai cặp khóa-giá trị trùng lặp (và theo đó tôi có nghĩa là cùng một khóa, giá trị khác nhau - nếu tôi hiểu hãy sửa tôi nếu tôi sai). Tuy nhiên, tôi không hiểu sự khác biệt giữa chúng. Cả hai đều được sử dụng để lưu trữ cặp giá trị khóa trùng lặp. Phần duy nhất mà chúng khác nhau là trong việc thực hiện của chúng, tức là ArrayListMultimap được triển khai dưới dạng một mảng và LinkedListMultimap được triển khai dưới dạng một LinkedList? Ngoài ra, chúng khác nhau về hiệu suất như thế nào? Tôi biết tôi đang yêu cầu rất nhiều nhưng tôi không thực sự biết nơi khác để tìm câu trả lời cho điều này.

Answer 1

Đó là trong tài liệu ... và trong mã. Về cơ bản bên cạnh một sự khác biệt mà bạn đã thấy (List lựa chọn triển khai), họ cũng sử dụng triển khai Map khác nhau. Vì vậy:

• ArrayListMultimap sử dụng HashMap cho bản đồ và ArrayList bộ sưu tập cor, có nghĩa là trật tự lặp của các phương pháp như entries(), asMap().keySet() hoặc asMap.entrySet() là undefined. Việc triển khai đơn giản và đơn giản là ListMultimap và bạn nên bắt đầu với điều này.

• LinkedListMultimap sử dụng LinkedList cho việc thu thập và cấu trúc dữ liệu chuyên ngành (danh sách tùy chỉnh liên kết) để duy trì lặp thứ tự của phương pháp nêu trên:

  thứ tự được duy trì sử dụng một danh sách liên kết có chứa tất cả các giá trị khóa cặp. Ngoài ra, một loạt các danh sách liên kết rời nhau của "anh chị em", mỗi giá trị chứa các giá trị cho một khóa cụ thể, được sử dụng để triển khai ValueForKeyIterator trong thời gian không đổi.

  Thêm vào đó nó sử dụng ít các cấu trúc khác để duy trì "danh sách liên kết" hành vi -like:

  private transient Node<K, V> head; // the head for all keys 
  private transient Node<K, V> tail; // the tail for all keys 
  private transient Multiset<K> keyCount; // the number of values for each key 
  private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key 
  private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key 
  

Ngoài ra, bộ nhớ là một ý nghĩa của các bộ sưu tập ủng hộ sử dụng trong các Multimap triển khai - see this comparision (có thể không được cập nhật 100%).

---

Cá nhân, khi tôi cần hiệu quả, có thể thay đổi ListMultimap với trật tự lặp xác định phím, tôi sử dụng "tùy chỉnh" ListMultimap (tạo ra với MultimapBuilder, mà là ở ổi từ v16.0):

ListMultimap<String, Integer> treeListMultimap = 
    MultimapBuilder.linkedHashKeys().arrayListValues().build(); 

---

Trước v16.0 tạo tùy chỉnh Multimap s là tiết hơn (sử dụng Multimaps.newListMultimap):

/** 
* Creates {@link ListMultimap} preserving insertion order of keys and values 
* (it's backed by {@link LinkedHashMap} and {@link ArrayList}). 
*/ 
public static <K, V> ListMultimap<K, V> newLinkedArrayListMultimap() { 
    return Multimaps.newListMultimap(
     Maps.<K, Collection<V>>newLinkedHashMap(), 
     new Supplier<List<V>>() { 
      @Override 
      public List<V> get() { 
      return Lists.newArrayList(); 
      } 
     }); 
}