Java中數(shù)組容器(ArrayList)設(shè)的計與實現(xiàn)
更新時間：2022年07月07日 09:02:48 作者：一無是處的研究僧
本篇文章主要跟大家介紹我們最常使用的一種容器ArrayList、Vector的原理，并且自己使用Java實現(xiàn)自己的數(shù)組容器MyArrayList，讓自己寫的容器能像ArrayList那樣工作,感興趣的可以了解一下
本篇文章主要跟大家介紹我們最常使用的一種容器ArrayList、Vector的原理，并且自己使用Java實現(xiàn)自己的數(shù)組容器MyArrayList，讓自己寫的容器能像ArrayList那樣工作。在本篇文章當(dāng)中首先介紹ArrayList的一些基本功能，然后去分析我們自己的容器MyArrayList應(yīng)該如何進(jìn)行設(shè)計，同時分析我們自己的具體實現(xiàn)方法，最后進(jìn)行代碼介紹?。。?/p>
ArrayList為我們提供了哪些功能
我們來看一個簡單的代碼，隨機(jī)生成100個隨機(jī)數(shù)，查看生成隨機(jī)數(shù)當(dāng)中是否存在50這個數(shù)。
public class MyArrayList {
public static void main(String[] args) {
Random random = new Random();
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
list.add(random.nextInt(5000));
}
for (int i = 0; i < 100; i++) {
if (list.get(i) == 50) {
System.out.println("包含數(shù)據(jù) 50");
}
}
list.set(5, 1000);// 設(shè)置下標(biāo)為5的數(shù)據(jù)為100
list.remove(5);// 刪除下標(biāo)為5的數(shù)據(jù)
list.remove(new Integer(888));// 刪除容器當(dāng)中的第一個值為5的數(shù)據(jù)
}
}上述代碼包含了ArrayList最基本的一個功能，一個是add方法，向數(shù)組容器當(dāng)中加入數(shù)據(jù)，另外一個方法是get從容器當(dāng)中拿出數(shù)據(jù)，set方法改變?nèi)萜骼锏臄?shù)據(jù)，remove方法刪除容器當(dāng)中的數(shù)據(jù)。ArrayList的很多其他的方法都是圍繞這四個最基本的方法展開的，因此我們在這里不仔細(xì)介紹其他的方法了，后面我們自己實現(xiàn)的時候遇到問題的時候自然會需要設(shè)計相應(yīng)的方法，然后我們進(jìn)行解決即可。
現(xiàn)在我們就需要去設(shè)計一個數(shù)組容器實現(xiàn)“增刪改查”這四個基本功能。
設(shè)計原理分析
首先明白一點我們需要使用什么工具去實現(xiàn)這樣一個容器。我們手里有的工具就是Java提供給我們的最基本的功能——數(shù)組（這個好像是廢話，我們的標(biāo)題就是數(shù)組容器??）。
當(dāng)我們在Java當(dāng)中使用數(shù)組去存儲數(shù)據(jù)時，數(shù)據(jù)在Java當(dāng)中的內(nèi)存布局大致如下圖所示。
我們在設(shè)計數(shù)組容器這樣一個數(shù)據(jù)結(jié)構(gòu)的時候主要會遇到兩個問題：
- 我們申請數(shù)組的長度是多少。
- 當(dāng)數(shù)組滿了之后怎么辦，也就是我們的擴(kuò)容機(jī)制。
對于這兩個問題，首先我們數(shù)組的初始大小可以有默認(rèn)值，在我們自己實現(xiàn)的MyArrayList當(dāng)中設(shè)置為10，我們在使用類時也可以傳遞一個參數(shù)指定初始大小。第二個問題當(dāng)我們的數(shù)組滿的時候我們需要對數(shù)組進(jìn)行擴(kuò)容，在我們實現(xiàn)的MyArrayList當(dāng)中我們采取的方式是，新數(shù)組的長度是原數(shù)組的兩倍（這個跟JDK的ArrayList方式不一樣，ArrayList擴(kuò)容為原來的1.5倍）。
代碼實現(xiàn)
為了讓我們的類實現(xiàn)的更加簡單我們在代碼當(dāng)中就不做很多非必要的邏輯判斷并且拋出異常，我們的代碼只要能表現(xiàn)出我們的思想即可。
首先定義一個接口MyCollection，表示我們要實現(xiàn)哪些方法！
public interface MyCollection<E> {
/**
* 往鏈表尾部加入一個數(shù)據(jù)
* @param o 加入到鏈表當(dāng)中的數(shù)據(jù)
* @return
*/
boolean add(E o);
/**
* 表示在第 index 位置插入數(shù)據(jù) o
* @param index
* @param o
* @return
*/
boolean add(int index, E o);
/**
* 從鏈表當(dāng)中刪除數(shù)據(jù) o
* @param o
* @return
*/
boolean remove(E o);
/**
* 從鏈表當(dāng)中刪除第 index 個數(shù)據(jù)
* @param index
* @return
*/
boolean remove(int index);
/**
* 往鏈表尾部加入一個數(shù)據(jù)，功能和 add 一樣
* @param o
* @return
*/
boolean append(E o);
/**
* 返回鏈表當(dāng)中數(shù)據(jù)的個數(shù)
* @return
*/
int size();
/**
* 表示鏈表是否為空
* @return
*/
boolean isEmpty();
/**
* 表示鏈表當(dāng)中是否包含數(shù)據(jù) o
* @param o
* @return
*/
boolean contain(E o);
/**
* 設(shè)置下標(biāo)為 index 的數(shù)據(jù)為 o
* @param index
* @param o
* @return
*/
boolean set(int index, E o);
}
我們的構(gòu)造函數(shù)，初始化過程。
public MyArrayList(int initialCapacity) {
this();
// 增長數(shù)組的空間為 initialCapacity，即申請一個數(shù)組
// 且數(shù)組的長度為 initialCapacity
grow(initialCapacity);
}
public MyArrayList() {
this.size = 0; // 容器當(dāng)中的數(shù)據(jù)個數(shù)在開始時為 0
this.elementData = EMPTY_INSTANCE; // 將數(shù)組設(shè)置為空數(shù)組
}
我們需要實現(xiàn)的最復(fù)雜的方法就是add了，這個方法是四個方法當(dāng)中最復(fù)雜的，其余的方法都相對比較簡單。
- 進(jìn)入
add方法之后，我們需要找到符合要求的最小數(shù)組長度，這個值通常是容器當(dāng)中元素的個數(shù)size + 1，也就是圖中的minCapacity首先先比較這個值和現(xiàn)在數(shù)組的長度，如果長度不夠的話則需要進(jìn)行擴(kuò)容，將數(shù)組的長度擴(kuò)大到原來的兩倍。 - 如果不需要擴(kuò)容，則直接講元素放入到數(shù)組當(dāng)中即可。
@Override
public boolean add(E o) {
// 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
ensureCapacity(size + 1);
// 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
elementData[++size] = o;
return true;
}
/**
* 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 capacity
* @param capacity
*/
public void ensureCapacity(int capacity) {
int candidateCapacity = findCapacity(capacity);
if (elementData.length < candidateCapacity)
grow(candidateCapacity);
}
/**
* 這個函數(shù)的主要目的就是找到最終數(shù)組長度需求的容量
* @param minCapacity
* @return
*/
private int findCapacity(int minCapacity) {
/**
* 如果 if 條件為 true 即 elementData 還是初始化時設(shè)置的空數(shù)組
* 那么返回默認(rèn)大小和需要大小的最大值
* 否則直接返回 minCapacity
*/
if (elementData == EMPTY_INSTANCE){
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
我們?yōu)槭裁葱枰獙?code>ensureCapacity的訪問限制權(quán)限設(shè)置為public？因為我們想讓用戶盡量去使用這個函數(shù)，因為如果我們?nèi)绻麑懗鱿旅孢@樣的代碼我們會一直申請內(nèi)存空間，然后也需要將前面的數(shù)組釋放掉，會給垃圾回收器造成更大的壓力。
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
list.add(i);
}
下面我們對ArrayList的方法進(jìn)行測試：
import java.util.ArrayList;
class Person {
String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
'}';
}
}
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<Person> o1 = new ArrayList<>();
o1.ensureCapacity(10000000);
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
o1.add(new Person());
}
long end = System.currentTimeMillis();
System.out.println("end - start: " + (end - start));
ArrayList<Person> o2 = new ArrayList<>();
start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
o2.add(new Person());
}
end = System.currentTimeMillis();
System.out.println("end - start: " + (end - start));
}
}
// 輸出結(jié)果
end - start: 1345
end - start: 4730
從上面的測試結(jié)果我們可以看出提前使用ensureCapacity方法之后，程序執(zhí)行的時間更加短。
插入數(shù)據(jù)的add方法。
@Override
public boolean add(E o) {
// 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
ensureCapacity(size + 1);
// 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
elementData[size] = o;
size++;
return true;
}
add在指定下標(biāo)插入數(shù)據(jù)。
- 首先將插入下標(biāo)后的數(shù)據(jù)往后移動一個位置
- 然后在將數(shù)據(jù)放在指定下標(biāo)的位置。
/**
* 在下標(biāo) index 位置插入數(shù)據(jù) o
* 首先先將 index 位置之后的數(shù)據(jù)往后移動一個位置
* 然后將 index 賦值為 o
* @param index
* @param o
* @return
*/
@Override
public boolean add(int index, E o) {
// 確保容器當(dāng)中的數(shù)組長度至少為 size + 1
ensureCapacity(size + 1);
// 將 elementData index位置之后的數(shù)據(jù)往后移動一個位置
// 做一個原地拷貝
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 移動的數(shù)據(jù)個數(shù)為 size - index
elementData[index] = o;
size++;
return true;
}
刪除數(shù)據(jù)的方法remove。
- 首先先刪除指定下標(biāo)的數(shù)據(jù)。
- 然后將指定下標(biāo)后的數(shù)據(jù)往前移動一個位置
- 在實際的操作過程中我們可以不刪除，直接移動，這樣也覆蓋被插入位置的數(shù)據(jù)了。
/**
* 移除下標(biāo)為 index 的數(shù)據(jù)
* @param index
* @return
*/
@Override
public boolean remove(int index) {
// 需要被移動的數(shù)據(jù)個數(shù)
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
return true;
}
移除容器當(dāng)中具體的某個對象。
/**
* 這個方法主要是用于溢出容器當(dāng)中具體的某個數(shù)據(jù)
* 首先先通過 for 循環(huán)遍歷容器當(dāng)中的每個數(shù)據(jù)，
* 比較找到相同的數(shù)據(jù)對應(yīng)的下標(biāo)，然后通過下標(biāo)移除方法
* @param o
* @return
*/
@Override
public boolean remove(E o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
remove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
remove(index);
return true;
}
}
return false;
}
set方法，這個方法就很簡單了。
@Override
public boolean set(int index, E o) {
elementData[index] = o;
return true;
}
重寫toString方法。
@Override
public String toString() {
if (size <= 0)
return "[]";
StringBuilder builder = new StringBuilder();
builder.append("[");
for (int index = 0; index < size; index++) {
builder.append(elementData[index].toString() + ", ");
}
builder.delete(builder.length() - 2, builder.length());
builder.append("]");
return builder.toString();
}
測試代碼
public static void main(String[] args) {
MyArrayList<Integer> list = new MyArrayList<>();
for (int i = 0; i < 15; i++) {
list.add(-i);
}
System.out.println(list.contain(5));
System.out.println(list);
list.remove(new Integer(-6));
System.out.println(list);
System.out.println(list.elementData.length); // 容器會擴(kuò)容兩倍，而默認(rèn)容器長度為10，因此這里是 20
list.add(5, 99999);
System.out.println(list);
System.out.println(list.contain(99999));
}
// 代碼輸出
false
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14]
[0, -1, -2, -3, -4, -5, -7, -8, -9, -10, -11, -12, -13, -14]
20
[0, -1, -2, -3, -4, 99999, -5, -7, -8, -9, -10, -11, -12, -13, -14]
true完整代碼
import java.util.ArrayList;
import java.util.Arrays;
public class MyArrayList<E> implements MyCollection<E> {
/**
* 容器當(dāng)中存儲數(shù)據(jù)的個數(shù)
*/
private int size;
/**
* 容器中數(shù)組的默認(rèn)長度
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 存放具體數(shù)據(jù)的數(shù)組，也就是我們?nèi)萜鳟?dāng)中真正存儲數(shù)據(jù)的地方
*/
Object[] elementData;
/**
* 當(dāng)容器當(dāng)中沒有數(shù)據(jù)將 elementData 設(shè)置為這個值，這個值是所有實例一起共享的
*/
private static final Object[] EMPTY_INSTANCE = {};
public MyArrayList(int initialCapacity) {
this();
// 增長數(shù)組的空間為 initialCapacity，即申請一個數(shù)組
// 且數(shù)組的長度為 initialCapacity
grow(initialCapacity);
}
public MyArrayList() {
this.size = 0; // 容器當(dāng)中的數(shù)據(jù)個數(shù)在開始時為 0
this.elementData = EMPTY_INSTANCE; // 將數(shù)組設(shè)置為空數(shù)組
}
/**
* 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 capacity
* @param capacity
*/
public void ensureCapacity(int capacity) {
int candidateCapacity = findCapacity(capacity);
if (elementData.length < candidateCapacity)
grow(candidateCapacity);
}
/**
* 這個函數(shù)的主要目的就是找到最終數(shù)組長度需求的容量
* @param minCapacity
* @return
*/
private int findCapacity(int minCapacity) {
/**
* 如果 if 條件為 true 即 elementData 還是初始化時設(shè)置的空數(shù)組
* 那么返回默認(rèn)大小和需要大小的最大值
* 否則直接返回 minCapacity
*/
if (elementData == EMPTY_INSTANCE){
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 該函數(shù)主要保證 elementData 的長度至少為 minCapacity
* 如果數(shù)組的長度小于 minCapacity 則需要進(jìn)行擴(kuò)容，反之
* @param minCapacity 數(shù)組的最短長度
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新的數(shù)組長度為原來數(shù)組長度的兩倍
int newCapacity = oldCapacity << 1;
// 如果數(shù)組新數(shù)組的長度 newCapacity 小于所需要的長度 minCapacity
// 新申請的長度應(yīng)該為 minCapacity
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
// 申請一個長度為 newCapacity 的數(shù)組，在將原來數(shù)組
// elementData 的數(shù)據(jù)拷貝到新數(shù)組當(dāng)中
elementData = Arrays.copyOf(elementData, newCapacity);
}
@Override
public boolean add(E o) {
// 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
ensureCapacity(size + 1);
// 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
elementData[size] = o;
size++;
return true;
}
/**
* 在下標(biāo) index 位置插入數(shù)據(jù) o
* 首先先將 index 位置之后的數(shù)據(jù)往后移動一個位置
* 然后將 index 賦值為 o
* @param index
* @param o
* @return
*/
@Override
public boolean add(int index, E o) {
// 確保容器當(dāng)中的數(shù)組長度至少為 size + 1
ensureCapacity(size + 1);
// 將 elementData index位置之后的數(shù)據(jù)往后移動一個位置
// 做一個原地拷貝
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 移動的數(shù)據(jù)個數(shù)為 size - index
elementData[index] = o;
size++;
return true;
}
/**
* 這個方法主要是用于溢出容器當(dāng)中具體的某個數(shù)據(jù)
* 首先先通過 for 循環(huán)遍歷容器當(dāng)中的每個數(shù)據(jù)，
* 比較找到相同的數(shù)據(jù)對應(yīng)的下標(biāo)，然后通過下標(biāo)移除方法
* @param o
* @return
*/
@Override
public boolean remove(E o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
remove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
remove(index);
return true;
}
}
return false;
}
/**
* 移除下標(biāo)為 index 的數(shù)據(jù)
* @param index
* @return
*/
@Override
public boolean remove(int index) {
// 需要被移動的數(shù)據(jù)個數(shù)
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
return true;
}
@Override
public boolean append(E o) {
return add(o);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contain(E o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
return true;
}
}
return false;
}
@Override
public String toString() {
if (size <= 0)
return "[]";
StringBuilder builder = new StringBuilder();
builder.append("[");
for (int index = 0; index < size; index++) {
builder.append(elementData[index].toString() + ", ");
}
builder.delete(builder.length() - 2, builder.length());
builder.append("]");
return builder.toString();
}
@Override
public boolean set(int index, E o) {
elementData[index] = o;
return true;
}
public static void main(String[] args) {
MyArrayList<Integer> list = new MyArrayList<>();
for (int i = 0; i < 15; i++) {
list.add(-i);
}
System.out.println(list.contain(5));
System.out.println(list);
list.remove(new Integer(-6));
System.out.println(list);
System.out.println(list.elementData.length);
list.add(5, 99999);
System.out.println(list);
System.out.println(list.contain(99999));
}
}
以上就是Java中數(shù)組容器(ArrayList)設(shè)的計與實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java數(shù)組容器的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Java中的thread類自帶有線程的一些方法，這些方法可以讓線程睡眠，插隊，提高線程調(diào)度的優(yōu)先級等等，它們提供了改變線程狀態(tài)的操作手段，這篇文章主要介紹了Java線程狀態(tài)及同步鎖,需要的朋友可以參考下2021-11-11
Spring Boot中使用Spring-data-jpa的配置方法詳解
今天小編就為大家分享一篇關(guān)于Spring Boot中使用Spring-data-jpa的配置方法詳解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
這篇文章主要介紹了淺談Java HttpURLConnection請求方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08
這篇文章主要介紹了Java多線程中的Phaser使用解析,java多線程技術(shù)提供了Phaser工具類,Phaser表示“階段器”,用來解決控制多個線程分階段共同完成任務(wù)的情景問題,其作用相比CountDownLatch和CyclicBarrier更加靈活,需要的朋友可以參考下2023-11-11
Springboot+MybatisPlus+Oracle實現(xiàn)主鍵自增的示例代碼
這篇文章主要介紹了Springboot+MybatisPlus+Oracle實現(xiàn)主鍵自增的示例代碼,本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
這篇文章主要給大家介紹了關(guān)于Spring Boot配置AOP打印日志的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Spring Boot具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
深入解析Java的Struts框架中的控制器DispatchAction
這篇文章主要介紹了深入解析Java的Struts框架中的控制器DispatchAction,Struts是Java的SSH三大web開發(fā)框架之一,需要的朋友可以參考下2015-12-12
SpringBoot中的@PostConstruct注解詳細(xì)解析
這篇文章主要介紹了SpringBoot中的@PostConstruct注解詳細(xì)解析,@PostConstruct注解,主要用于在Spring容器啟動時執(zhí)行某些操作或者任務(wù)，@PostConstruct注解一般放在BEAN的方法上,一旦BEAN初始化完成之后,將會調(diào)用這個方法,需要的朋友可以參考下2024-01-01
Java MultipartFile實現(xiàn)上傳文件/上傳圖片
這篇文章主要介紹了Java MultipartFile實現(xiàn)上傳文件/上傳圖片，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2020-12-12
Java深入分析Iterator迭代器與foreach循環(huán)的使用
這篇文章主要介紹了Java-Iterator迭代器與foreach循環(huán),主要包括Iterator迭代器接口的操作方法和foreach?循環(huán)語法解析，需要的朋友可以參考下2022-05-05