Khi coding với Java/Kotlin, chúng ta thường rất hay phải thao tác với các sub class của List điển hình là ArrayList. Nó thông dụng đến mức làm chúng ta đôi khi quên đi kiểu dữ liệu mảng (Array) – Cấu trúc dữ liệu quy định các phần tử phải có cùng kiểu và kích thước cố định không thể thay đổi.
Vậy tại sao ArrayList có thể add/remove phần tử rất tiện lợi như thế ? Hãy cùng nhau tìm hiểu nhé.
Nhảy vào source code Java, dễ dàng thấy được ArrayList chỉ là một ‘tờ giấy gói xôi’ =)) Bên trong nó sử dụng một mảng object để chứa data:
transient Object[] elementData; // non-private to simplify nested class access
Và cũng vì Object là kiểu dữ liệu lớn nhất trong Java (Mọi người hay gọi vui là Father Of Big – Bố của to) nên List cho phép chúng ta có thể generics để hold kiểu dữ liệu bất kì.
Có một số khái niệm cần làm rõ trước khi bắt đầu:
- Capacity: Sức chứa của mảng là số lượng phần tử tối đa mà mảng
elementDatacó thể chứa. - Length: Số lượng phần tử thực tế đã được add vào mảng. Và như vậy thì length <= capacity.
Bây giờ chúng ta sẽ đi qua các step hoạt động của hàm add() nhé:
1 2 3 4 5 6 | <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token function">ensureCapacityInternal</span><span class="token punctuation">(</span>size <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// Increments modCount!!</span> elementData<span class="token punctuation">[</span>size<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> e<span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Thật sự rất đơn giản, chỉ cần đảm bảo mảng elementData có đủ không gian và sau đó chèn phần tử mới vào cuối mảng là xong.
Tuy nhiên ta sẽ tìm hiểu hàm ensureCapacityInternal(), đây là hàm đảm bảo việc request thêm không gian để có thể chứa thêm phần tử mới được add vào.
Mặc định, mảng sẽ được khởi tạo với không gian đủ để chứa 10 phần tử, nếu như không gian chứa đã hết thì hàm grow() sẽ được gọi.
Hàm grow() phụ trách 2 việc:
- Tăng kích thước của mảng elementData.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | <span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">grow</span><span class="token punctuation">(</span><span class="token keyword">int</span> minCapacity<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// overflow-conscious code</span> <span class="token keyword">int</span> oldCapacity <span class="token operator">=</span> elementData<span class="token punctuation">.</span>length<span class="token punctuation">;</span> <span class="token keyword">int</span> newCapacity <span class="token operator">=</span> oldCapacity <span class="token operator">+</span> <span class="token punctuation">(</span>oldCapacity <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>newCapacity <span class="token operator">-</span> minCapacity <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span> newCapacity <span class="token operator">=</span> minCapacity<span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>newCapacity <span class="token operator">-</span> MAX_ARRAY_SIZE <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">)</span> newCapacity <span class="token operator">=</span> <span class="token function">hugeCapacity</span><span class="token punctuation">(</span>minCapacity<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// minCapacity is usually close to size, so this is a win:</span> elementData <span class="token operator">=</span> <span class="token class-name">Arrays</span><span class="token punctuation">.</span><span class="token function">copyOf</span><span class="token punctuation">(</span>elementData<span class="token punctuation">,</span> newCapacity<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> ``` <span class="token class-name">Logic</span> tại đây khá rõ ràng<span class="token punctuation">,</span> số lượng phần tử của mảng mới<span class="token operator">:</span> <span class="token operator">-</span> <span class="token class-name">M</span>ặc định gán<span class="token operator">:</span> newCapacity <span class="token operator">=</span> <span class="token number">1.5</span> <span class="token operator">*</span> length hiện tại của mảng<span class="token punctuation">.</span> ``` <span class="token keyword">int</span> newCapacity <span class="token operator">=</span> oldCapacity <span class="token operator">+</span> <span class="token punctuation">(</span>oldCapacity <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>``` <span class="token class-name">Ph</span>ép dịch bit sang phải <span class="token number">1</span> bit là phép chia cho <span class="token number">2.</span> <span class="token operator">=</span><span class="token operator">></span> oldCapacity <span class="token operator">+</span> <span class="token punctuation">(</span>oldCapacity <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token number">1.5</span> <span class="token operator">*</span> oldCapacity<span class="token punctuation">;</span> <span class="token operator">-</span> <span class="token class-name">N</span>ếu newCapacity vẫn nhỏ hơn số lượng mong muốn minCapacity thì sẽ gán luôn newCapacity <span class="token operator">=</span> minCapacity <span class="token operator">-</span> <span class="token class-name">N</span>ếu như minCapacity <span class="token operator"><=</span> <span class="token class-name">Integer</span><span class="token punctuation">.</span>MAX_VALUE <span class="token operator">-</span> <span class="token number">8</span> thì sẽ gán minCapacity <span class="token operator">=</span> <span class="token class-name">Integer</span><span class="token punctuation">.</span>MAX_VALUE <span class="token operator">-</span> <span class="token number">8</span> <span class="token operator">-</span> <span class="token class-name">N</span>ếu như minCapacity <span class="token operator">></span> <span class="token class-name">Integer</span><span class="token punctuation">.</span>MAX_VALUE <span class="token operator">-</span> <span class="token number">8</span> thì sẽ gán minCapacity <span class="token operator">=</span> <span class="token class-name">Integer</span><span class="token punctuation">.</span>MAX_VALUE luôn cho vừa lòng hả dạ <span class="token operator">=</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token class-name">Nh</span>ư vậy thì số lượng phần tử tối đa mà một <span class="token class-name">ArrayList</span> có thể chứa chính là <span class="token class-name">Integer</span><span class="token punctuation">.</span>MAX_VALUE <span class="token operator">=</span> <span class="token number">2147483647</span><span class="token punctuation">;</span> <span class="token number">2.</span> <span class="token class-name">Copy</span> các phần tử của mảng hiện tại sang mảng mớ<span class="token class-name"><span class="token namespace">i<span class="token punctuation">.</span></span> V</span>ì mảng có tính chất là không thể thay đổi số lượng phần tử<span class="token punctuation">,</span> vậy nên việc tăng kích cỡ cho mảng đồng nghĩa với việc tạo một mảng mới có nhiều phần tử hơn sau đó mang các giá trị của mảng hiện tại <span class="token class-name"><span class="token namespace">sang<span class="token punctuation">.</span></span> V</span>ậy <span class="token class-name">Oracle</span> sử dụng vòng lặp trên <span class="token class-name">Java</span> để thực hiện việc này <span class="token operator">?</span> <span class="token class-name">T</span>ất nhiên là không được<span class="token punctuation">,</span> không ty đầu hàng công nghệ không thể làm theo cách dễ dàng như vậy đượ<span class="token class-name"><span class="token namespace">c<span class="token punctuation">.</span></span> Vi</span>ệc copy element của mảng cũ sang mảng mới được thực hiện thông qua hàm <span class="token class-name">Arrays</span><span class="token punctuation">.</span><span class="token function">copyOf</span><span class="token punctuation">(</span><span class="token punctuation">)</span> ```java <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token generics"><span class="token punctuation"><</span><span class="token class-name">T</span><span class="token punctuation">,</span><span class="token class-name">U</span><span class="token punctuation">></span></span> <span class="token class-name">T</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token function">copyOf</span><span class="token punctuation">(</span><span class="token class-name">U</span><span class="token punctuation">[</span><span class="token punctuation">]</span> original<span class="token punctuation">,</span> <span class="token keyword">int</span> newLength<span class="token punctuation">,</span> <span class="token class-name">Class</span><span class="token operator"><</span><span class="token operator">?</span> <span class="token keyword">extends</span> <span class="token class-name">T</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token operator">></span> newType<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token annotation punctuation">@SuppressWarnings</span><span class="token punctuation">(</span><span class="token string">"unchecked"</span><span class="token punctuation">)</span> <span class="token class-name">T</span><span class="token punctuation">[</span><span class="token punctuation">]</span> copy <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token class-name">Object</span><span class="token punctuation">)</span>newType <span class="token operator">==</span> <span class="token punctuation">(</span><span class="token class-name">Object</span><span class="token punctuation">)</span><span class="token class-name">Object</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token keyword">class</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token punctuation">(</span><span class="token class-name">T</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">new</span> <span class="token class-name">Object</span><span class="token punctuation">[</span>newLength<span class="token punctuation">]</span> <span class="token operator">:</span> <span class="token punctuation">(</span><span class="token class-name">T</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token class-name">Array</span><span class="token punctuation">.</span><span class="token function">newInstance</span><span class="token punctuation">(</span>newType<span class="token punctuation">.</span><span class="token function">getComponentType</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> newLength<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token class-name">System</span><span class="token punctuation">.</span><span class="token function">arraycopy</span><span class="token punctuation">(</span>original<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> copy<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token class-name">Math</span><span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>original<span class="token punctuation">.</span>length<span class="token punctuation">,</span> newLength<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> copy<span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Tiếp theo copyOf() sẽ call đến System.arraycopy() để thực hiện copy các phần tử từ mảng original từ vị trí bắt đầu là 0 sang mảng copy với số lượng là newLength = newCapacity vừa tính toán được ở bước trước.
1 2 3 4 | <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">native</span> <span class="token keyword">void</span> <span class="token function">arraycopy</span><span class="token punctuation">(</span><span class="token class-name">Object</span> src<span class="token punctuation">,</span> <span class="token keyword">int</span> srcPos<span class="token punctuation">,</span> <span class="token class-name">Object</span> dest<span class="token punctuation">,</span> <span class="token keyword">int</span> destPos<span class="token punctuation">,</span> <span class="token keyword">int</span> length<span class="token punctuation">)</span><span class="token punctuation">;</span> |
Đến đây ta thấy rằng System.arraycopy là một native method được viết bằng C++, nó thực hiện việc copy các phần tử của mảng nguồn src sang mảng đích dest
System.arraycopy() được sử dụng rất rất nhiều vậy nên nó được tối ưu bộ nhớ và cung cấp thông qua hàm memmove() Bionic Libc. Nếu như platform có sẵn thì nó sẽ được sử dụng, nếu không thì Dalvik_java_lang_System_arraycopy sẽ được sử dụng thay thế.
Hoá ra những thứ mà chúng ta vẫn thường sử dụng bấy lâu nay được xây dựng vô cùng phức tạp và công phu, abstract dưới nhiều tầng mà phải đào sâu tìm hiểu rất kĩ mới có thể hiểu được.