你的位置:首页 > Java教程

[Java教程]编写高质量代码:改善Java程序的151个建议(第5章:数组和集合___建议65~69)


建议65:避开基本类型数组转换列表陷阱

   我们在开发中经常会使用Arrays和Collections这两个工具类和列表之间转换,非常方便,但也有时候会出现一些奇怪的问题,来看如下代码: 

1 public class Client65 {2   public static void main(String[] args) {3     int data [] = {1,2,3,4,5};4     List list= Arrays.asList(data);5     System.out.println("列表中的元素数量是:"+list.size());6   }7 }

  也许你会说,这很简单,list变量的元素数量当然是5了。但是运行后打印出来的列表数量为1。

  事实上data确实是一个有5个元素的int类型数组,只是通过asList转换成列表后就只有一个元素了,这是为什么呢?其他4个元素到什么地方去了呢?

  我们仔细看一下Arrays.asList的方法说明:输入一个变长参数,返回一个固定长度的列表。注意这里是一个变长参数,看源码:

 public static <T> List<T> asList(T... a) {    return new ArrayList<>(a);  }

  asList方法输入的是一个泛型变长参数,我们知道基本类型是不能泛型化的,也就是说8个基本类型不能作为泛型参数,要想作为泛型参数就必须使用其所对应的包装类型,那前面的例子传递了一个int类型的数组,为何程序没有报编译错误呢?

  在Java中,数组是一个对象,它是可以泛型化的,也就是说我们的例子是把一个int类型的数组作为了T的类型,所以在转换后在List中就只有一个类型为int数组的元素了,我们打印出来看看,代码如下: 

1 public class Client65 {2   public static void main(String[] args) {3     int data [] = {1,2,3,4,5};4     List list= Arrays.asList(data);5     System.out.println("元素类型是:"+list.get(0).getClass());6     System.out.println("前后是否相等:"+data.equals(list.get(0)));  7   }8 }

  输出的结果是: 元素类型是:class [I   前后是否相等:true

  很明显,放在列表中的元素时一个int数组,可能有人要问了,为什么"元素类型:"后的class是"[I"?我们并没有指明是数组(Array)类型呀!这是因为JVM不可能输出Array类型,因为Array是属于java.lang.reflect包的,它是通过反射访问数组元素的工具类。在Java中任何一个一维数组的类型都是 " [I " ,究其原因就是Java并没有定义数组这一个类,它是在编译器编译的时候生成的,是一个特殊的类,在JDK的帮助中也没有任何数组类的信息。

  弄清楚了问题,修改也很easy,直接使用包装类即可,部分代码如下: 

Integer data [] = {1,2,3,4,5};

  把int替换为Integer即可让输出元素数量为5.需要说明的是,不仅仅是int类型的数组有这个问题,其它7个基本类型的数组也存在相似的问题,这就需要大家注意了,在把基本类型数组转换为列表时,要特别小心asList方法的陷阱,避免出现程序逻辑混乱的情况。

  注意:原始类型数组不能作为asList的输入参数,否则会引起程序逻辑混乱。

建议66:asList方法产生的List的对象不可更改

  上一个建议指出了asList方法在转换基本类型数组时存在的问题,接着我们看一下asList方法返回的列表有何特殊的地方,代码如下:  

 1 public class Client66 { 2   public static void main(String[] args) { 3     // 五天工作制 4     Week days[] = { Week.Mon, Week.Tue, Week.Wed, Week.Thu, Week.Fri }; 5     // 转换为列表 6     List<Week> list = Arrays.asList(days); 7     // 增加周六为工作日 8     list.add(Week.Sat); 9     /* do something */10   }11 }12 enum Week {13   Sun, Mon, Tue, Wed, Thu, Fri, Sat14 }

  很简单的程序呀,默认声明的工作日(workDays)是从周一到周五,偶尔周六也会算作工作日加入到工作日列表中,不过,这段程序执行时会不会有什么问题呢?编译没有任何问题,但是一运行,却出现了如下结果:

  

UnsupportedOperationException,不支持的操作,居然不支持list的add方法,这是什么原因呢?我们看看asList方法的源代码:

 public static <T> List<T> asList(T... a) {    return new ArrayList<>(a);  }

  直接new了一个ArrayList对象返回,难道ArrayList不支持add方法,不可能呀!可能,问题就出现在这个ArrayList类上,此ArrayList非java.util.ArrayList,而是Arrays工具类的一个内部类,其构造函数如下所示: 

 1 private static class ArrayList<E> extends AbstractList<E> 2     implements RandomAccess, java.io.Serializable 3   { 4     private static final long serialVersionUID = -2764017481108945198L; 5     private final E[] a; 6  7     ArrayList(E[] array) { 8       if (array==null) 9         throw new NullPointerException();10       a = array;11     }12   /*其它方法略*/  13 }  

  这个ArrayList是一个静态私有内部类,除了Arrays能访问外,其它类都不能访问,仔细看这个类,它没有提供add方法,那肯定是父类AbstractList提供了,来看代码:  

1 public boolean add(E e) {2     add(size(), e);3     return true;4   }5 6 public void add(int index, E element) {7     throw new UnsupportedOperationException();8   }

  父类确实提供了,但没有提供具体的实现,所以每个子类都需要自己覆写add方法,而Arrays的内部类ArrayList没有覆写,因此add一个元素就报错了。

  我们深入地看看这个ArrayList静态内部类,它仅仅实现了5个方法:

  1. size:元素数量
  2. get:获得制定元素
  3. set:重置某一元素值
  4. contains:是否包含某元素
  5. toArray:转化为数组,实现了数组的浅拷贝

  把这几个方法的源代码展示一下: 

 1 //元素数量 2    public int size() { 3       return a.length; 4     } 5  6     public Object[] toArray() { 7       return a.clone(); 8     } 9     //转化为数组,实现了数组的浅拷贝10     public <T> T[] toArray(T[] a) {11       int size = size();12       if (a.length < size)13         return Arrays.copyOf(this.a, size,14                   (Class<? extends T[]>) a.getClass());15       System.arraycopy(this.a, 0, a, 0, size);16       if (a.length > size)17         a[size] = null;18       return a;19     }20     //获得指定元素21     public E get(int index) {22       return a[index];23     }24     //重置某一元素25     public E set(int index, E element) {26       E oldValue = a[index];27       a[index] = element;28       return oldValue;29     }30 31     public int indexOf(Object o) {32       if (o==null) {33         for (int i=0; i<a.length; i++)34           if (a[i]==null)35             return i;36       } else {37         for (int i=0; i<a.length; i++)38           if (o.equals(a[i]))39             return i;40       }41       return -1;42     }43     //是否包含元素44     public boolean contains(Object o) {45       return indexOf(o) != -1;46     }

  对于我们经常使用list.add和list.remove方法它都没有实现,也就是说asList返回的是一个长度不可变的列表,数组是多长,转换成的列表也就是多长,换句话说此处的列表只是数组的一个外壳,不再保持列表的动态变长的特性,这才是我们关注的重点。有些开发人员喜欢这样定义个初始化列表: 

  List<String> names= Arrays.asList("张三","李四","王五");

  一句话完成了列表的定义和初始化,看似很便捷,却隐藏着重大隐患---列表长度无法修改。想想看,如果这样一个List传递到一个允许添加的add操作的方法中,那将会产生何种结果,如果有这种习惯的javaer,请慎之戒之,除非非常自信该List只用于只读操作。

建议67:不同的列表选择不同的遍历算法

   我们思考这样一个案例:统计一个省的各科高考平均值,比如数学平均分是多少,语文平均分是多少等,这是每年招生办都会公布的数据,我们来想想看该算法应如何实现。当然使用数据库中的一个SQL语句就可能求出平均值,不过这不再我们的考虑之列,这里还是使用纯Java的算法来解决之,看代码:  

 1 public class Client67 { 2   public static void main(String[] args) { 3     // 学生数量 80万 4     int stuNum = 80 * 10000; 5     // List集合,记录所有学生的分数 6     List<Integer> scores = new ArrayList<Integer>(stuNum); 7     // 写入分数 8     for (int i = 0; i < stuNum; i++) { 9       scores.add(new Random().nextInt(150));10     }11     // 记录开始计算 时间12     long start = System.currentTimeMillis();13     System.out.println("平均分是:" + average(scores));14     long end = System.currentTimeMillis();15     System.out.println("执行时间:" + (end - start) + "ms");16   }17 18   public static int average(List<Integer> scores) {19     int sum = 0;20     // 遍历求和21     for (int i : scores) {22       sum += i;23     }24     return sum / scores.size();25   }26 }

  把80万名学生的成绩放到一个ArrayList数组中,然后通过foreach方法遍历求和,再计算平均值,程序很简单,输出结果:

  平均分是:74
     执行时间:11ms

  仅仅计算一个算术平均值就花了11ms,不要说什么其它诸如加权平均值,补充平均值等算法,那花的时间肯定更长。我们仔细分析一下average方法,加号操作是最基本的,没有什么可以优化的,剩下的就是一个遍历了,问题是List的遍历可以优化吗?

  我们尝试一下,List的遍历还有另外一种方式,即通过下标方式来访问,代码如下:

1 public static int average(List<Integer> scores) {2     int sum = 0;3     // 遍历求和4     for (int i = 0; i < scores.size(); i++) {5       sum += scores.get(i);6     }7     return sum / scores.size();8   }

  不再使用foreach遍历,而是采用下标方式遍历,我们看看输出结果:

          平均分是:74
             执行时间:8ms
  执行时间已经下降,如果数据量更大,会更明显。那为什么我们使用下标方式遍历数组可以提高的性能呢?

  这是因为ArrayList数组实现了RandomAccess接口(随机存取接口),这样标志着ArrayList是一个可以随机存取的列表。在Java中,RandomAccess和Cloneable、Serializable一样,都是标志性接口,不需要任何实现,只是用来表明其实现类具有某种特质的,实现了Cloneable表明可以被拷贝,实现了Serializable接口表明被序列化了,实现了RandomAccess接口则表明这个类可以随机存取,对我们的ArrayList来说也就标志着其数据元素之间没有关联,即两个位置相邻的元素之间没有相互依赖和索引关系,可以随机访问和存取。我们知道,Java的foreach语法时iterator(迭代器)的变形用法,也就是说上面的foreach与下面的代码等价:

for (Iterator<Integer> i = scores.iterator(); i.hasNext();) {      sum += i.next();    }

  那我们再想想什么是迭代器,迭代器是23中设计模式中的一种,"提供一种方法访问一个容器对象中的各个元素,同时又无须暴露该对象的内部细节",也就是说对于ArrayList,需要先创建一个迭代器容器,然后屏蔽内部遍历细节,对外提供hasNext、next等方法。问题是ArrayList实现RandomAccess接口,表明元素之间本来没有关系,可是,为了使用迭代器就需要强制建立一种相互"知晓"的关系,比如上一个元素可以判断是否有下一个元素,以及下一个元素时什么等关系,这也就是foreach遍历耗时的原因。

  Java的ArrayList类加上了RandomAccess接口,就是在告诉我们,“ArrayList是随机存取的,采用下标方式遍历列表速度回更快”,接着又有一个问题,为什么不把RandomAccess接口加到所有List的实现类上呢?

  那是因为有些List的实现类不是随机存取的,而是有序存取的,比如LinkedList类,LinkedList类也是一个列表,但它实现了双向链表,每个数据节点都有三个数据项:前节点的引用(Previous Node)、本节点元素(Node Element)、后继结点的引用(Next Node),这是数据结构的基本知识,不多讲了,也就是说在LinkedList中的两个元素本来就是有关联的,我知道你的存在,你也知道我的存在。那大家想想看,元素之间已经有关联了,使用foreach也就是迭代器方式是不是效率更高呢?我们修改一下例子,代码如下:

 1 public static void main(String[] args) { 2     // 学生数量 80万 3     int stuNum = 80 * 10000; 4     // List集合,记录所有学生的分数 5     List<Integer> scores = new LinkedList<Integer>(); 6     // 写入分数 7     for (int i = 0; i < stuNum; i++) { 8       scores.add(new Random().nextInt(150)); 9     }10     // 记录开始计算 时间11     long start = System.currentTimeMillis();12     System.out.println("平均分是:" + average(scores));13     long end = System.currentTimeMillis();14     System.out.println("执行时间:" + (end - start) + "ms");15   }16 17   public static int average(List<Integer> scores) {18     int sum = 0;19     // 遍历求和20     for (int i : scores) {21       sum += i;22     }23     return sum / scores.size();24   }

输出结果为:  平均分是:74 执行时间:12ms 。执行效率还好。但是比ArrayList就慢了,但如果LinkedList采用下标方式遍历:效率会如何呢?我告诉你会很慢。直接分析一下源码: 

1 public E get(int index) {2     checkElementIndex(index);3     return node(index).item;4   }

  由node方法查找指定下标的节点,然后返回其包含的元素,看node方法: 

 1 Node<E> node(int index) { 2     // assert isElementIndex(index); 3  4     if (index < (size >> 1)) { 5       Node<E> x = first; 6       for (int i = 0; i < index; i++) 7         x = x.next; 8       return x; 9     } else {10       Node<E> x = last;11       for (int i = size - 1; i > index; i--)12         x = x.prev;13       return x;14     }15   }

  看懂了吗?程序会先判断输入的下标与中间值(size右移一位,也就是除以2了)的关系,小于中间值则从头开始正向搜索,大于中间值则从尾节点反向搜索,想想看,每一次的get方法都是一个遍历,"性能"两字从何说去呢?  

  明白了随机存取列表和有序存取列表的区别,我们的average方法就必须重构了,以便实现不同的列表采用不同的遍历方式,代码如下: 

 1 public static int average(List<Integer> scores) { 2     int sum = 0; 3  4     if (scores instanceof RandomAccess) { 5       // 可以随机存取,则使用下标遍历 6       for (int i = 0; i < scores.size(); i++) { 7         sum += scores.get(i); 8       } 9     } else {10       // 有序存取,使用foreach方式11       for (int i : scores) {12         sum += i;13       }14     }15     return sum / scores.size();16   }

  如此一来,列表的遍历就可以"以不变应万变"了,无论是随机存取列表还是有序列表,它都可以提供快速的遍历。

  注意:列表遍历不是那么简单的,适时选择最优的遍历方式,不要固化为一种。  

建议68:频繁插入和删除时使用LinkList

   上一个建议介绍了列表的遍历方式,也就是“读” 操作,本建议将介绍列表的"写"操作:即插入、删除、修改动作。

  (1)、插入元素:列表中我们使用最多的是ArrayList,下面来看看它的插入(add方法)算法,源代码如下:

 1 public void add(int index, E element) { 2     //检查下标是否越界 3     rangeCheckForAdd(index); 4     //若需要扩容,则增大底层数组的长度 5     ensureCapacityInternal(size + 1); // Increments modCount!! 6     //给index下标之后的元素(包括当前元素)的下标加1,空出index位置 7     System.arraycopy(elementData, index, elementData, index + 1, 8             size - index); 9     //赋值index位置元素10     elementData[index] = element;11     //列表长度加112     size++;13   }

  注意看arrayCopy方法,只要插入一个元素,其后的元素就会向后移动一位,虽然arrayCopy是一个本地方法,效率非常高,但频繁的插入,每次后面的元素都要拷贝一遍,效率就更低了,特别是在头位置插入元素时,现在的问题是,开发中确实会遇到要插入的元素的情况,哪有什么更好的方法解决此效率问题吗?

  有,使用LinkedList即可。我么知道LinkedList是一个双向列表,它的插入只是修改了相邻元素的next和previous引用,其插入算法(add方法)如下:

  

1 public void add(int index, E element) {2     checkPositionIndex(index);3 4     if (index == size)5       linkLast(element);6     else7       linkBefore(element, node(index));8   }

 1 void linkLast(E e) { 2     final Node<E> l = last; 3     final Node<E> newNode = new Node<>(l, e, null); 4     last = newNode; 5     if (l == null) 6       first = newNode; 7     else 8       l.next = newNode; 9     size++;10     modCount++;11   }

 1 void linkBefore(E e, Node<E> succ) { 2     // assert succ != null; 3     final Node<E> pred = succ.prev; 4     final Node<E> newNode = new Node<>(pred, e, succ); 5     succ.prev = newNode; 6     if (pred == null) 7       first = newNode; 8     else 9       pred.next = newNode;10     size++;11     modCount++;12   }

这个方法,第一步检查是否越界,下来判断插入元素的位置与列表的长度比较,如果相等,调用linkLast,否则调用linkBefore方法。但这两个方法的共同点都是双向链表插入算法,把自己插入到链表,然后再把前节点的next和后节点的previous指向自己。想想看,这样插入一个元素的过程中,没有任何元素会有拷贝过程,只是引用地址变了,那效率自然就高了。

  (2)、删除元素:插入了解清楚了,我们再来看看删除动作。ArrayList提供了删除指定位置上的元素,删除指定元素,删除一个下标范围内的元素集等删除动作。三者的实现原理基本相似,都是找索引位置,然后删除。我们以最常用的删除指定下标的方法(remove方法)为例来看看删除动作的性能到底如何,源码如下:  

 1 public E remove(int index) { 2     //下标校验 3     rangeCheck(index); 4     //修改计数器加1 5     modCount++; 6     //记录要删除的元素 7     E oldValue = elementData(index); 8     //有多少个元素向前移动 9     int numMoved = size - index - 1;10     if (numMoved > 0)11       //index后的元素向前移动一位12       System.arraycopy(elementData, index+1, elementData, index,13                numMoved);14     //列表长度减115     elementData[--size] = null; // Let gc do its work16     //返回删除的值17     return oldValue;18   }

  注意看,index位置后的元素都向前移动了一位,最后一个位置空出来了,这又是一个数组拷贝,和插入一样,如果数据量大,删除动作必然会暴露出性能和效率方面的问题。ArrayList其它的两个删除方法与此类似,不再赘述。

  我么再来看LinkedList的删除动作。LinkedList提供了非常多的删除操作,比如删除指定位置元素,删除头元素等,与之相关的poll方法也会执行删除动作,下面来看最基本的删除指定位置元素的方法remove,源代码如下: 

 public E remove(int index) {    checkElementIndex(index);    return unlink(node(index));  }

 1 E unlink(Node<E> x) { 2     // assert x != null; 3     final E element = x.item; 4     final Node<E> next = x.next; 5     final Node<E> prev = x.prev; 6  7     if (prev == null) { 8       first = next; 9     } else {10       prev.next = next;11       x.prev = null;12     }13 14     if (next == null) {15       last = prev;16     } else {17       next.prev = prev;18       x.next = null;19     }20 21     x.item = null;22     size--;23     modCount++;24     return element;25   }

 1 private static class Node<E> { 2     E item; 3     Node<E> next; 4     Node<E> prev; 5  6     Node(Node<E> prev, E element, Node<E> next) { 7       this.item = element; 8       this.next = next; 9       this.prev = prev;10     }11   }

  这也是双向链表标准删除算法,没有任何耗时的操作,全部都是引用指针的变更,效率自然高了。

  (3)、修改元素:写操作还有一个动作,修改元素值,在这一点上LinkedList输给了ArrayList,这是因为LinkedList是按顺序存储的,因此定位元素必然是一个遍历过程,效率大打折扣,我们来看Set方法的代码:  

1  public E set(int index, E element) {2     checkElementIndex(index);3     //定位节点4     Node<E> x = node(index);5     E oldVal = x.item;6     //节点元素替换7     x.item = element;8     return oldVal;9   }

  看似很简洁,但是这里使用了node方法定位元素,上一个建议中我们已经说明了LinkedList这种顺序存取列表的元素定位方式会折半遍历,这是一个极耗时的操作,而ArrayList的修改动作则是数组元素的直接替换,简单高效。

  在修改动作上,LinkedList比ArrayList慢很多,特别是要进行大量的修改时,两者完全不在一个数量级上。

  上面通过分析源码完成了LinkedList与ArrayList之间的PK,其中LinkedList胜两局:删除和插入效率高ArrayList胜一局:修改元素效率高。总体来说,在写方面LinkedList占优势,而且在实际使用中,修改是一个比较少的动作。因此有大量写的操作(更多的是插入和删除),推荐使用LinkedList。不过何为少量?何为大量呢?

  这就依赖于咱们在开发中系统了,具体情况具体分析了。

建议69:列表相等只关心元素数据

   我们来看一个比较列表相等的例子,代码如下:

 1 public class Client69 { 2   public static void main(String[] args) { 3     ArrayList<String> strs = new ArrayList<String>(); 4     strs.add("A"); 5      6     Vector<String> strs2 = new Vector<String>(); 7     strs2.add("A"); 8      9     System.out.println(strs.equals(strs2));10   }11 }

  两个类都不同,一个是ArrayList,一个是Vector,那结果肯定不相等了。真是这样吗?但其实结果为true,也就是两者相等。

  我们分析一下,两者为何相等,两者都是列表(List),都实现了List接口,也都继承了AbstractList抽象类,其equals方法是在AbstractList中定义的,我们来看源代码:

 1 public boolean equals(Object o) { 2       if (o == this) 3         return true; 4       //是否是列表,注意这里:只要实现List接口即可 5       if (!(o instanceof List)) 6         return false; 7       //通过迭代器访问List的所有元素 8       ListIterator<E> e1 = listIterator(); 9       ListIterator e2 = ((List) o).listIterator();10       //遍历两个List的元素11       while (e1.hasNext() && e2.hasNext()) {12         E o1 = e1.next();13         Object o2 = e2.next();14         //只要存在着不相等就退出15         if (!(o1==null ? o2==null : o1.equals(o2)))16           return false;17       }18       //长度是否也相等19       return !(e1.hasNext() || e2.hasNext());20     }

  看到没,这里只要实现了List接口就成,它不关心List的具体实现类,只要所有元素相等,并且长度也相等就表明两个List是相等的,与具体的容量类型无关。也就是说,上面的例子虽然一个是Arraylist,一个是Vector,只要里面的元素相等,那结果也就相等。

  Java如此处理也确实是在为开发者考虑,列表只是一个容器,只要是同一种类型的容器(如List),不用关心,容器的细节差别,只要确定所有的元素数据相等,那这两个列表就是相等的,如此一来,我们在开发中就不用太关注容器的细节了,可以把注意力更多地放在数据元素上,而且即使中途重构容器类型,也不会对相等的判断产生太大的影响。

  其它的集合类型,如Set、Map等于此相同,也是只关心集合元素,不用考虑集合类型。

  注意:判断集合是否相等时只须关注元素是否相等即可。