是否選擇了合適的數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)處理對(duì)系統(tǒng)的性能有著極大的影響，
JDK
中提供了常用的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)類，比如鏈表、堆棧、哈希表，很多第三方開(kāi)源庫(kù)也進(jìn)行了有益的擴(kuò)展。關(guān)于這些類的原理以及使用可以參考相關(guān)的手冊(cè)，在本節(jié)中重點(diǎn)講解一些使用中需要注意的問(wèn)題
。
1.1.1.??????
增量?jī)?nèi)存分配
ArrayList
、
HashMap
、
Vector
等類都允許我們向其中加入任意多的對(duì)象，從而進(jìn)行處理的，我們?cè)谙硎芩鼈儙?lái)的便利的同時(shí)也要注意一定的性能問(wèn)題。以
ArrayList
為例，我們來(lái)看一下在很多情況下是如何編寫(xiě)出低性能的代碼的：
Cownew開(kāi)源原創(chuàng)：
http://www.cownew.com
http://www.aygfsteel.com/huanzhugege
在一個(gè)數(shù)組中有若干個(gè)對(duì)象，對(duì)象的類型都是
PersonInfo
，
PersonInfo
的類結(jié)構(gòu)如下：
public class PersonInfo
{
???? //
身份證號(hào)碼
???? private String id;
???? //
姓名
???? private String name;
???? //
年齡
???? private int age;
???? public PersonInfo(String id, String name, int age)
???? {
???????? super();
???????? this.id = id;
???????? this.name = name;
???????? this.age = age;
???? }
?
???? public int getAge()
???? {
???????? return age;
???? }
?
???? public String getId()
???? {
???????? return id;
???? }
?
???? public String getName()
???? {
???????? return name;
???? }
}
請(qǐng)將所有這些
PersonInf
的身份證號(hào)碼，也就是
id
屬性，提取出來(lái)，放到另一個(gè)
List
類型的變量中。
實(shí)現(xiàn)代碼
1
：
PersonInfo[] persons = new PersonInfo[] {
???????? new PersonInfo("00001", "Tom", 20),
???????? new PersonInfo("00002", "Tim", 23),
???????? new PersonInfo("00003", "Sally", 26),
???????? new PersonInfo("00005", "Lily", 20),
???????? new PersonInfo("00006", "Lucy", 30),
???????? new PersonInfo("00008", "Kitty", 20),
???????? new PersonInfo("00011", "Smith", 20),
???????? new PersonInfo("00031", "Ketty", 22),
???????? new PersonInfo("00051", "Melly", 20),
???????? new PersonInfo("00022", "Blues", 20),
???????? new PersonInfo("00033", "Tid", 18),
???????? new PersonInfo("00101", "Duoliaos", 30),
???????? new PersonInfo("00201", "Yang", 26),
???????? new PersonInfo("03001", "King", 20),
???????? new PersonInfo("05001", "Lee", 20),
???????? new PersonInfo("10001", "Wang", 20),
???????? new PersonInfo("06001", "Pizza", 60) };
?
List list = new ArrayList();
for (int i = 0, n = persons.length; i < n; i++)
{
???? PersonInfo pInfo = persons[i];
???? list.add(pInfo.getId());
}
程序運(yùn)行正常，好像沒(méi)有出現(xiàn)任何問(wèn)題。程序也確實(shí)真的不會(huì)出現(xiàn)問(wèn)題，因?yàn)槠溥壿嬋绱撕?jiǎn)單，不會(huì)但來(lái)問(wèn)題。但是這個(gè)程序性能是最優(yōu)的嗎？
讓我們來(lái)看看
ArrayList
類的實(shí)現(xiàn)
：
public class ArrayList extends AbstractList implements List, RandomAccess,
???????? Cloneable, java.io.Serializable
{
????
……
???? private transient Object elementData[];
????
……
???? public ArrayList(int initialCapacity)
???? {
???????? super();
???????? if (initialCapacity < 0)
????????????? throw new IllegalArgumentException("Illegal Capacity: "
?????????????????????? + initialCapacity);
???????? this.elementData = new Object[initialCapacity];
???? }
???? public ArrayList()
???? {
???????? this(10);
???? }
????
……
???? public void ensureCapacity(int minCapacity)
???? {
???????? modCount++;
???????? int oldCapacity = elementData.length;
???????? if (minCapacity > oldCapacity)
???????? {
????????????? Object oldData[] = elementData;
????????????? int newCapacity = (oldCapacity * 3) / 2 + 1;
????????????? if (newCapacity < minCapacity)
?????????????????? newCapacity = minCapacity;
????????????? elementData = new Object[newCapacity];
????????????? System.arraycopy(oldData, 0, elementData, 0, size);
???????? }
???? }???
?
???? public boolean add(Object o)
???? {
???????? ensureCapacity(size + 1);
???????? elementData[size++] = o;
???????? return true;
???? }
}
正如其名字所暗示的，
ArrayList
內(nèi)部是使用數(shù)組保存的數(shù)據(jù)，
Java
中的數(shù)組是固定大小的，要想改變數(shù)組的大小，就要重新開(kāi)辟一個(gè)新的大小的內(nèi)存區(qū)域，把原先的數(shù)據(jù)復(fù)制到新內(nèi)存區(qū)域中，這就是增量性數(shù)組。由于需要重新開(kāi)辟內(nèi)存區(qū)域并進(jìn)行數(shù)據(jù)的復(fù)制，因此改變數(shù)組的大小是非常耗時(shí)的，我們要盡量避免改變數(shù)組的大小。
從
ArrayList
的內(nèi)部實(shí)現(xiàn)我們可以發(fā)現(xiàn)，
ArrayList
中儲(chǔ)存數(shù)據(jù)用的數(shù)組的默認(rèn)大小為
10
，當(dāng)調(diào)用
add
方法向其中增加數(shù)據(jù)的時(shí)候，如果數(shù)據(jù)已經(jīng)超過(guò)了數(shù)組的大小，
ArrayList
就要增加數(shù)組的大小以便容納更多的數(shù)據(jù)。在我們的這個(gè)人例子中，由于數(shù)據(jù)已經(jīng)超過(guò)
10
條，當(dāng)增加到第
11
條的時(shí)候，
ArrayList
就會(huì)進(jìn)行一次“擴(kuò)容”，這是一個(gè)非常耗時(shí)的操作，因此我們必須想方設(shè)法避免。
我們注意到
ArrayList
有一個(gè)帶參數(shù)的構(gòu)造函數(shù)：
public ArrayList(int initialCapacity)
，這里的
initialCapacity
代表構(gòu)造此
ArrayList
的時(shí)候，數(shù)組的大小。我們可以使用此構(gòu)造函數(shù)來(lái)避免“擴(kuò)容”。
實(shí)現(xiàn)代碼
2
：
PersonInfo[] persons = new PersonInfo[] {
???????? new PersonInfo("00001", "Tom", 20),
???????? new PersonInfo("00002", "Tim", 23),
???????? new PersonInfo("00003", "Sally", 26),
???????? new PersonInfo("00005", "Lily", 20),
???????? new PersonInfo("00006", "Lucy", 30),
???????? new PersonInfo("00008", "Kitty", 20),
???????? new PersonInfo("00011", "Smith", 20),
???????? new PersonInfo("00031", "Ketty", 22),
???????? new PersonInfo("00051", "Melly", 20),
???????? new PersonInfo("00022", "Blues", 20),
???????? new PersonInfo("00033", "Tid", 18),
???????? new PersonInfo("00101", "Duoliaos", 30),
???????? new PersonInfo("00201", "Yang", 26),
???????? new PersonInfo("03001", "King", 20),
???????? new PersonInfo("05001", "Lee", 20),
???????? new PersonInfo("10001", "Wang", 20),
???????? new PersonInfo("06001", "Pizza", 60) };
?
List list = new ArrayList(persons.length);
for (int i = 0, n = persons.length; i < n; i++)
{
???? PersonInfo pInfo = persons[i];
???? list.add(pInfo.getId());
}
我們已經(jīng)知道了
list
將放置
persons.length
條數(shù)據(jù)，因此我們就使
list
中數(shù)組的默認(rèn)大小設(shè)置為
persons.length
，這樣系統(tǒng)的性能就好了很多。
不僅是
ArrayList
，我們?cè)谑褂?/span>
Vector
、
HashMap
等類的同時(shí)，同樣要注意這個(gè)問(wèn)題。
選用合適的類
List
接口最常用的實(shí)現(xiàn)類有兩個(gè)：
ArrayList
、
LinkedList
，我們一般都是通過(guò)
List
接口來(lái)調(diào)用這些類的實(shí)現(xiàn)方法，所以它們的使用方式是幾乎相同的，其區(qū)別就在于其實(shí)現(xiàn)方式。
正如
4.5.1
中闡述的那樣，
ArrayList
內(nèi)部是使用數(shù)組保存的數(shù)據(jù)，而
LinkedList
則使用鏈表保存的數(shù)據(jù)。數(shù)組方式和鏈表方式儲(chǔ)存數(shù)據(jù)的優(yōu)缺點(diǎn)比較如下
：
數(shù)組中的數(shù)據(jù)是順序排列的，因此要向數(shù)組中插入數(shù)據(jù)或者從數(shù)組中刪除數(shù)據(jù)，就必須對(duì)其他數(shù)據(jù)進(jìn)行位置的改變，因此效率是非常低的；但是由于數(shù)組的數(shù)據(jù)是按下標(biāo)讀取的，所以從數(shù)組中檢索數(shù)據(jù)是非?？斓?/span>
。
鏈表中的數(shù)據(jù)是通過(guò)指針連在一起的，向鏈表中插入數(shù)據(jù)或者從鏈表中刪除數(shù)據(jù)只需要斷開(kāi)指針關(guān)系即可，效率非常高；但是從鏈表中檢索數(shù)據(jù)的時(shí)候，必須從鏈表頭向后遍歷，效率非常低
。
因此
ArrayList
適合于保存很少插入、刪除，但是經(jīng)常讀取的場(chǎng)合，而
LinkedList
適合于經(jīng)常插入、刪除，但是很少讀取的場(chǎng)合。合理的使用這兩個(gè)類，將會(huì)提高系統(tǒng)的效率。
選用合適的數(shù)據(jù)結(jié)構(gòu)
很多程序員都意識(shí)到了
Map
的方便性和實(shí)用性，因此也造成了
Map
的濫用。比如：
一個(gè)數(shù)組中有若干字符串，請(qǐng)驗(yàn)證，這些字符串是否有重復(fù)。
實(shí)現(xiàn)代碼
1
：
String[] data = { "11", "22", "33", "55", "11", "66" };
Map map = new HashMap();
for (int i = 0, n = data.length; i < n; i++)
{
???? if (map.containsKey(data[i]))
???? {
???????? System.out.println("
數(shù)據(jù)重復(fù)
");
????????
return;
???? }
???? map.put(data[i], "");
}
運(yùn)行結(jié)果
：
數(shù)據(jù)重復(fù)
??????
這段代碼利用了
Map
中鍵不能重復(fù)的特性，實(shí)現(xiàn)了要求的效果，但是看起來(lái)怪怪的，因?yàn)?/span>
Map
中的數(shù)據(jù)是“鍵
-
值對(duì)”，而這里只用到了“鍵”，對(duì)于“值”則只是簡(jiǎn)單的塞了一個(gè)空字符串進(jìn)去應(yīng)付差事。顯然這對(duì)
Map
來(lái)說(shuō)是誤用。
實(shí)現(xiàn)代碼
2
：
String[] data = { "11", "22", "33", "55", "11", "66" };
Set set = new HashSet();
for (int i = 0, n = data.length; i < n; i++)
{
???? if (set.contains(data[i]))
???? {
???????? System.out.println("
數(shù)據(jù)重復(fù)
");
???????? return;
???? }
???? set.add(data[i]);
}
運(yùn)行結(jié)果
：
數(shù)據(jù)重復(fù)
??????
JDK
中的
Set
接口代表中數(shù)學(xué)中的“集合”（注意和
JDK
中的
Collection
區(qū)分開(kāi)），即不重復(fù)的數(shù)據(jù)項(xiàng)的容器。顯然使用
Set
接口就完全能滿足我們的要求，同時(shí)我們又使用了采用哈希算法的
HashSet
，這就保證了判斷數(shù)據(jù)重復(fù)時(shí)的效率。案例系統(tǒng)中的
PermissionServiceImpl
類（包
com.cownew.PIS.base.permission.bizLayer
下）就是用
Set
來(lái)完成權(quán)限項(xiàng)名稱重復(fù)驗(yàn)證的；類
ServerUserContext
（包
com.cownew.PIS.framework.server.sessionMgr
下）的
getPermissonNameSet
方法返回
Set
類型的意義也在于此
。
關(guān)于返回值
經(jīng)常需要使用
List
、
Map
、
Set
等類做為方法返回值以返回多個(gè)數(shù)據(jù)，但是
JDK1.5
之前是不支持泛型的，我們只能看到方法返回一個(gè)
List
、
Map
或者
Set
類型的返回值，至于這些容器內(nèi)存放著什么類型的數(shù)據(jù)則無(wú)法得知，只能通過(guò)查手冊(cè)才能得知。在讀取數(shù)據(jù)的時(shí)候又要進(jìn)行類型轉(zhuǎn)換。這給系統(tǒng)留下了很多不確定性因素。在
JDK1.5
之前唯一能在編譯器就確定容器中數(shù)據(jù)的類型的
Java
結(jié)構(gòu)就是數(shù)組，因此如果在返回?cái)?shù)據(jù)的時(shí)候能夠確定數(shù)據(jù)的類型以及大小，并且確定調(diào)用者只是讀取返回值，那么我們就應(yīng)該盡量使用數(shù)組來(lái)返回?cái)?shù)據(jù)，這樣程序的可讀性就增強(qiáng)了，而且也減少了很多不確定性因素。
在使用返回值的時(shí)候還要注意一些慣用法。
（
1
）數(shù)組，一定不能返回
NULL
Object[] fooBar()
{
??? //do something
??? return null;
}
極少有人這樣使用此方法：
Object[] objArray = fooBar();
if (objArray != null)
{
??? for (int i = 0; i < objArray.Length; ++i)
??? {
??????? //do something
??? }
}
應(yīng)該這樣寫(xiě)
fooBar
方法：
Object[] fooBar()
{
??? //do something
??? return new Object[0];
}
（
2
）集合，同樣不能返回
NULL
Set fooBar()
{
??? //do something
??? return null;
}
應(yīng)該這樣寫(xiě)：
Set fooBar()
{
??? //do something
??? return new HashSet(0);
}