首页 > 代码库 > 改善java程序的151个建议--数组和集合
改善java程序的151个建议--数组和集合
60、性能考虑,数组是首选,在基本类型处理方面。数组还是占优势的,并且集合类的底层也都是通过数组实现。建议在性能要求较高的场景中使用数组替代集合。
61、假设有必要。使用变长数组:我们能够通过对数组扩容”婉转”地解决数组扩容问题。以下採用的是Arrays数组工具类的copyOf方法。产生了一个newLen长度的新数组,并把原有的值拷贝了进去,之后就能够对超长的元素进行赋值了
62、警惕数组的浅拷贝
Person[] p=new Person[5];
Person[] p2=Arrays.copyOf(p,p.length);
假设改动了p2中某个属性的值。比如p2中username的值,那么p也会改动,这就是所说的浅拷贝。解决方案是:遍历p,然后又一次生成一个Person放入p2中,这就实现了深拷贝,我们在使用集合的时候,比如List,应该避免这种使用方式:Arrays.copyOf(list.toArray());
63、在明白的场景下,为集合指定初始容量
ArrayList是一个大小可变的数组,但它在底层使用的是数组存储,并且数组是定长的。要实现动态长度必要要进行长度的扩展。底层实现是在元素达到elementData长度的临界点时。将elementData扩容1.5倍,为什么是1.5倍呢,这是由于经过測试验证,扩容1.5倍即满足了性能要求,也降低了内存消耗,源码例如以下:
接下来我们看一下ArrayList的构造函数例如以下:
上面是无參数构造。以下是指定容量的有參函数构造,假设我们不设置容量,系统就依照1.5倍的规则扩容,每次扩容都是一次数组的拷贝,假设数据量很大,这种拷贝会很耗费资源。并且效率很低下。假设我们已经知道了一个ArrayList的可能长度,尽量避免了数组拷贝,然后对其设置一个初始容量则能够显著提高系统性能。其它集合都一样。以下是Vector底层数组的长度计算方式:
64、多种最值算法,适时选择
1)自行实现,高速查找最大值
2)先排序。后取值,以下数组使用了clone方法的主要原因是不影响原数组中的排序
3)查找仅次于最大值的元素
最值计算时。使用集合最简单,使用数组性能最优;
65、避开基本类型数组转换列表的陷进
int[] data=http://www.mamicode.com/{1,2,3,4,5};List list=Arrays.asList(data);list.size()得到的结果为1,这是由于asList的方法接收的是一个变长參数,返回一个固定长度的列表,其源码例如以下:
数组是一个对象,它是能够泛型化的。也就是说这里把一个int类型的数组作为了T类型。所以转换后在List中就仅仅有一个类型为int数组的元素了。改动方案是将int改为Integer
Integer[] data=http://www.mamicode.com/{1,2,3,4,5};List list=Arrays.asList(data);list.size()得到的结果为5
结论:原始类型数组不能作为asList的输入參数,否则会引起程序逻辑混乱。
66、asList方法产生的List对象不可更改
看以下一段程序:
public static void main(String[] args) { Integer[] datas={1,2,3,4}; List<Integer> list=Arrays.asList(datas); list.add(6); }
执行结果抛出:UnsupportedOperationException。原因是此asList底层实现是返回了一个ArrayList,此ArrayList并非java.util.ArrayList,而是Arrays工具类的一个静态私有内部类。除了Arrays能訪问外,其它类都不能訪问,这个类中没有提供add方法,其父类AbstractList提供的add方法中抛出该异常,它只实现了5个方法:size()、toArray()、get()、set()、contains()。asList返回的是一个长度不可变的列表,数组是多长,转换成的列表也就是多长,换句话说,此处的列表不过数组的一个外壳。不再保持列表动态变长的特性,所以很不推荐例如以下方式定义和初始化列表:
List<String> list=Arrays.asList(“abc”,”ddd”,”sss”);这个list仅仅能进行读操作
67、不同的列表选择不同的遍历方法
我们有这样一个需求。将100万数据放入ArrayList和LinkedList中。然后分别通过foreach的方式和遍历下标的方式进行求和并计算平均值运算,得出结果例如以下:
通过ArrayList下标遍历耗时:2ms,得出平均值为:49
通过ArrayList foreach遍历耗时:6ms,得出平均值为:49
通过LinkedList下标遍历耗时:5515ms,得出平均值为:49
通过LinkedList foreach遍历耗时:3ms,得出平均值为:49
我们能够知道,通过下标遍历的方式:for(int i=0,size=list.size();i<size;i++)对照,ArrayList的效率远远比LinkedList的效率要高,而通过foreach遍历的方式:for(Integer i:list)对照,LinkedList的效率比ArrayList好。这是由于ArrayList实现了RandomAccess接口(随机存取接口),也就标志着ArrayList是一个能够随机存取的列表。也就说明了当中的数据元素之间是没有关联的,即两个位置相邻的元素之间没有相互依赖和索引关系,能够随机訪问和存储,而使用迭代器就须要强制建立一种相互关系,比方上一个元素能够推断是否有下一个元素。以及下一个元素是什么等等,所以使用ArrayList通过foreach遍历须要为其加入关系。这就是耗时的原因。
LinkedList它底层实现了双向链表,当中的两个元素本来就是有关联的,所以使用foreach会效率会比較高。通过底层代码会发现,LinkedList的get方法会每次都会进行一次遍历,所以效率很低。
上面说的就是随机存储列表(比如ArrayList)和有序存取列表(比如LinkedList)的差别。随机存储列表。实现了RandomAccess接口,使用下标遍历的方式效率高,有序存储列表,其元素之间本来就存在关系,使用foreach遍历的方式效率高,我们能够写一个万能遍历方式:
public static void searchQuick(List<Integer> list,String listName){ int sum=0; String str=""; long startTime=System.currentTimeMillis(); if(list instanceof RandomAccess){ str+=listName+"随机存储,使用下标遍历方式最快"; for(int i=0,size=list.size();i<size;i++){ sum+=list.get(i); } }else{ str+=listName+"有序存储。使用foreach遍历方式最快"; for(Integer i:list){ sum+=i; } } long endTime=System.currentTimeMillis(); System.out.println(str+",遍历耗时:"+(endTime-startTime)+"ms,得出平均值为:"+sum/list.size()); }
【知识拓展】RandomAccess和Cloneable、Serializable一样。都是标志性接口,不须要不论什么实现,仅仅是用来表明事实上现类具有某种特质的。实现了Cloneable表明能够被拷贝,实现了Serializable表明能够被序列化,实现了Serializable表明这个类能够进行随机存储(元素间没有关系,能够随机訪问和存储)。
68、频繁插入和删除时使用LinkedList
在指定位置插入元素:add(int index,E element)
ArrayList:底层是数组实现,每次插入一个元素。其后的元素就会向后移动一位。效率比較低
LinkedList:底层是一个双向链表,它的插入仅仅是改动相邻元素的next和previous的引用,效率高
删除元素:remove(int index),和上面一样,LinkedList效率比ArrayList高
改动元素:set(int index,E element),ArrayList比LinkedList效率高,由于LinkedList是顺序存储的。定位元素是一个折半遍历过程。比較耗时,效率低,ArrayList的改动动作则是数组元素的直接替换。简单高效。
添加元素:add(E elment);ArrayList和LinkedList在性能上基本没什么区别
综上所述。适当的场景选择适当的集合操作
69、列表相等仅仅需关心元素数据
ArrayList<String> strs=new ArrayList<String>(); strs.add("abc"); Vector<String> strs2=new Vector<String>(); strs2.add("abc"); LinkedList<String> strs3=new LinkedList<String>(); strs3.add("abc"); System.out.println(strs.equals(strs2)); System.out.println(strs.equals(strs3)); System.out.println(strs2.equals(strs3));
如上程序,程序输出的结果都是true,这是由于这三个列表都实现了List接口,也都继承了AbstractList抽象类。其equals方法是在AbstractList中定义的,源码例如以下:
从源码中能够看出。仅仅要求实现了List接口就成。它不关心List的详细实现类,仅仅要全部的元素相等,而且长度也相等就表明两个List是相等的。与详细的容量类型无关。其它的集合类型。如Set、Map也几乎相同,仅仅关心集合元素,不用考虑集合类型。
推断集合是否相等时仅仅须关注元素是否相等就可以。
70、子列表仅仅是原列表的一个视图。subList产生的列表仅仅是原列表的一个视图,全部的修修改作直接作用于原列表
看以下的程序:
List<String> list1=new ArrayList<String>(); list1.add("A"); list1.add("B"); //构造一个包括list1列表的字符串列表 List<String> list2=new ArrayList<String>(list1); System.out.println(list1.equals(list2)); //使用subList生成与list1同样的列表 List<String> list3=list1.subList(0, list1.size()); System.out.println(list1.equals(list3)); //list3中添加一个元素 list3.add("C"); System.out.println(list1);//A、B、C System.out.println(list3);//A、B、C System.out.println(list1.equals(list2)); System.out.println(list1.equals(list3));
上面的结果输出为:true、true、false、true,前两个我们都知道,那么后面两个为什么会出现这种结果呢!
这是由于通过subList生成的List是原有List的一个视图。也就是说list3是list1的一个视图。对list3的全部的修修改作都会反映在原列表list1上。所以上面中list3添加一个元素C的时候,此时list1也会添加一个C,list1和list3保持一致,自然而然就相等了;通过ArrayList构造函数创建的list2实际上它是一个新列表了,它是通过数组的copyOf(浅拷贝)生成的,生成的list2和原列表list1之间没有不论什么关系了
71、推荐使用subList处理局部列表
需求:一个列表有100个元素。如今要删除索引位置为20到30的元素,我们除了使用循环遍历进行删除外,还能够使用subList进行删除:
list.subList(20,30).clear();由于subList生成的List是原列表的一个视图,全部对subList生成List的操作都会作用到原列表
72、生成子列表后不要再操作原列表。保持原列表的仅仅读状态
以下代码:
List<String> list1=new ArrayList<String>(); list1.add("A"); list1.add("B"); list1.add("C"); List<String> list2=list1.subList(0, 1); list2.add("D"); System.out.println(list1.size()); System.out.println(list2.size());
在运行list2.size()的时候会抛出ConcurrentModificationException(并发改动异常)。这是由于对原列表list1进行改动后(添加一个元素D),list2取出的列表不会又一次生成一个新列表,后面对子列表list2进行操作时,就会检測到改动计数器与预期的不同。于是就抛出了并发改动异常。子列表提供的size方法中检查改动计数器源码:
subList的其它方法也检測改动计数器,比如set、get、add等方法,若生成子列表后,再改动原列表,这些方法也会抛出ConcurrentModificationException异常
对于子列表操作,由于视图是动态生成的。生成子列表后再操作原列表,必定会导致”视图”的不稳定,最有效的办法就是通过Collections.unmodifiableList方法设置列表为仅仅读状态(防御式编程):
我们的List能够有多个视图,就是说能够有多个子列表,仅仅要生成的子列表多于一个。则不论什么一个子列表就都不能改动了。否则就会抛出上面的异常。
List<String> list1=new ArrayList<String>(); list1.add("A"); list1.add("B"); list1.add("C"); //表示list1仅仅读 list1=Collections.unmodifiableList(list1); //仅仅读后不能对list1进行写入操作,抛出 //ConcurrentModificationException list1.add("F"); //有多个子列表 List<String> list2=list1.subList(0, 1); List<String> list3=list1.subList(0, 2); //多个子列表,就不能对不论什么子列表进行写入操作了 list3.add("G"); //抛出ConcurrentModificationException System.out.println(list2.size());
73、使用Comparator、Comparable进行排序
我们创建Employee默认让其能够依照id进行排序。实现代码例如以下:
class Employee implements Comparable<Employee>{ private int id; private String name; public Employee(int id,String name){ this.id=id; this.name=name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public int compareTo(Employee e) { System.out.println("execute compareTo"); Integer eId=Integer.valueOf(this.id); return eId.compareTo(Integer.valueOf(e.getId())); }}
測试代码例如以下:
List<Employee> list=new ArrayList<Employee>(); list.add(new Employee(100,"Mary")); list.add(new Employee(99,"Jack")); list.add(new Employee(101,"Lucy")); list.add(new Employee(103,"John")); list.add(new Employee(102,"Tom")); //运行排序。调用Employee默认排序compareTo方法 Collections.sort(list); for(Employee e:list){ System.out.println("id="+e.getId()+",name="+e.getName()); }
执行后的结果是依照id进行升序排序的,在測试的时候,调用Collections.sort()方法会执行Employee中的compareTo方法
假设我们进行需求改进,须要对Employee中的name进行排序,那么我们该怎么处理呢,当然我们能够改动源码,可是更好的处理方式是我们定义一个comparator,然后调用Collections.sort(List list,Comparator);重载方法,编写我们的NameComparator:
/** * 依照名称进行排序 * @author dell * */class NameComparator implements Comparator<Employee>{ @Override public int compare(Employee e1, Employee e2) { System.out.println("execute NameComparator"); return e1.getName().compareTo(e2.getName()); }}
測试:測试结果为依照名称的升序进行排序
//依照名称自己定制排序。实现Comparator接口,默认排序不会被运行 Collections.sort(list,new NameComparator()); for(Employee e:list){ System.out.println("id="+e.getId()+",name="+e.getName()); }
Comparable与Comparator:实现了Comparable接口的类表明自身是能够进行比較的,有了比較才干进行排序。而Comparator接口是一个工具类接口,它的名字也已经表明其作用:用作比較,它与原有类的逻辑没有关系,仅仅是实现两个类的比較逻辑;Comparable接口能够作为实现类的默认排序法,一个类仅仅能有一个固定的、由compareTo方法提供的默认排序算法;Comparator接口则是一个类的扩展排序工具。一个类能够有非常多的比較器
74、不推荐使用binarySearch对列表进行检索
情景。我们须要在List中查找出一个元素的索引。我们能够通过indexOf的方式进行查询,也能够通过binarySearch的方式进行检索。仅仅是通过binarySearch进行检索的时候存在List中的元素必须是有序的。否则会出错。这就可能会打乱了我们实际从数据库或者web等查询出来的集合数据,可是使用binarySearch检索性能高、效率快。所以我们有类似需求的时候我们得依据实际场景来决定使用的方法。
75、集合中的元素必须做到compareTo与equals同步
我们在进行indexOf和binarySearch方法进行索引查找的时候。假设compareTo中的比較与equals方法中的比較不一致。比如compareTo中比較的是id属性。而equals中比較的是name属性,那么就会造成结果不一样。这是由于:
indexOf是通过equals方法推断的。equals等于true就觉得找到符合条件的元素,而binarySearch查找的根据是compareTo方法的返回值,返回0即觉得找到符合条件的元素。假设我们覆写这两个方法的时候不一致。就会出现故障;equals是推断元素是否相等,compareTo是推断元素在排序中的位置是否同样,所以我们就应该保证当排序位置同样的时候。其equals也同样。实现了compareTo方法,就应该覆写equals方法。确保两者同步,否则就会产生逻辑混乱
76、集合运算时使用更优雅的方式
集合的交集、并集、差集的操作在持久层中使用得很频繁,从数据库中取出的就是多个数据集合,之后我们能够使用集合中的各种方法构建我们须要的数据,须要两个集合的and结构。就是交集,须要两个集合的or结果,那就是并集。须要两个集合的not结果,那就是差集
集合求并集:list1.addAll(list2);
集合求交集:list1.retainAll(list2);
集合求差集:属于list1但不属于list2:list1.removeAll(list2);
无反复的并集:1、删除list1中出现的元素:list2.remove(list1);2、把剩余的list2元素加入到list1中:list1.addAll(list2);
77、使用shuffle打乱列表
当我们要对List集合中的元素进行顺序打乱的时候,我们可能会想到通过一个随机数,然后遍历List集合,将元素与随机元素交换顺序:
事实上我们还能够使用一个方法非常方便的来实现上面的乱序操作:
Collections.shuffle(List list);我们能够依据项目适当的场景来使用此功能
78、降低HashMap中元素的数量
HashMap在底层比ArrayList多了一层Entry的对象封装,多占用了内存。而且它的扩容策略是2倍长度的递增,同一时候还会依据阀值推断规则进行推断。因此相对于ArrayList来说。大量加入数据会先出现内存溢出,所以尽量让HashMap中的元素少量并简单
79、集合中的哈希码不要反复
一个列表查找某值是非常耗资源的。随机存储的列表是遍历查找,顺序存储列表是链表查找。或者是Collections的二分法查找,可是这都不怎么快,最快的还是要数Hash开头的集合。比如HashMap、HashSet等等的查找。比如我们相同在ArrayList和HashMap加入100000个元素,当我们使用contains方法进行查找最后一个值的时候,会发现HashMap的效率比ArrayList高出非常多
HashMap的查找原理:当中使用hashCode定位元素。如有哈希冲突,则遍历对照,在没有哈希冲突的情况下,HashMap的查找则是依赖hashCode定位的,由于是直接定位。效率当然就高;假设哈希码同样,它的查找效率就与ArrayList没什么两样了,所以在一些项目中,尽管我们重写了hashCode方法可是返回值确是固定的,此时假设把这些对象插入到HashMap中,查找就会比較耗时了,在HashMap中的hashCode应避免冲突。
80、多线程环境下考虑使用Vector或HashTable
我们这里须要理解两个概念:线程安全和同步改动的问题
同步改动:多个线程对同一对象不同方法进行操作,比如add和remove。并发改动:一个线程添加,一个线程删除。这不属于多线程
/** * 这属于同步改动问题,不是线程同步,多个线程訪问同一对象的不同的方法 * ArrayList和Vector都会抛出ConcurrentModificationException异常 * @param datas */ public static void synchroUpdate(final List<String> datas){ Thread addThread=new Thread(){ @Override public void run() { while(true){ datas.add("新增:"+new Random().nextInt()); } } }; //降低 Thread removeThread=new Thread(){ @Override public void run() { for(String str:datas){ datas.remove(str); } } }; addThread.start(); removeThread.start(); }
线程安全:多个线程对同一对象的同一个方法进行操作,比如多个线程訪问remove方法
/** * 多线程问题,多个线程訪问同一对象的同一个方法 * 假设使用ArrayList,则datas.remove(0)可能会取出相同的数据。这是线程不安全所造成的,我们能够使用synchronized解决 * 假设使用Vector,由于它是线程安全的,所以datas.remove(0)不会出现相同的数据,它的内部实现已经使用了synchronized * @param datas */ public static void mulThread(final List<String> datas){ for(int i=0;i<10;i++){ new Thread(){ public void run() { while(true){ System.out.println(Thread.currentThread().getId()+"--"+datas.remove(0)); } }; }.start(); } }
系统开发过程中,除非必要,否则不要使用synchronizedkeyword,这是从性能的角度考虑的,可是一旦涉及多线程的时候(这里说的是真正的多线程。而不是并发改动的问题,比方一个线程添加,一个线程删除,这不是多线程)。Vector、HashTable会是最佳的选择,使用ArrayList和HashMap结合synchronized也是可行的方法。
81、SortedSot中的元素被改动后可能会影响其排序位置,非稳定排序推荐使用List
非稳定:不确定集合中的元素何时会发生变化
TreeSet:实现了类默认排序为升序的Set集合,当中的元素不能反复,TreeSet实现了SortedSet接口,它仅仅是定义了在给集合增加元素时将其进行排序,不能保证元素改动后的排序结果。因此TreeSet适用于不变量的集合数据排序。比如String、Integer等类型。但不适用于可变量的排序,特别是不确定何时元素会发生变化的数据集合,改动后的TreeSet再排序解决方式:
New TreeSet<Person>(new ArrayList<Person>(TreeSet set));
List:实现自己主动排序,即使改动也能进行自己主动排序。我们能够使用Collections.sort方法对List进行排序。可是List中的元素是能够反复的
对应排序选择对应的解决方式!
82、集合大家族
List:集合中元素可反复
ArrayList:一个动态数组
LinkedList:一个双向链表
Vector:一个线程安全的动态数组
Stack:一个对象栈,遵循先进后出的原则
Set:集合中元素不能反复
EnumSet:枚举类型的专用Set。当中全部元素都是枚举类型
HashSet:是以哈希码决定其元素位置的Set,原理与HashMap相似,提供高速的插入和查找方法
TreeSet:是一个自己主动排序的Set,它实现了SortedSet接口
Map:键值集合
排序Map:TreeMap。它依据Key值进行自己主动排序
非排序Map:HashMap、HashTable、Propertie、EnumMap,当中Properties是HashTable的子类。它的用途是从Property文件里载入数据。并提供方便的读写操作;EnumMap是要求其Key必须是某一个枚举类型
WeakHashMap:是一个採用弱键方式实现的Map类。它的特点是:WeakHashMap对象的存在并不会阻止垃圾回收器对键值对的回收,使用其装载数据不用操心内存溢出问题,GC会自己主动删除不用的键值对,可是GC是悄悄回收的,程序不知该动作,所以存在重大的隐患
Queue:
堵塞式队列:队列满了以后再插入元素则会抛出异常。当中主要有:
ArrayBlockingQueue:一个以数组方式实现的有界堵塞队列
PriorityBlockingQueue:按照优先级组建的队列
LinkedBlockingQueue:通过链表实现的堵塞队列
非堵塞队列:无边界的,仅仅要内存同意,都能够持续追加元素,最常使用的是PriorityQueue
双端队列,支持在头、尾两端插入和移出元素:ArrayDeque、LinkedBlockingDeque、LinkedList
数组:数组和集合最大的差别就是数组可以容纳基本类型,而集合就不行,它容纳的基本类型数据也是通过该java装箱转换为对象类型放进去的。全部的集合底层存储的都是数组
工具类:
数组工具类:java.util.Arrays、java.lang.reflect.Array
集合工具类:java.util.Collections
扩展类:集合类我们能够自行扩展。最好的办法是拿来主义。能够使用Apache中的commons-collections扩展包,也能够使用Google中的google-collections这些优秀的数据集合扩展包
改善java程序的151个建议--数组和集合