首页 > 代码库 > 编写高质量代码:改善Java程序的151个建议(第5章:数组和集合___建议79~82)

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

建议79:集合中的哈希码不要重复

  在一个列表中查找某值是非常耗费资源的,随机存取的列表是遍历查找,顺序存储的列表是链表查找,或者是Collections的二分法查找,但这都不够快,毕竟都是遍历嘛,最快的还要数以Hash开头的集合(如HashMap、HashSet等类)查找,我们以HashMap为例,看看是如何查找key值的,代码如下: 

 1 public class Client79 { 2     public static void main(String[] args) { 3         int size = 10000; 4         List<String> list = new ArrayList<String>(size); 5         // 初始化 6         for (int i = 0; i < size; i++) { 7             list.add("value" + i); 8         } 9         // 记录开始时间,单位纳秒10         long start = System.nanoTime();11         // 开始查找12         list.contains("value" + (size - 1));13         // 记录结束时间,单位纳秒14         long end = System.nanoTime();15         System.out.println("List的执行时间:" + (end - start) + "ns");16         // Map的查找时间17         Map<String, String> map = new HashMap<String, String>(size);18         for (int i = 0; i < size; i++) {19             map.put("key" + i, "value" + i);20         }21         start = System.nanoTime();22         map.containsKey("key" + (size - 1));23         end = System.nanoTime();24         System.out.println("map的执行时间:" + (end - start) + "ns");25     }26 }

  两个不同的集合容器,一个是ArrayList,一个是HashMap,都是插入10000个元素,然后判断是否包含最后一个加入的元素。逻辑相同,但是执行时间差别却非常大,结果如下:

  技术分享

  HahsMap比ArrayList快了两个数量级!两者的contains方法都是判断是否包含指定值,为何差距如此巨大呢?而且如果数据量增大,差距也会非线性增长。

  我们先来看看ArrayList,它的contains方法是一个遍历对比,这很easy,不多说。我们看看HashMap的ContainsKey方法是如何实现的,代码如下:

public boolean containsKey(Object key) {        //判断getEntry是否为空        return getEntry(key) != null;    }

  getEntry方法会根据key值查找它的键值对(也就是Entry对象),如果没有找到,则返回null。我们再看看该方法又是如何实现的,代码如下: 

 1 final Entry<K,V> getEntry(Object key) { 2          //计算key的哈希码 3             int hash = (key == null) ? 0 : hash(key); 4             //定位Entry、indexOf方法是根据hash定位数组的位置的 5             for (Entry<K,V> e = table[indexFor(hash, table.length)]; 6                  e != null; 7                  e = e.next) { 8                 Object k; 9                 //哈希码相同,并且键值也相等才符合条件10                 if (e.hash == hash &&11                     ((k = e.key) == key || (key != null && key.equals(k))))12                     return e;13             }14             return null;15         }

  注意看上面代码中红色字体部分,通过indexFor方法定位Entry在数组table中的位置,这是HashMap实现的一个关键点,怎么能根据hashCode定位它在数组中的位置呢?

  要解释此问题,还需要从HashMap的table数组是如何存储元素的说起,首先要说明三点:

  • table数组的长度永远是2的N次幂。
  • table数组的元素是Entry类型
  • table数组中的元素位置是不连续的

  table数组为何如此设计呢?下面逐步来说明,先来看HashMap是如何插入元素的,代码如下: 

 1 public V put(K key, V value) { 2         //null键处理 3         if (key == null) 4             return putForNullKey(value); 5         //计算hash码,并定位元素 6         int hash = hash(key); 7         int i = indexFor(hash, table.length); 8         for (Entry<K, V> e = table[i]; e != null; e = e.next) { 9             Object k;10             //哈希码相同,并且key相等,则覆盖11             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {12                 V oldValue =http://www.mamicode.com/ e.value;13                 e.value =http://www.mamicode.com/ value;14                 e.recordAccess(this);15                 return oldValue;16             }17         }18         modCount++;19         //插入新元素,或者替换哈希的旧元素并建立链表20         addEntry(hash, key, value, i);21         return null;22     }

  注意看,HashMap每次增加元素时都会先计算其哈希码值,然后使用hash方法再次对hashCode进行抽取和统计,同时兼顾哈希码的高位和低位信息产生一个唯一值,也就是说hashCode不同,hash方法返回的值也不同,之后再通过indexFor方法与数组长度做一次与运算,即可计算出其在数组中的位置,简单的说,hash方法和indexFor方法就是把哈希码转变成数组的下标,源代码如下:

 1    final int hash(Object k) { 2         int h = 0; 3         if (useAltHashing) { 4             if (k instanceof String) { 5                 return sun.misc.Hashing.stringHash32((String) k); 6             } 7             h = hashSeed; 8         } 9 10         h ^= k.hashCode();11 12         // This function ensures that hashCodes that differ only by13         // constant multiples at each bit position have a bounded14         // number of collisions (approximately 8 at default load factor).15         h ^= (h >>> 20) ^ (h >>> 12);16         return h ^ (h >>> 7) ^ (h >>> 4);17     }
1 /**2      * Returns index for hash code h.3      */4     static int indexFor(int h, int length) {5         return h & (length-1);6     }

  顺便说一下,null值也是可以作为key值的,它的位置永远是在Entry数组中的第一位。

  现在有一个很重要的问题摆在前面了:哈希运算存在着哈希冲突问题,即对于一个固定的哈希算法f(k),允许出现f(k1)=f(k2),但k1≠k2的情况,也就是说两个不同的Entry,可能产生相同的哈希码,HashMap是如何处理这种冲突问题的呢?答案是通过链表,每个键值对都是一个Entry,其中每个Entry都有一个next变量,也就是说它会指向一个键值对---很明显,这应该是一个单向链表,该链表是由addEntity方法完成的,其代码如下: 

1  void addEntry(int hash, K key, V value, int bucketIndex) {2         if ((size >= threshold) && (null != table[bucketIndex])) {3             resize(2 * table.length);4             hash = (null != key) ? hash(key) : 0;5             bucketIndex = indexFor(hash, table.length);6         }7 8         createEntry(hash, key, value, bucketIndex);9     }
 void createEntry(int hash, K key, V value, int bucketIndex) {        //取得当前位置元素        Entry<K,V> e = table[bucketIndex];       //生成新的键值对,并进行替换,建立链表        table[bucketIndex] = new Entry<>(hash, key, value, e);        size++;    }

  这段程序涵盖了两个业务逻辑,如果新加入的元素的键值对的hashCode是唯一的,那直接插入到数组中,它Entry的next值则为null;如果新加入的键值对的hashCode与其它元素冲突,则替换掉数组中的当前值,并把新加入的Entry的next变量指向被替换的元素,于是一个链表就产生了,如下图所示:

  技术分享

   HashMap的存储主线还是数组,遇到哈希码冲突的时候则使用链表解决。了解了HashMap是如何存储的,查找也就一目了然了:使用hashCode定位元素,若有哈希冲突,则遍历对比,换句话说,如果没有哈希冲突的情况下,HashMap的查找则是依赖hashCode定位的,因为是直接定位,那效率当然就高了。

  知道HashMap的查找原理,我们就应该很清楚:如果哈希码相同,它的查找效率就与ArrayList没什么两样了,遍历对比,性能会大打折扣。特别是哪些进度紧张的项目中,虽重写了hashCode方法但返回值却是固定的,此时如果把哪些对象插入到HashMap中,查找就相当耗时了。

  注意:HashMap中的hashCode应避免冲突。

建议80:多线程使用Vector或HashTable

  Vector是ArrayList的多线程版本,HashTable是HashMap的多线程版本,这些概念我们都很清楚,但我们经常会逃避使用Vector和HashTable,因为用的少,不熟嘛!只有在真正需要的时候才会想要使用它们,但问题是什么时候真正需要呢?我们来看一个例子,看看使用多线程安全的Vector是否可以解决问题,代码如下: 

 1 public class Client80 { 2     public static void main(String[] args) { 3         // 火车票列表 4         final List<String> tickets = new ArrayList<String>(100000); 5         // 初始化票据池 6         for (int i = 0; i < 100000; i++) { 7             tickets.add("火车票" + i); 8         } 9         // 退票10         Thread returnThread = new Thread() {11             @Override12             public void run() {13                 while (true) {14                     tickets.add("车票" + new Random().nextInt());15                 }16 17             };18         };19 20         // 售票21         Thread saleThread = new Thread() {22             @Override23             public void run() {24                 for (String ticket : tickets) {25                     tickets.remove(ticket);26                 }27             }28         };29         // 启动退票线程30         returnThread.start();31         // 启动售票线程32         saleThread.start();33 34     }35 }

  模拟火车站售票程序,先初始化一堆火车票,然后开始出售,同时也有退票产生,这段程序有木有问题呢?可能会有人看出了问题,ArrayList是线程不安全的,两个线程访问同一个ArrayList数组肯定会有问题。

  没错,确定有问题,运行结果如下:

  技术分享

 

 运气好的话,该异常马上就会抛出,也会会有人说这是一个典型错误,只须把ArrayList替换成Vector即可解决问题,真的是这样吗?我们把ArrayList替换成Vector后,结果依旧。仍然抛出相同的异常,Vector应经是线程安全的,为什么还会报这个错呢?

 这是因为它混淆了线程安全和同步修改异常,基本上所有的集合类都有一个快速失败(Fail-Fast)的校验机制,当一个集合在被多个线程修改并访问时,就可能出现ConcurrentModificationException异常,这是为了确保集合方法一致而设置的保护措施,它的实现原理就是我们经常提到的modCount修改计数器:如果在读列表时,modCount发生变化(也就是有其它线程修改)则会抛出ConcurrentModificationException异常,这与线程同步是两码事,线程同步是为了保护集合中的数据不被脏读、脏写而设置的,我们来看看线程安全到底用在什么地方,代码如下:

 1 public static void main(String[] args) { 2         // 火车票列表 3         final List<String> tickets = new ArrayList<String>(100000); 4         // 初始化票据池 5         for (int i = 0; i < 100000; i++) { 6             tickets.add("火车票" + i); 7         } 8         // 10个窗口售票 9         for (int i = 0; i < 10; i++) {10             new Thread() {11                 public void run() {12                     while (true) {13                         System.out.println(Thread.currentThread().getId()14                                 + "----" + tickets.remove(0));15                         if (tickets.size() == 0) {16                             break;17                         }18                     }19                 };20             }.start();21         }22     }

  还是火车站售票程序,有10个窗口在卖火车票,程序打印出窗口号(也就是线程号)和车票编号,我们很快就可以看到这样的输出:

  技术分享

 

  注意看,上面有两个线程在卖同一张火车票,这才是线程不同步的问题,此时把ArrayList修改为Vector即可解决问题,因为Vector的每个方法前都加上了synchronized关键字,同时知会允许一个线程进入该方法,确保了程序的可靠性。

  虽然在系统开发中我们一再说明,除非必要,否则不要使用synchronized,这是从性能的角度考虑的,但是一旦涉及到多线程(注意这里说的是真正的多线程,并不是并发修改的问题,比如一个线程增加,一个线程删除,这不属于多线程的范畴),Vector会是最佳选择,当然自己在程序中加synchronized也是可行的方法。

  HashMap的线程安全类HashTable与此相同,不再赘述。

建议81:非稳定排序推荐使用List

  我们知道Set和List的最大区别就是Set中的元素不可以重复(这个重复指的是equals方法的返回值相等),其它方面则没有太大区别了,在Set的实现类中有一个比较常用的类需要了解一下:TreeSet,该类实现了默认排序为升序的Set集合,如果插入一个元素,默认会按照升序排列(当然是根据Comparable接口的compareTo的返回值确定排序位置了),不过,这样的排序是不是在元素经常变化的场景中也适用呢?我们来看看例子:  

 1 public class Client81 { 2     public static void main(String[] args) { 3         SortedSet<Person> set = new TreeSet<Person>(); 4         // 身高180CM 5         set.add(new Person(180)); 6         // 身高175CM 7         set.add(new Person(175)); 8         for (Person p : set) { 9             System.out.println("身高:" + p.getHeight());10         }11     }12 13     static class Person implements Comparable<Person> {14         // 身高15         private int height;16 17         public Person(int _height) {18             height = _height;19         }20 21         public int getHeight() {22             return height;23         }24 25         public void setHeight(int height) {26             this.height = height;27         }28 29         // 按照身高排序30         @Override31         public int compareTo(Person o) {32             return height - o.height;33         }34 35     }36 }

  这是Set的简单用法,定义一个Set集合,之后放入两个元素,虽然175后放入,但是由于是按照升序排列的,所以输出结果应该是175在前,180在后。

  这没有问题,随着时间的推移,身高175cm的人长高了10cm,而180cm却保持不变,那排序位置应该改变一下吧,代码如下: 

 1 public static void main(String[] args) { 2         SortedSet<Person> set = new TreeSet<Person>(); 3         // 身高180CM 4         set.add(new Person(180)); 5         // 身高175CM 6         set.add(new Person(175)); 7         set.first().setHeight(185); 8         for (Person p : set) { 9             System.out.println("身高:" + p.getHeight());10         }11     }

  找出身高最矮的人,也就是排在第一位的人,然后修改一下身高值,重新排序了?我们看下输出结果:

  技术分享

 

  很可惜,竟然没有重现排序,偏离了我们的预期。这正是下面要说明的问题,SortedSet接口(TreeSet实现了此接口)只是定义了在给集合加入元素时将其进行排序,并不能保证元素修改后的排序结果,因此TreeSet适用于不变量的集合数据排序,比如String、Integer等类型,但不使用与可变量的排序,特别是不确定何时元素会发生变化的数据集合。

  原因知道了,那如何解决此类重排序问题呢?有两种方式:

  (1)、Set集合重排序:重新生成一个Set对象,也就是对原有的Set对象重新排序,代码如下:

         set.first().setHeight(185);        //set重排序        set=new TreeSet<Person>(new ArrayList<Person>(set));

  就这一行红色代码即可重新排序,可能有人会问,使用TreeSet<SortedSet<E> s> 这个构造函数不是可以更好的解决问题吗?不行,该构造函数只是原Set的浅拷贝,如果里面有相同的元素,是不会重新排序的。

  (2)、彻底重构掉TreeSet,使用List解决问题

    我们之所以使用TreeSet是希望实现自动排序,即使修改也能自动排序,既然它无法实现,那就用List来代替,然后使用Collections.sort()方法对List排序,代码比较简单,不再赘述。

  两种方式都可以解决我们的问题,如果需要保证集合中元素的唯一性,又要保证元素值修改后排序正确,那该如何处理呢?List不能保证集合中的元素唯一,它是可以重复的,而Set能保证元素唯一,不重复。如果采用List解决排序问题,就需要自行解决元素重复问题(若要剔除也很简单,转变为HashSet,剔除后再转回来)。若采用TreeSet,则需要解决元素修改后的排序问题,孰是孰非,就需要根据具体的开发场景来决定了。

  注意:SortedSet中的元素被修改后可能会影响到其排序位置。

建议82:由点及面,集合大家族总结

  Java中的集合类实在是太丰富了,有常用的ArrayList、HashMap,也有不常用的Stack、Queue,有线程安全的Vector、HashTable,也有线程不安全的LinkedList、TreeMap,有阻塞式的ArrayBlockingQueue,也有非阻塞式的PriorityQueue等,整个集合大家族非常庞大,可以划分以下几类:

  (1)、List:实现List接口的集合主要有:ArrayList、LinkedList、Vector、Stack,其中ArrayList是一个动态数组,LinkedList是一个双向链表,Vector是一个线程安全的动态数组,Stack是一个对象栈,遵循先进后出的原则。  

  (2)、Set:Set是不包含重复元素的集合,其主要实现类有:EnumSet、HashSet、TreeSet,其中EnumSet是枚举类型专用Set,所有元素都是枚举类型;HashSet是以哈希码决定其元素位置的Set,其原理与HashMap相似,它提供快速的插入和查找方法;TreeSet是一个自动排序的Set,它实现了SortedSet接口。

  (3)、Map:Map是一个大家族,他可以分为排序Map和非排序Map,排序Map主要是TreeMap类,他根据key值进行自动排序;非排序Map主要包括:HashMap、HashTable、Properties、EnumMap等,其中Properties是HashTable的子类,它的主要用途是从Property文件中加载数据,并提供方便的操作,EnumMap则是要求其Key必须是某一个枚举类型。

   Map中还有一个WeakHashMap类需要说明,  它是一个采用弱键方式实现的Map类,它的特点是:WeakHashMap对象的存在并不会阻止垃圾回收器对键值对的回收,也就是说使用WeakHashMap装载数据不用担心内存溢出的问题,GC会自动删除不用的键值对,这是好事。但也存在一个严重的问题:GC是静悄悄的回收的(何时回收,God,Knows!)我们的程序无法知晓该动作,存在着重大的隐患。

  (4)、Queue:对列,它分为两类,一类是阻塞式队列,队列满了以后再插入元素会抛出异常,主要包括:ArrayBlockingQueue、PriorityQueue、LinkedBlockingQueue,其中ArrayBlockingQueue是一个以数组方式实现的有界阻塞队列;另一类是非阻塞队列,无边界的,只要内存允许,都可以持续追加元素,我们经常使用的是PriorityQuene类。

  还有一种队列,是双端队列,支持在头、尾两端插入和移除元素,它的主要实现类是:ArrayDeque、LinkedBlockingDeque、LinkedList。

  (5)、数组:数组与集合的最大区别就是数组能够容纳基本类型,而集合就不行,更重要的一点就是所有的集合底层存储的都是数组。

  (6)、工具类:数组的工具类是java.util.Arrays和java.lang.reflect.Array,集合的工具类是java.util.Collections,有了这两个工具类,操作数组和集合就会易如反掌,得心应手。

  (7)、扩展类:集合类当然可以自行扩展了,想写一个自己的List?没问题,但最好的办法还是"拿来主义",可以使用Apache的common-collections扩展包,也可以使用Google的google-collections扩展包,这些足以应对我们的开发需要。

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