Kích thước tối đa của HashSet, Vector, LinkedList

Question

Kích thước tối đa là HashSet, Vector, LinkedList là gì? Tôi biết rằng ArrayList có thể lưu trữ hơn 3277000 số.

Tuy nhiên, kích thước của danh sách phụ thuộc vào kích thước bộ nhớ (heap). Nếu nó đạt đến mức tối đa, JDK sẽ ném một số OutOfMemoryError.

Nhưng tôi không biết giới hạn số lượng phần tử trong HashSet, Vector và LinkedList.

Answer 1

Không có kích thước tối đa nào được chỉ định cho các cấu trúc này.

Giới hạn kích thước thực tế thực tế có thể ở đâu đó trong vùng Integer.MAX_VALUE (tức là 2147483647, khoảng 2 tỷ phần tử), vì đó là kích thước tối đa của một mảng trong Java.

• Một HashSet sử dụng một HashMap nội bộ, vì vậy nó có kích thước tối đa giống như
  • Một HashMap sử dụng một mảng mà luôn luôn có một kích thước đó là một sức mạnh của hai, vì vậy nó có thể được tối đa là 2 = 1073741824 phần tử lớn (vì lũy thừa kế tiếp của hai số lớn hơn Integer.MAX_VALUE).
  • Thông thường, số lượng phần tử nhiều nhất là số lượng nhân với hệ số tải (0,75 theo mặc định). Tuy nhiên, khi HashMap ngừng thay đổi kích thước, thì vẫn còn cho phép bạn thêm các yếu tố, khai thác thực tế là mỗi nhóm được quản lý qua danh sách được liên kết. Do đó, giới hạn duy nhất cho các phần tử trong một số HashMap/HashSet là bộ nhớ.
• Một Vector sử dụng một mảng nội bộ trong đó có một kích thước tối đa của chính xác Integer.MAX_VALUE, vì vậy nó không thể hỗ trợ nhiều hơn thế nhiều yếu tố
• Một LinkedListkhông sử dụng một mảng như việc lưu trữ cơ bản, để không giới hạn kích thước. Nó sử dụng cấu trúc danh sách được liên kết kép cổ điển không có giới hạn cố hữu, do đó, kích thước của nó là chỉ bị giới hạn bởi bộ nhớ khả dụng. Lưu ý rằng LinkedList sẽ báo cáo kích thước sai nếu nó lớn hơn Integer.MAX_VALUE, vì nó sử dụng trường int để lưu trữ kích thước và loại trả lại là size() cũng là int.

Lưu ý rằng trong khi Collection API không xác định cách một Collection với hơn Integer.MAX_VALUE yếu tố nên cư xử. Quan trọng nhất là trạng thái này là the size() documentation:

Nếu bộ sưu tập này chứa nhiều hơn Integer.MAX_VALUE.

Lưu ý rằng trong khi HashMap, HashSet và LinkedListvẻ để hỗ trợ nhiều hơn Integer.MAX_VALUE yếu tố, none của những thực hiện phương pháp size() theo cách này (ví dụ: họ chỉ đơn giản là để cho tràn size lĩnh vực nội bộ).

Điều này khiến tôi tin rằng các hoạt động khác cũng không được xác định rõ trong điều kiện này.

Vì vậy, tôi muốn nói đó là an toàn sử dụng những bộ sưu tập có mục đích chung với lên đếnInteger.MAX_VLAUE yếu tố. Nếu bạn biết mà bạn sẽ cần phải lưu trữ nhiều hơn thế, thì bạn nên chuyển sang triển khai bộ sưu tập chuyên dụng thực sự hỗ trợ việc này.

Answer 2

Kích thước tối đa phụ thuộc vào cài đặt bộ nhớ của JVM và tất nhiên bộ nhớ hệ thống có sẵn. Kích thước tiêu thụ bộ nhớ cụ thể cho mỗi mục nhập danh sách cũng khác nhau giữa các nền tảng, do đó, cách dễ nhất có thể là chạy thử nghiệm đơn giản.

Answer 3

Trong mọi trường hợp, bạn có thể bị giới hạn bởi kích thước heap JVM thay vì bất kỳ thứ gì khác. Cuối cùng bạn sẽ luôn nhận được các mảng vì vậy tôi rất nghi ngờ rằng bất kỳ người trong số họ sẽ quản lý nhiều hơn 2 - 1 yếu tố, nhưng bạn rất, rất có khả năng chạy ra khỏi đống trước đó anyway.

Answer 4

Phụ thuộc rất nhiều vào chi tiết triển khai.

Một HashSet sử dụng một mảng làm cửa hàng cơ bản theo mặc định nó cố gắng phát triển khi bộ sưu tập đủ 75%. Điều này có nghĩa là nó sẽ thất bại nếu bạn cố gắng thêm nhiều hơn 750.000.000 mục. (Nó không thể phát triển mảng từ 2^30 đến 2^31 mục)

Tăng hệ số tải làm tăng kích thước tối đa của bộ sưu tập. ví dụ. hệ số tải 10 cho phép 10 tỷ phần tử. (Cần lưu ý rằng HashSet tương đối kém hiệu quả trong 100 triệu phần tử khi phân phối mã băm 32 bit bắt đầu trông ít ngẫu nhiên hơn và số va chạm tăng)

Vector gấp đôi dung lượng và bắt đầu ở mức 10. Điều này có nghĩa là nó sẽ không thể tăng trên mức xấp xỉ 1,34 tỷ. Thay đổi kích thước ban đầu thành 2^n-1 sẽ cho bạn nhiều đầu hơn.

BTW: Sử dụng ArrayList thay vì Vector nếu bạn có thể.

Danh sách liên kết không có giới hạn kế thừa và có thể vượt quá 2,1 tỷ. Tại thời điểm này kích thước() có thể trả về Integer.MAX_VALUE, tuy nhiên một số chức năng như toArray sẽ thất bại vì nó không thể đặt tất cả các đối tượng vào một mảng, thay vào đó sẽ cung cấp cho bạn Integer.MAX_VALUE đầu tiên thay vì ném một ngoại lệ.

Khi @Joachim Sauer lưu ý, OpenJDK hiện tại có thể trả lại kết quả không chính xác cho các kích thước trên Integer.MAX_VALUE. ví dụ. nó có thể là một số âm.

Answer 5

Như đã nêu trong các câu trả lời khác, mảng không thể đạt được 2^31 mục nhập. Các loại dữ liệu khác bị hạn chế hoặc bằng cách này hoặc chúng có khả năng sẽ báo cáo sai kích thước của chúng() cuối cùng. Tuy nhiên, các giới hạn lý thuyết này không thể đạt được trên một số hệ thống:

Trên hệ thống 32 bit, số byte có sẵn không bao giờ vượt quá 2^32 chính xác. Và đó là giả định rằng bạn không có hệ điều hành nào chiếm bộ nhớ.Một con trỏ 32 bit là 4 byte. Bất kỳ thứ gì không dựa vào mảng phải bao gồm ít nhất một con trỏ cho mỗi mục nhập: điều này có nghĩa là số lượng mục nhập tối đa là 2^32/4 hoặc 2^30 cho những thứ không sử dụng mảng.

Một mảng đồng bằng có thể đạt được giới hạn lý thuyết của nó, nhưng chỉ một mảng byte, một mảng ngắn có chiều dài 2^31-1 sẽ sử dụng hết khoảng 2^32 + 38 byte.

Một số máy ảo Java đã giới thiệu một mô hình bộ nhớ mới sử dụng con trỏ được nén. Bằng cách điều chỉnh sự liên kết của con trỏ, hơi nhiều hơn 2^32 byte có thể được tham chiếu với 32 con trỏ byte. Khoảng bốn lần nữa. Điều này là đủ để làm cho một kích thước LinkedList() trở thành tiêu cực, nhưng không đủ để cho phép nó quấn quanh không.

Hệ thống sáu mươi bốn bit có sáu mươi bốn bit con trỏ, làm cho tất cả các con trỏ trở nên lớn gấp hai lần, làm cho các mảng không phải mảng trở nên mập mờ hơn. Điều này cũng có nghĩa là công suất tối đa được hỗ trợ nhảy tới 2^64 byte chính xác. Điều này là đủ cho một mảng 2D để đạt được tối đa lý thuyết của nó. byte [0x7fffffff] [0x7fffffff] sử dụng bộ nhớ xấp xỉ bằng 40 + 40 * (2^31-1) + (2^31-1) (2^31-1) = 40 + 40 (2^31-1) + (2^62-2^32 + 1)