基礎(chǔ)知識(shí)

數(shù)組是具有相同類型的數(shù)據(jù)的集合，也就是說數(shù)組的所有元素的類型都是相同的，在所有的數(shù)據(jù)結(jié)構(gòu)中，數(shù)組算是最常見也是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，我們最常見的也就是一維數(shù)組，當(dāng)然還有二維，三維……，數(shù)組需要先聲明才能使用，數(shù)組的大小一旦確定就不可以在變了。比如我們聲明一個(gè)長度為10的數(shù)組

1int[]?array?=?new?int[10];

數(shù)組的下標(biāo)是從0開始的，比如上面數(shù)組的第一個(gè)元素是array[0]，最后一個(gè)元素是array[9]。

我們還可以在聲明的時(shí)候直接對他進(jìn)行初始化，比如

1int[]?array?=?new?int[]{1,?2,?3};

上面我們聲明了一個(gè)長度為3的數(shù)組。

源碼分析

操作數(shù)組的類我們常見的估計(jì)也就是ArrayList了，他對數(shù)組的操作非常簡單，所有的數(shù)據(jù)都會(huì)存放到這個(gè)數(shù)組中

1transient?Object[]?elementData;

我們來看一下他常見的幾個(gè)方法，首先是get方法

1public?E?get(int?index)?{2????if?(index?>=?size)3????????throw?new?IndexOutOfBoundsException(outOfBoundsMsg(index));45????return?(E)?elementData[index];6}

首先判斷是否越界，如果越界直接拋異常，否則就根據(jù)他的下標(biāo)從數(shù)組中直接返回，在看一下他的set方法

1public?E?set(int?index,?E?element)?{2????if?(index?>=?size)3????????throw?new?IndexOutOfBoundsException(outOfBoundsMsg(index));45????E?oldValue?=?(E)?elementData[index];6????elementData[index]?=?element;7????return?oldValue;8}

和get方法一樣，也是先判斷是否越界，然后再操作，代碼比較簡單，我們再來看一個(gè)add方法

1public?void?add(int?index,?E?element)?{ 2????if?(index?>?size?||?index?0)
3????????throw?new?IndexOutOfBoundsException(outOfBoundsMsg(index));
4
5????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
6????System.arraycopy(elementData,?index,?elementData,?index?+?1,
7?????????????????????size?-?index);
8????elementData[index]?=?element;
9????size++;
10}

這里也是先判斷是否越界，然后再判斷是否需要擴(kuò)容，最后在操作，接著我們來看一下ensureCapacityInternal方法

1private?void?ensureCapacityInternal(int?minCapacity)?{ 2????if?(elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{ 3????????minCapacity?=?Math.max(DEFAULT_CAPACITY,?minCapacity); 4????} 5 6????ensureExplicitCapacity(minCapacity); 7} 8 9private?void?ensureExplicitCapacity(int?minCapacity)?{10????modCount++;1112????//?overflow-conscious?code13????if?(minCapacity?-?elementData.length?>?0)14????????grow(minCapacity);15}

他的默認(rèn)初始化大小是10

1private?static?final?int?DEFAULT_CAPACITY?=?10;

上面代碼第13行，如果我們需要的空間大于數(shù)組長度的時(shí)候，說明數(shù)組不夠用了，要進(jìn)行擴(kuò)容，就會(huì)執(zhí)行下面的grow方法，我們來看一下grow方法的代碼

1private?void?grow(int?minCapacity)?{ 2????//?overflow-conscious?code 3????int?oldCapacity?=?elementData.length; 4????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1); 5????if?(newCapacity?-?minCapacity?0)
6????????newCapacity?=?minCapacity;
7????if?(newCapacity?-?MAX_ARRAY_SIZE?>?0)
8????????newCapacity?=?hugeCapacity(minCapacity);
9????//?minCapacity?is?usually?close?to?size,?so?this?is?a?win:
10????elementData?=?Arrays.copyOf(elementData,?newCapacity);
11}

代碼也比較簡單，擴(kuò)容的時(shí)候在第4行還會(huì)增加一半的大小，比如原來數(shù)組大小是10，第一次擴(kuò)容后會(huì)是15。在ArrayList中無論使用add還是remove都會(huì)使用這樣一個(gè)方法

1????????System.arraycopy(elementData,?index+1,?elementData,?index,
2?????????????????????????numMoved);

這說明對數(shù)組的查找是比較方便的，但對數(shù)組的增刪就沒那么方便了，因?yàn)閿?shù)組是一塊連續(xù)的內(nèi)存空間，如果在前面增加和刪除，都會(huì)導(dǎo)致后面元素位置的變動(dòng)。

ArraList是線程不安全，如果使用線程安全的可以用Vector，還有一個(gè)線程安全的類

CopyOnWriteArrayList，他只在add和remove的時(shí)候，也就是修改數(shù)據(jù)的時(shí)候會(huì)先synchronized，在get的時(shí)候沒有，我們來看一下代碼

1private?E?get(Object[]?a,?int?index)?{
2????return?(E)?a[index];
3}

我們再來看一下他的add方法

1public?boolean?add(E?e)?{
2????synchronized?(lock)?{
3????????Object[]?elements?=?getArray();
4????????int?len?=?elements.length;
5????????Object[]?newElements?=?Arrays.copyOf(elements,?len?+?1);
6????????newElements[len]?=?e;
7????????setArray(newElements);
8????????return?true;
9????}
10}

他不像ArrayList每次擴(kuò)容的時(shí)候，size都會(huì)增加一半，他是每次add一個(gè)元素的時(shí)候size只會(huì)加1，同理remove的時(shí)候size只會(huì)減1。

后話

常見的數(shù)據(jù)結(jié)構(gòu)種類也不是很多，比如，數(shù)組，鏈表，隊(duì)列，棧，樹，圖，等，還有數(shù)組和鏈表結(jié)合的，比如HashMap。但每一種又會(huì)有很多的分類，比如鏈表有單向的，雙向的，環(huán)形的，隊(duì)列又有一般的隊(duì)列和雙端隊(duì)列，樹又分為二叉樹，AVL樹，紅黑樹，B+樹，2-3樹，哈夫曼樹，字典樹等等。如果細(xì)分下去，還是比較多的，今天講的數(shù)組是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，基本上也沒什么可說的，剩下的那些數(shù)據(jù)結(jié)構(gòu)后續(xù)都會(huì)一一分析。

總結(jié)

以上是生活随笔為你收集整理的扩容是元素还是数组_348，数据结构1,数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。