là HashMaps với công suất được xác định trước nhanh hơn

Question

Tôi đã xem qua một thuật toán trên mạng http://www.coderanch.com/t/201836/Performance/java/Hashtable-vs-Hashmap và quyết định thử nghiệm nó

public class MapTest{ 
    static int sizeOfTrial = 100000; 
    static String[] keys = new String[sizeOfTrial]; 
    static String[] vals = new String[sizeOfTrial]; 

    public static void main(String[] args) { 
     //init sizeOfTrial key/value pairs 
     for (int i=0; i < sizeOfTrial; i++){ 
      String s1 = "key"+ i; 
      String s2 = "val"+ i; 
      keys[i] = s1; 
      vals[i] = s2; 
     } 
     test(new TreeMap(), "TreeMap"); 
     test(new Hashtable(), "Hashtable"); 
     test(new HashMap(), "HashMap"); 
     test(new Hashtable(200000), "Hashtable presized"); 
     test(new HashMap(200000), "HashMap presized"); 
    } 

    public static void test(Map tm, String name){ 
    long t1 = System.currentTimeMillis(); 
    for (int i=0; i < sizeOfTrial; i++){ 
     tm.put(keys[i],vals[i]); 
    } 
    for (int i=0; i < sizeOfTrial; i++){ 
     tm.get(keys[i]); 
    } 
    long t2 = System.currentTimeMillis(); 
    System.out.println("total time for " + name + ": " + (t2-t1)); 
    } 
} 

và tôi đã nhận kết quả như sau

total time for TreeMap: 1744 
total time for Hashtable: 446 
total time for HashMap: 234 
total time for Hashtable presized: 209 
total time for HashMap presized: 196 

là JVM này phụ thuộc và độc đoán hay nó thực sự cung cấp thời gian truy cập và lưu trữ nhanh hơn?

Answer 1

Xác định trước kích thước mong đợi của bất kỳ loại loại vùng chứa nào sẽ cung cấp thời gian lưu trữ nhanh hơn đơn giản vì bộ nhớ không phải được phân bổ lại động trong thời gian chạy thường xuyên. Thông thường, lưu trữ sao lưu là một số loại mảng, và khi bạn vượt quá khả năng có sẵn, mảng phải được sao chép vào một mảng lớn hơn mới. Đây là một hoạt động tốn kém có thể phải xảy ra nhiều lần nếu bạn lưu trữ một số lượng lớn các đối tượng vào một container bắt đầu với dung lượng rất nhỏ.

Hiệu suất đọc từ bản đồ cũng không bị ảnh hưởng. Bạn có thể chứng minh điều này tốt hơn bằng cách đặt riêng phần tm.put từ phần tm.get.

---

Sửa: Để minh họa điểm này hơn nữa, tôi sửa đổi mã để thời gian tm.put tách biệt khỏi tm.get. Sau đây là các kết quả trên máy tính của tôi:

total time for TreeMap tm.put: 159 
total time for TreeMap tm.get: 74 
total time for Hashtable tm.put: 20 
total time for Hashtable tm.get: 10 
total time for HashMap tm.put: 42 
total time for HashMap tm.get: 5 
total time for Hashtable presized tm.put: 11 
total time for Hashtable presized tm.get: 9 
total time for HashMap presized tm.put: 6 
total time for HashMap presized tm.get: 4 

Chú ý rằng sự khác biệt giữa Hashtable thường xuyên và presized cho tm.put là một yếu tố của ~ 2. Tương tự, với HashMap sự khác biệt giữa thông thường và được đặt trước là hệ số của ~ 7 để lưu trữ. Tuy nhiên, nhìn vào phía bên đọc, cả Hashtable và Hashmap có khoảng timings tương tự cho tm.get trong cả hai trường hợp (10 ms vs 9 ms cho Hashtable, và 5 ms vs 4 ms cho HashMap). Cũng lưu ý rằng trong trường hợp đã được định trước, cả việc đặt và nhận lấy khoảng một lượng thời gian tương đương.