Memory hiệu quả trong Java

Question

(Có một số câu hỏi về mảng thưa thớt tiết kiệm thời gian nhưng tôi đang tìm kiếm hiệu quả bộ nhớ.)

Tôi cần tương đương với một List<T> hoặc Map<Integer,T> mà

1. Có thể phát triển theo yêu cầu chỉ bằng cách đặt một khóa lớn hơn bất kỳ khóa nào trước đây. (Có thể giả sử các phím không âm).
2. Hiệu quả bộ nhớ là ArrayList<T> trong trường hợp hầu hết các chỉ mục không phải là null, tức là khi dữ liệu thực tế không quá thưa thớt.
3. Khi chỉ số thưa thớt, hãy sử dụng không gian tỷ lệ thuận với số không chỉ số null.
4. Sử dụng ít bộ nhớ hơn HashMap<Integer,T> (vì điều này sẽ tự động khóa các phím và có thể không tận dụng loại khóa vô hướng).
5. Có thể nhận hoặc đặt thành phần trong thời gian nhật ký được phân bổ (N) khi N là số mục nhập: không cần phải là thời gian tuyến tính, tìm kiếm nhị phân sẽ được chấp nhận.
6. Được thực hiện trong thư viện Java thuần túy mã nguồn mở không phải là virus (tốt nhất là ở Trung tâm Maven).

Có ai biết lớp tiện ích như vậy không?

Tôi đã mong đợi Bộ sưu tập của Commons có một bộ sưu tập nhưng dường như không có.

Tôi đã xem qua số org.apache.commons.math.util.OpenIntToFieldHashMap trông gần như đúng, ngoại trừ loại giá trị là FieldElement có vẻ không phù hợp; Tôi chỉ muốn T extends Object. Dường như nó sẽ dễ dàng để chỉnh sửa mã nguồn của nó để được chung chung hơn, mặc dù tôi thà sử dụng một phụ thuộc nhị phân nếu có sẵn.

Answer 1

Tôi sẽ thử với trove bộ sưu tập, có TIntObjectMap có thể phù hợp với mục đích của bạn.

Answer 2

Tôi đã lưu trường hợp thử nghiệm của mình là jglick/inthashmap. Kết quả:

HashMap size: 1017504 
TIntObjectMap size: 853216 
IntHashMap size: 846984 
OpenIntObjectHashMap size: 760472 

Answer 3

Tôi sẽ xem triển khai SparseArray của Android để lấy cảm hứng. Bạn có thể xem nguồn bằng cách tải xuống mã nguồn của AOSP tại đây http://source.android.com/source/downloading.html

Answer 4

Tôi sẽ đề nghị bạn sử dụng OpenIntObjectHashMap từ thư viện Colt. Link