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

阿赫瓦里
2016-09-23
原文

建议75：集合中的元素必须做到compareTo和equals同步

　　实现了Comparable接口的元素就可以排序，compareTo方法是Comparable接口要求必须实现的，它与equals方法有关系吗?有关系，在compareTo的返回为0时，它表示的是进行比较的两个元素时相等的。equals是不是也应该对此作出相应的动作呢？我们看如下代码：

 class City implements Comparable<City> {<br/>
     private String code;

     private String name;

     public City(String _code, String _name) {<br/>
         code = _code;<br/>
         name = _name;<br/>
     }<br/>
     //code、name的setter和getter方法略<br/>
     @Override<br/>
     public int compareTo(City o) {<br/>
         //按照城市名称排序<br/>
         return new CompareToBuilder().append(name, o.name).toComparison();<br/>
     }

     @Override<br/>
     public boolean equals(Object obj) {<br/>
         if (null == obj) {<br/>
             return false;<br/>
         }<br/>
         if (this == obj) {<br/>
             return true;<br/>
         }<br/>
         if (obj.getClass() == getClass()) {<br/>
             return false;<br/>
         }<br/>
         City city = (City) obj;<br/>
         // 根据code判断是否相等<br/>
         return new EqualsBuilder().append(code, city.code).isEquals();<br/>
     }

 }

　　我们把多个城市对象放在一个list中，然后使用不同的方法查找同一个城市，看看返回值有神么异常？代码如下：

     public static void main(String[] args) {<br/>
         List<City> cities = new ArrayList<City>();<br/>
         cities.add(new City("021", "上海"));<br/>
         cities.add(new City("021", "沪"));<br/>
         // 排序<br/>
         Collections.sort(cities);<br/>
         // 查找对象<br/>
         City city = new City("021", "沪");<br/>
         // indexOf方法取得索引值<br/>
         int index1 = cities.indexOf(city);<br/>
         // binarySearch查找索引值<br/>
         int index2 = Collections.binarySearch(cities, city);<br/>
         System.out.println(" 索引值(indexOf) :" + index1);<br/>
         System.out.println(" 索引值(binarySearch) :" + index2);<br/>
     }

　　输出的index1和index2应该一致吧，都是从一个列表中查找相同的元素，只是使用的算法不同嘛。但是很遗憾，结果不一致：

　　indexOf返回的是第一个元素，而binarySearch返回的是第二个元素(索引值为1)，这是怎么回事呢？

　　这是因为indexOf是通过equals方法判断的，equals方法等于true就认为找到符合条件的元素了，而binarySearch查找的依据是compareTo方法的返回值，返回0即认为找到符合条件的元素了。

　　仔细审查一下代码，我们覆写了compareTo和equals方法，但是两者并不一致。使用indexOf方法查找时，遍历每个元素，然后比较equals方法的返回值，因为equals方法是根据code判断的，因此当第一次循环时，equals就返回true，indexOf方法结束，查找到指定值。而使用binarySearch二分法查找时，依据的是每个元素的compareTo方法返回值，而compareTo方法又是依赖属性的，name相等就返回0，binarySearch就认为找到元素了。

　　问题明白了，修改很easy，将equals方法修改成判断name是否相等即可，虽然可以解决问题，但这是一个很无奈的办法，而且还要依赖我们的系统是否支持此类修改，因为逻辑已经发生了很大的变化，从这个例子，我们可以理解两点：

indexOf依赖equals方法查找，binarySearch则依赖compareTo方法查找；
equals是判断元素是否相等，compareTo是判断元素在排序中的位置是否相同。

　　既然一个决定排序位置，一个是决定相等，那我们就应该保证当排序相同时，其equals也相同，否则就会产生逻辑混乱。

　　注意：实现了compareTo方法就应该覆写equals方法，确保两者同步。

建议76：集合运算时使用最优雅方式

　　在初中代数中，我们经常会求两个集合的并集、交集、差集等，在Java中也存在着此类运算，那如何实现呢？一提到此类集合操作，大部分的实现者都会说：对两个集合进行遍历，即可求出结果。是的。遍历可以实现并集、交集、差集等运算，但这不是最优雅的处理方式，下面来看看如何进行更优雅、快速、方便的集合操作：

　　(1)、并集：也叫作合集，把两个集合加起来即可，这非常简单，代码如下：　　　

 public static void main(String[] args) {<br/>
         List<String> list1 = new ArrayList<String>();<br/>
         list1.add("A");<br/>
         list1.add("B");<br/>
         List<String> list2 = new ArrayList<String>();<br/>
         list2.add("C");<br/>
         // 并集<br/>
         list1.addAll(list2);<br/>
     }

　　(2)、交集：计算两个集合的共有元素，也就是你有我也有的元素集合，代码如下：

//交集<br/>
list1.retainAll(list2);

　　其中的变量list1和list2是两个列表，仅此一行，list1中就只包含了list1、list2中共有的元素了，注意retailAll方法会删除list1中没有出现在list2中的元素。

　　(3)、差集：由所有属于A但不属于B的元素组成的集合，叫做A与B的差集，也就是我有你没有的元素，代码如下：

//差集<br/>
list1.removeAll(list2);

　　也很简单，从list1中删除出现在list2中的元素，即可得出list1和list2的差集部分。

　　(4)、无重复的并集：并集是集合A加集合B，那如果集合A和集合B有交集，就需要确保并集的结果中只有一份交集，此为无重复的并集，此操作也比较简单，代码如下：

        //删除在list1中出现的元素<br/>
        list2.removeAll(list1);<br/>
        //把剩余的list2元素加到list1中<br/>
        list1.addAll(list2);

　　可能有人会说，求出两个集合的并集，然后转成hashSet剔除重复元素不就解决了吗？错了，这样解决是不行的，比如集合A有10个元素(其中有两个元素值是相同的)，集合B有8个元素，它们的交集有两个元素，我们可以计算出它们的并集是18个元素，而无重复的并集有16个元素，但是如果用hashSet算法，算出来则只有15个元素，因为你把集合A中原本就重复的元素也剔除了。

　　之所以介绍并集、交集、差集，那是因为在实际开发中，很少有使用JDK提供的方法实现集合这些操作，基本上都是采用了标准的嵌套for循环：要并集就是加法，要交集就是contains判断是否存在，要差集就使用了!contains（不包含），有时候还要为这类操作提供了一个单独的方法看似很规范，其实应经脱离了优雅的味道。

　　集合的这些操作在持久层中使用的非常频繁，从数据库中取出的就是多个数据集合，之后我们就可以使用集合的各种方法构建我们需要的数据，需要两个集合的and结果，那是交集，需要两个集合的or结果，那是并集，需要两个集合的not结果，那是差集。

建议77：使用shuffle打乱列表

　　在网站上，我们经常会看到关键字云(word cloud)和标签云(tag cloud)，用于表达这个关键字或标签是经常被查阅的，而且还可以看到这些标签的动态运动，每次刷新都会有不一样的关键字或标签，让浏览者觉得这个网站的访问量很大，短短的几分钟就有这么多的搜索量。不过，在Java中该如何实现呢？代码如下：　　

 public static void main(String[] args) {<br/>
         int tagCloudNum = 10;<br/>
         List<String> tagClouds = new ArrayList<String>(tagCloudNum);<br/>
         // 初始化标签云，一般是从数据库读入，省略<br/>
         Random rand = new Random();<br/>
         for (int i = 0; i < tagCloudNum; i++) {<br/>
             // 取得随机位置<br/>
             int randomPosition = rand.nextInt(tagCloudNum);<br/>
             // 当前元素与随机元素交换<br/>
             String temp = tagClouds.get(i);<br/>
             tagClouds.set(i, tagClouds.get(randomPosition));<br/>
             tagClouds.set(randomPosition, temp);<br/>
         }<br/>
     }

　　现从数据库中读取标签，然后使用随机数打乱，每次产生不同的顺序，嗯，确实能让浏览者感觉到我们的标签云顺序在变化—浏览者多嘛！但是，对于乱序处理我们可以有更好的实现方式，先来修改第一版：

 public static void main(String[] args) {<br/>
         int tagCloudNum = 10;<br/>
         List<String> tagClouds = new ArrayList<String>(tagCloudNum);<br/>
         // 初始化标签云，一般是从数据库读入，省略<br/>
         Random rand = new Random();<br/>
         for (int i = 0; i < tagCloudNum; i++) {<br/>
             // 取得随机位置<br/>
             int randomPosition = rand.nextInt(tagCloudNum);<br/>
             // 当前元素与随机元素交换<br/>
             Collections.swap(tagClouds, i, randomPosition);<br/>
         }<br/>
     }

　　上面使用了Collections的swap方法，该方法会交换两个位置的元素值，不用我们自己写交换代码了。难道乱序到此就优化完了吗？没有，我们可以继续重构，第二版如下：

     public static void main(String[] args) {<br/>
         int tagCloudNum = 10;<br/>
         List<String> tagClouds = new ArrayList<String>(tagCloudNum);<br/>
         // 初始化标签云，一般是从数据库读入，省略<br/>
         //打乱顺序<br/>
         Collections.shuffle(tagClouds);<br/>
     }

　这才是我们想要的结果，就这一行，即可打乱一个列表的顺序，我们不用费尽心思的遍历、替换元素了。我们一般很少用到shuffle这个方法，那它在什么地方用呢？

可用在程序的 “伪装” 上：比如我们例子中的标签云，或者是游侠中的打怪、修行、群殴时宝物的分配策略。
可用在抽奖程序中：比如年会的抽奖程序，先使用shuffle把员工顺序打乱，每个员工的中奖几率相等，然后就可以抽出第一名、第二名。
可以用在安全传输方面：比如发送端发送一组数据，先随机打乱顺序，然后加密发送，接收端解密，然后进行排序，即可实现即使是相同的数据源，也会产生不同密文的效果，加强了数据的安全性。

建议78：减少HashMap中元素的数量　

　　本建议是说HahMap中存放数据过多的话会出现内存溢出，代码如下：　　

     public static void main(String[] args) {<br/>
         Map<String, String> map = new HashMap<String, String>();<br/>
         List<String> list = new ArrayList<String>();<br/>
         final Runtime rt = Runtime.getRuntime();<br/>
         // JVM中止前记录信息<br/>
         rt.addShutdownHook(new Thread() {<br/>
             @Override<br/>
             public void run() {<br/>
                 StringBuffer sb = new StringBuffer();<br/>
                 long heapMaxSize = rt.maxMemory() >> 20;<br/>
                 sb.append(" 最大可用内存：" + heapMaxSize + " M\n");<br/>
                 long total = rt.totalMemory() >> 20;<br/>
                 sb.append(" 堆内存大小：" + total + "M\n");<br/>
                 long free = rt.freeMemory() >> 20;<br/>
                 sb.append(" 空闲内存：" + free + "M");<br/>
                 System.out.println(sb);<br/>
             }<br/>
         });<br/>
         for (int i = 0; i < 40*10000; i++) {<br/>
             map.put("key" + i, "value" + i);<br/>
 //            list.add("list"+i);<br/>
         }<br/>
     }

　　这个例子，我经过多次运算，发现在40万的数据并不会内存溢出，如果要复现此问题，需要修改Eclipse的内存配置，才会复现。但现在的机器的内存逐渐的增大，硬件配置的提高，应该可以容纳更多的数据。本人机器是windows64，内存8G配置，Eclipse的配置为 -Xms286M -Xmx1024M，在单独运行此程序时，数据量加到千万级别才会复现出此问题。但在生产环境中，如果放的是复杂对象，可能同样配置的机器存放的数据量会小一些。

　　但如果换成list存放，则同样的配置存放的数据比HashMap要多一些，本人就针对此现象进行分析一下几点：

　　1.HashMap和ArrayList的长度都是动态增加的，不过两者的扩容机制不同，先说HashMap,它在底层是以数组的方式保存元素的，其中每一个键值对就是一个元素，也就是说HashMap把键值对封装成了一个Entry对象，然后再把Entry对象放到了数组中。也就是说HashMap比ArrayList多了一次封装，多出了一倍的对象。其中HashMap的扩容机制代码如下(resize(2 * table.length)这就是扩容核心代码)：

    void addEntry(int hash, K key, V value, int bucketIndex) {<br/>
         if ((size >= threshold) && (null != table[bucketIndex])) {<br/>
             resize(2 * table.length);<br/>
             hash = (null != key) ? hash(key) : 0;<br/>
             bucketIndex = indexFor(hash, table.length);<br/>
         }

         createEntry(hash, key, value, bucketIndex);<br/>
     }

在插入键值对时会做长度校验，如果大于或者等于阈值，则数组长度会增大一倍。

  void resize(int newCapacity) {<br/>
         Entry[] oldTable = table;<br/>
         int oldCapacity = oldTable.length;<br/>
         if (oldCapacity == MAXIMUM_CAPACITY) {<br/>
             threshold = Integer.MAX_VALUE;<br/>
             return;<br/>
         }

         Entry[] newTable = new Entry[newCapacity];<br/>
         boolean oldAltHashing = useAltHashing;<br/>
         useAltHashing |= sun.misc.VM.isBooted() &&<br/>
                 (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);<br/>
         boolean rehash = oldAltHashing ^ useAltHashing;<br/>
         transfer(newTable, rehash);<br/>
         table = newTable;<br/>
      <strong>   threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);<br/>
</strong>     }

　　而阈值就是代码中红色标注的部分，新容量*加权因子和MAXIMUM_CAPACITY + 1两个值的最小值。MAXIMUM_CAPACITY的值如下：　

static final int MAXIMUM_CAPACITY = 1 << 30;

　　而加权因子的值为0.75，代码如下：

static final float DEFAULT_LOAD_FACTOR = 0.75f;

　　所以hashMap的size大于数组的0.75倍时，就开始扩容，经过计算得知(怎么计算的，以文中例子来说，查找2的N次幂大于40万的最小值即为数组的最大长度，再乘以0.75，也就是最后一次扩容点，计算的结果是N=19)，在Map的size为393216时，符合了扩容条件，于是393216个元素开始搬家，要扩容则需要申请一个长度为1048576(当前长度的两倍，2的20次方)的数组，如果此时内存不足以支撑此运算，就会爆出内存溢出。这个就是这个问题的根本原因。

　2、我们思考一下ArrayList的扩容策略，它是在小于数组长度的时候才会扩容1.5倍，经过计算得知，ArrayLsit在超过80万后(一次加两个元素，40万的两倍)，最近的一次扩容是在size为1005305时同样的道理，如果此时内存不足以申请扩容1.5倍时的数组，也会出现内存溢出。

　综合来说，HashMap比ArrayList多了一层Entry的底层封装对象，多占用了内存，并且它的扩容策略是2倍长度的递增，同时还会根据阈值判断规则进行判断，因此相对于ArrayList来说，同样的数据，它就会优先内存溢出。

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30