Hiệu suất HashMap vs LinkedHashMap lặp lại qua các giá trị()

Question

Có sự khác biệt hiệu suất giữa HashMap và LinkedHashMap cho truyền tải qua chức năng values() không?

Answer 1

Tôi nghĩ rằng LinkedHashMap phải là nhanh hơn trong traversal do nextEntry thực hiện vượt trội trong nó Iterator

Đây là lý do tại sao:

Chúng ta hãy đi từng bước từ việc thực hiện values.
Việc thực hiện HashMap của values là thế này:

public Collection<V> values() { 
     Collection<V> vs = values; 
     return (vs != null ? vs : (values = new Values())); 
    } 

Các LinkedHashMap kéo dài từ HashMap và thừa hưởng việc thực hiện tương tự.

Sự khác biệt là trong việc thực hiện Iterator cho số Values trong cả hai.

cho HashMap nó kéo dài từ java.util.HashMap.HashIterator

private final class ValueIterator extends HashIterator<V> { 
     public V next() { 
      return nextEntry().value; 
     } 
    } 

nhưng đối với LinkedHashMap nó kéo dài từ java.util.LinkedHashMap.LinkedHashIterator

private class ValueIterator extends LinkedHashIterator<V> { 
     public V next() { return nextEntry().value; } 
    } 

nên chênh lệch về cơ bản nắm để nextEntry thực hiện.

Đối LinkedHashMap nó chỉ là gọi e.after trong đó e là Entry, nhưng đối với HashMap có một số công việc liên quan đến việc đi qua các mảng Entry[] để tìm ra tiếp theo sau.

CẬP NHẬT: Mã cho nextEntry() trong HashMap

final Entry<K,V> nextEntry() { 
      if (modCount != expectedModCount) 
       throw new ConcurrentModificationException(); 
      Entry<K,V> e = next; 
      if (e == null) 
       throw new NoSuchElementException(); 

      if ((next = e.next) == null) { 
       Entry[] t = table; 
       while (index < t.length && (next = t[index++]) == null) 
        ; 
      } 
      current = e; 
      return e; 
     } 

Bản đăng ký cuối [] không phải là một cửa hàng liền kề. (Có thể có giá trị null ở giữa). Nếu bạn nhìn vào đoạn mã trên, những gì nó làm là trỏ tới hiện tại và tìm tiếp theo, bằng cách lặp qua mục [].

Nhưng Tôi nghĩ rằng hiệu suất tăng này sẽ đến với chi phí chèn.Kiểm tra phương pháp addEntry trong cả hai lớp như một bài tập.

Answer 2

Lời khuyên tốt nhất là "Đừng ngại thử nó" nhưng tôi khá chắc rằng chúng rất giống nhau. Getter cho tập hợp giá trị là O (1) và như vậy là mỗi bước lặp. Lặp lại thông qua một danh sách liên kết là tầm thường như lặp qua các băm băm, với một cạnh nhỏ có thể có trong favpr của danh sách liên kết.

Answer 3

Nó gần như không quan trọng. Câu hỏi đặt ra là: bạn cần gì. Nếu thứ tự của các yếu tố có liên quan, bạn phải sử dụng LinkedHashMap. Nếu không, bạn chỉ cần không cần nó, vì vậy hãy sử dụng HashMap.

Answer 4

Tôi đã thử trong một UnitTest, giá trị được lặp lại() 10000 lần, mili giây: 806 so với 902. Nó gần như giống nhau.

Answer 5

Vâng, sẽ có sự khác biệt hiệu năng giống như bạn nhận được trong tất cả các lần lặp trên HashMap so LinkedHashMap: HashMap sẽ mất thời gian tỉ lệ với số lượng các mục cộng với kích thước của bảng băm, và LinkedHashMap sẽ chỉ mất thời gian tỉ lệ với số lượng mục nhập.

Answer 6

Tôi đã viết một chương trình lược tả nhỏ tạo 1 triệu khóa (Số nguyên) so với Boolean.TRUE, lặp lại 100 lần. Đã tìm thấy các mục sau:

HashMap:- 
Create: 3.7sec 
Iterate: 1.1sec 
Access: 1.5sec 
Total: 6.2sec 

LinkedHashMap:- 
Create: 4.7sec (30% slower) 
Iterate: 0.5sec (50% faster) 
Access: 0.8sec (50% faster) 
Total : 6.0sec 

Thu gom rác không được thực hiện để gây ô nhiễm số lượng, tuy nhiên tôi nghĩ LinkedHashMap có cạnh trên HashMap và tôi sẽ sử dụng nó trong mã sau này.