是否選擇了合適的數據結構進行數據處理對系統的性能有著極大的影響，
JDK
中提供了常用的數據結構的實現類，比如鏈表、堆棧、哈希表，很多第三方開源庫也進行了有益的擴展。關于這些類的原理以及使用可以參考相關的手冊，在本節中重點講解一些使用中需要注意的問題
。
1.1.1.??????
增量內存分配
ArrayList
、
HashMap
、
Vector
等類都允許我們向其中加入任意多的對象，從而進行處理的，我們在享受它們帶來的便利的同時也要注意一定的性能問題。以
ArrayList
為例，我們來看一下在很多情況下是如何編寫出低性能的代碼的：
Cownew開源原創：
http://www.cownew.com
http://www.tkk7.com/huanzhugege
在一個數組中有若干個對象，對象的類型都是
PersonInfo
，
PersonInfo
的類結構如下：
public class PersonInfo
{
???? //
身份證號碼
???? 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;
???? }
}
請將所有這些
PersonInf
的身份證號碼，也就是
id
屬性，提取出來，放到另一個
List
類型的變量中。
實現代碼
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());
}
程序運行正常，好像沒有出現任何問題。程序也確實真的不會出現問題，因為其邏輯如此簡單，不會但來問題。但是這個程序性能是最優的嗎？
讓我們來看看
ArrayList
類的實現
：
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
內部是使用數組保存的數據，
Java
中的數組是固定大小的，要想改變數組的大小，就要重新開辟一個新的大小的內存區域，把原先的數據復制到新內存區域中，這就是增量性數組。由于需要重新開辟內存區域并進行數據的復制，因此改變數組的大小是非常耗時的，我們要盡量避免改變數組的大小。
從
ArrayList
的內部實現我們可以發現，
ArrayList
中儲存數據用的數組的默認大小為
10
，當調用
add
方法向其中增加數據的時候，如果數據已經超過了數組的大小，
ArrayList
就要增加數組的大小以便容納更多的數據。在我們的這個人例子中，由于數據已經超過
10
條，當增加到第
11
條的時候，
ArrayList
就會進行一次“擴容”，這是一個非常耗時的操作，因此我們必須想方設法避免。
我們注意到
ArrayList
有一個帶參數的構造函數：
public ArrayList(int initialCapacity)
，這里的
initialCapacity
代表構造此
ArrayList
的時候，數組的大小。我們可以使用此構造函數來避免“擴容”。
實現代碼
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());
}
我們已經知道了
list
將放置
persons.length
條數據，因此我們就使
list
中數組的默認大小設置為
persons.length
，這樣系統的性能就好了很多。
不僅是
ArrayList
，我們在使用
Vector
、
HashMap
等類的同時，同樣要注意這個問題。
選用合適的類
List
接口最常用的實現類有兩個：
ArrayList
、
LinkedList
，我們一般都是通過
List
接口來調用這些類的實現方法，所以它們的使用方式是幾乎相同的，其區別就在于其實現方式。
正如
4.5.1
中闡述的那樣，
ArrayList
內部是使用數組保存的數據，而
LinkedList
則使用鏈表保存的數據。數組方式和鏈表方式儲存數據的優缺點比較如下
：
數組中的數據是順序排列的，因此要向數組中插入數據或者從數組中刪除數據，就必須對其他數據進行位置的改變，因此效率是非常低的；但是由于數組的數據是按下標讀取的，所以從數組中檢索數據是非常快的
。
鏈表中的數據是通過指針連在一起的，向鏈表中插入數據或者從鏈表中刪除數據只需要斷開指針關系即可，效率非常高；但是從鏈表中檢索數據的時候，必須從鏈表頭向后遍歷，效率非常低
。
因此
ArrayList
適合于保存很少插入、刪除，但是經常讀取的場合，而
LinkedList
適合于經常插入、刪除，但是很少讀取的場合。合理的使用這兩個類，將會提高系統的效率。
選用合適的數據結構
很多程序員都意識到了
Map
的方便性和實用性，因此也造成了
Map
的濫用。比如：
一個數組中有若干字符串，請驗證，這些字符串是否有重復。
實現代碼
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("
數據重復
");
????????
return;
???? }
???? map.put(data[i], "");
}
運行結果
：
數據重復
??????
這段代碼利用了
Map
中鍵不能重復的特性，實現了要求的效果，但是看起來怪怪的，因為
Map
中的數據是“鍵
-
值對”，而這里只用到了“鍵”，對于“值”則只是簡單的塞了一個空字符串進去應付差事。顯然這對
Map
來說是誤用。
實現代碼
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("
數據重復
");
???????? return;
???? }
???? set.add(data[i]);
}
運行結果
：
數據重復
??????
JDK
中的
Set
接口代表中數學中的“集合”（注意和
JDK
中的
Collection
區分開），即不重復的數據項的容器。顯然使用
Set
接口就完全能滿足我們的要求，同時我們又使用了采用哈希算法的
HashSet
，這就保證了判斷數據重復時的效率。案例系統中的
PermissionServiceImpl
類（包
com.cownew.PIS.base.permission.bizLayer
下）就是用
Set
來完成權限項名稱重復驗證的；類
ServerUserContext
（包
com.cownew.PIS.framework.server.sessionMgr
下）的
getPermissonNameSet
方法返回
Set
類型的意義也在于此
。
關于返回值
經常需要使用
List
、
Map
、
Set
等類做為方法返回值以返回多個數據，但是
JDK1.5
之前是不支持泛型的，我們只能看到方法返回一個
List
、
Map
或者
Set
類型的返回值，至于這些容器內存放著什么類型的數據則無法得知，只能通過查手冊才能得知。在讀取數據的時候又要進行類型轉換。這給系統留下了很多不確定性因素。在
JDK1.5
之前唯一能在編譯器就確定容器中數據的類型的
Java
結構就是數組，因此如果在返回數據的時候能夠確定數據的類型以及大小，并且確定調用者只是讀取返回值，那么我們就應該盡量使用數組來返回數據，這樣程序的可讀性就增強了，而且也減少了很多不確定性因素。
在使用返回值的時候還要注意一些慣用法。
（
1
）數組，一定不能返回
NULL
Object[] fooBar()
{
??? //do something
??? return null;
}
極少有人這樣使用此方法：
Object[] objArray = fooBar();
if (objArray != null)
{
??? for (int i = 0; i < objArray.Length; ++i)
??? {
??????? //do something
??? }
}
應該這樣寫
fooBar
方法：
Object[] fooBar()
{
??? //do something
??? return new Object[0];
}
（
2
）集合，同樣不能返回
NULL
Set fooBar()
{
??? //do something
??? return null;
}
應該這樣寫：
Set fooBar()
{
??? //do something
??? return new HashSet(0);
}