Cấp phát bộ nhớ trong Set (java)

[MNHBA]

Mọi người cho em hỏi cách thức cấp phát bộ nhớ của Set không?
Ví dụ như khi khởi tạo 1 hashSet/treeSet thì sẽ được cung cấp mặc định bao nhiêu bộ nhớ, và khi cung cấp đầy bộ nhớ đấy thì nó tự động thêm như thế nào?
Cũng như khi xoá 1 hay nhiều phần tử trong HashSet/TreeSet thì bộ nhớ có tự động giảm hay không ?
Em cám ơn !

[SITUVN.gcd]

Này thì bạn tìm hiểu mã nguồn mới hiểu được chứ.
Từ khóa: java Set source code. Sẽ có khác biệt giữa Open JDK và Oracle JDK (và cả Android). open jdk vs oracle jdk.

[library (La biblioteca)]

Hm. Như @SITUVN.gcd có đề cập ở trên, cách tốt nhất và dễ nhất cho cậu là đọc mã nguồn của HashSet hoặc TreeSet. Và cũng như đề cập ở trên, các phiên bản JDK khác nhau có thể sẽ có cách implement khác nhau chút (nhưng không nhiều đâu ).

@MNHBA

Mọi người cho em hỏi cách thức cấp phát bộ nhớ của Set không?

Set là interface, và cách khởi tạo và sử dụng bộ nhớ của Set sẽ phụ thuộc vào loại Set của cậu (HashSet có cách dùng bộ nhớ khác với TreeSet, vì design của 2 bên hoàn toàn khác nhau). Vậy nên, tớ không có câu trả lời chung chung cho câu hỏi của cậu được

@MNHBA

Ví dụ như khi khởi tạo 1 hashSet/treeSet thì sẽ được cung cấp mặc định bao nhiêu bộ nhớ

Cậu nên đọc source code của cả 2 để rõ hơn. Tớ sẽ giúp cậu phần HashSet, cậu làm điều tương tự với TreeSet nhé! (TreeSet sẽ dễ hơn theo ý kiến cá nhân tớ)

HashSet trong implement sử dụng HashMap ở bên trong để lưu trữ, nên câu hỏi của cậu tương đương với với câu hỏi về HashMap.
Khi khởi tạo HashMap, do bảng băm sẽ được khởi tạo khi cậu thêm phần tử đầu tiên vào, nên bộ nhớ mà HashMap chiếm không nhiều.

@MNHBA

và khi cung cấp đầy bộ nhớ đấy thì nó tự động thêm như thế nào?

Phần này sẽ dài dòng đấy.

Trước tiên, cậu cần biết cấu trúc HashMap như thế nào.
Về mặt cấu trúc, HashMap bao gồm các thành phần gọi là bucket (hay bin). Khi cậu thêm phần tử vào, phần tử đó sẽ được tính toán hash code, và phân phối các phần tử đó vào từng bucket có hash code tương ứng. Từng bucket là linked list.

Tiếp theo, tớ sẽ cho cậu biết khi nào được gọi là “bộ nhớ đầy”.
HashMap có 1 thông số gọi là capacity: kích thước của map - hay số lượng cặp key-value trong map. Kích thước này mặc định là 16 phần tử.
HashMap được coi là đầy khi số lượng phần tử nó có chiếm 75% lượng capacity. Khi điều này xảy ra:

• HashMap sẽ được tăng gấp đôi capacity (tối đa là 2^30 phần tử).
• HashMap sẽ được rehash lại.
• Với Java 8+, khi cậu có 64 phần tử trong hash map, các bucket trong hash map của cậu sẽ được chuyển thành dạng tree. Nó cũng ảnh hưởng tới bộ nhớ mà HashMap chiếm (do mỗi tree node có kích thước gấp đôi linked list node thông thường).

@MNHBA

Cũng như khi xoá 1 hay nhiều phần tử trong HashSet/TreeSet thì bộ nhớ có tự động giảm hay không ?

Khi cậu giảm số phần tử của node, kích thước của HashMap không bị thay đổi (cả 3 version JDK tớ check đều vậy).
Tuy nhiên, trong implementation node của HashMap ở Java 8+ có đề cập:

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins.

Khi convert các bucket của HashMap từ Tree sang linked list, kích thước của HashMap sẽ giảm đi, do TreeNode có kích thước lớn hơn Node thông thường. Tuy nhiên, tớ có check implementation, và không tìm thấy cài đặt theo như note trên.

Hope it helps!