是否选择了合适的数据结构进行数据处理对系统的性能有着极大的影响，
JDK
中提供了常用的数据结构的实现类，比如链表、堆栈、哈希表，很多第三方开源库也进行了有益的扩展。关于这些类的原理以及使用可以参考相关的手册，在本节中重点讲解一些使用中需要注意的问题
。
1.1.1.
增量内存分配
ArrayList
、
HashMap
、
Vector
等类都允许我们向其中加入任意多的对象，从而进行处理的，我们在享受它们带来的便利的同时也要注意一定的性能问题。以
ArrayList
为例，我们来看一下在很多情况下是如何编写出低性能的代码的：
Cownew开源原创：
http://www.cownew.com
http://www.blogjava.net/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);
}