1. 使用shuffle打乱列表

在网站上我们经常看到关键字云和标签云等，用于表明这个关键字或标签经常被查阅。我

使用swap实现：

  public static void main(String[] arg) {
    int tagCloudNum = 10;
    List<String> tagfClouds = new ArrayList<>(tagCloudNum);
    
    Random rand = new Random();
    for(int i=0;i<tagCloudNum;i++){
        int randomPosition = rand.nextInt(tagCloudNum);
        Collections.swap(tagfClouds,i,randomPosition);
    }
  }

最优的使用shuffle实现：

  public static void main(String[] arg) {
    int tagCloudNum = 10;
    List<String> tagfClouds = new ArrayList<>(tagCloudNum);
    //打乱顺序
    Collections.shuffle(tagfClouds);
  }

2. 减少HashMap中元素的数量

在系统开发中我们经常会使用HashMap作为数据集容器,或者是用缓冲池来处理,一般很稳定,但偶尔也会出现内存溢出的问题(OutOfMemory错误),而且这经常是与HashMap有关的.而且这经常是与HashMap有关的.比如我们使用缓冲池操作数据时,大批量的增删改产操作就可能会让内存溢出,下面建立一段模拟程序,重现该问题,看代码:

import java.util.HashMap;
import java.util.Map;

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

运行结果如下：

Exception in thread "main" 最大可用内存：63M
对内存大小：63M
空闲内存：7M
java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.resize(Unknown Source)
    at java.util.HashMap.addEntry(Unknown Source)
    at java.util.HashMap.put(Unknown Source)
    at cn.summerchill.test.Client.main(Client.java:26)

内存溢出了....可能认为在运行时增加"-Xmx"参数设置内存大小就可以了,这确实可以,不过浮于表面,没有真正的从溢出的最根本原因上来解决问题.难道的是String字符串太多了?字符串对象对象加起来撑死最多10MB,而且这里还空闲了7MB内存,不应该报内存溢出？

或者是put方法有缺陷,产生了内存泄漏?不可能...这里还有7MB的内存可用,应该要用尽了才会出现内存泄漏啊

用ArrayList做一个对比,把相同数据插入到ArrayList中看看会怎么样,看代码:

import java.util.ArrayList;
import java.util.List;

public class Client {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        final Runtime rt = Runtime.getRuntime();
        // JVM终止前记录内存信息
        rt.addShutdownHook(new Thread() {
            @Override
            public void run() {
                StringBuffer sb = new StringBuffer();
                long heapMaxSize = rt.maxMemory() >> 20;
                sb.append("最大可用内存：" + heapMaxSize + "M\n");
                long total = rt.totalMemory() >> 20;
                sb.append("对内存大小：" + total + "M\n");
                long free = rt.freeMemory() >> 20;
                sb.append("空闲内存：" + free + "M");
                System.out.println(sb);
            }
        });
        // 放入40万同样字符串
        for (int i = 0; i < 400000; i++) {
            list.add("key" + i);
            list.add("vlaue" + i);
        }
    }
}

运行输出:

最大可用内存：63M
对内存大小：63M
空闲内存：11M

ArrayList运行很正常,没有出现内存溢出的情况,两个容器,容纳的元素相同,数量相同,ArrayList没有溢出,但HashMap却溢出了,很明显,这与HashMap内部的处理机制有很大的关系.

HashMap在底层也是以数组方式保存元素的,其中每一个键值对就是一个元素 ,也就是说HashMap把键值对封装成了一个Entry对象,然后再把Entry放到了数组中,我们简单看一下Entry类:java.util.HashMap.Entry<K, V>

static class Entry<K,V> implements Map.Entry<K,V> {
        //键
        final K key;
        //值
        V value;
        //相同哈希码的下一个元素
        Entry<K,V> next;
        
        final int hash;
        //key,value的getter和setter方法,以及重写的equals,hashCode,toString方法
    }

HashMap底层的数组变量名叫table,它是Entry类型的数组,保存的是一个个的键值对(在我们的例子中Entry是由两个String类型组成的).对我们的例子来说,HashMap比ArrayList多了一次封装,把String类型的键值对转换成Entry对象后再放入数组,这就多了40万个对象,这应该是问题产生的一个原因.

我们知道HashMap的长度也是可以动态增加的,它的扩容机制与ArrayList稍有不同,其代码如下:

if (size++ >= threshold)

　　resize(2 * table.length);

在插入键值对时,会做长度校验,如果大于或等于阀值(threshold变量),则数组长度增大一倍,不过,默认的阀值是多大呢?默认是当前长度与加载因子的乘积.

threshold = (int) (newCapacity * loadFactory);

默认的加载因子(loadFactor变量)是0.75,也就是说只要HashMap的size大于数组长度的0.75倍时,就开始扩容,经过计算得知(怎么计算,查找2的N次方大于40万的最小值即为数组的最大长度,再乘以0.75就是最后一次扩容点,计算的结果是19),

在Map的size为393216时,符合了扩容条件,于是393216个元素准备开始大搬家,那就要首先申请一个长度为1048576(当前长度的两倍,2的19次方再乘以2,即2的20次方)的数组,但问题是此时剩余的内存只有7Mb了.不足以支撑此时的运算.于是就报内存溢出了.这是第二个原因,也是最根本的原因.

这就解释了为什么还剩余7MB的时候就报内存溢出了.

再考虑下ArrayList的扩容策略,它是在小于数组长度的时候才会扩容1.5倍,经过计算得知,ArrayList的size在超过80万后(一次加两个元素,40万的两倍),最近的一次扩容会在size为1005308时,也就是说,如果程序设置了增加元素的上限为502655,同样会报内存溢出,因为他也要申请一个1507963长度的数组.如果没有这么大的地方,就报错了.

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

3. 从源码分析HashSet / HashMap是如何保证不重复的

HashSet.add()调用的是HashMap.put()。HashMap判断依据是key值。映射到一个hash桶，当key值相等时，替换掉旧值，不相等就追加节点。这样保证了一个HashMap里key值是唯一的。从而相同key值的元素只有一份，保证其唯一

public class HashSet<E> 
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private static final Object PRESENT = new Object();
    private transient HashMap<E,Object> map;
        ......

    public boolean add(E e) {
        //用了HashMap的put
        return map.put(e, PRESENT)==null;
    }
}

public class HashMap<K,V> 
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    ......

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /* n是表的大小，是2的整次幂，初始大小是16.
         * (n - 1) & hash相当于对表大小取余，即i是下标
         * tab[i]=null即这个桶是空的，直接newNode即可
         * p如果不空则赋值为链表头，第一个节点
         */
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //桶不空即链表至少有一个节点
        else {
            Node<K,V> e; K k;
            //如果key相同则赋给e
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果桶里不是链表而是红黑树，那根据hash值放入红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //它是链表并且需要寻找下一个节点进行比较
            else {
                for (int binCount = 0; ; ++binCount) {
                    //链表到头没找着key相同的，要新增
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表的节点总数 >= 8变成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //找到相等的，不必再往下，跳出for循环
                    //如果不跳出，e最后一定等于null
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //和前面if里的e=p.next配合，往前一个
                    p = e;
                }
            }
            //e是找到的那个链表里的旧的
            if (e != null) { 
                V oldValue = e.value;
                //onlyIfAbsent不可更新开关，put默认false
                //可更新 或 原值为空，则替换为新值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }//end else桶空情况
        //全局修改次数+1
        ++modCount;
        //size+1 > 阈值（capacity * load factor）
        if (++size > threshold)
            resize();
        //对HashMap来说是空方法，是LinkedHashMap用的
        afterNodeInsertion(evict);
        return null;
    }
}

4. 非稳定排序推荐使用List

我们知道Set与List的区别就是Set中元素不可以重复（这个重复是指equals方法的返回值相等），其它方面没有太大的区别。在Set的实现类里有一个TreeSet，该类实现了类默认排序为升序的Set集合，如果插入一个元素，默认会按升序排列（当然是根据Comparable接口的compareTo的返回值确定排序位置）

import java.util.SortedSet;
import java.util.TreeSet;

public class Client {
    public static void main(String[] args) {
        SortedSet<Person> set = new TreeSet<Person>();
        //身高180CM
        set.add(new Person(180));
        //身高175CM
        set.add(new Person(175));
        
        for(Person p:set){
            System.out.println("身高:"+p.getHeight());
        }
    }
    
    static class Person implements Comparable<Person>{
        //身高
        private int height;
        
        public Person(int _age){
            height = _age;
        }
        

        public int getHeight() {
            return height;
        }


        public void setHeight(int height) {
            this.height = height;
        }

        //按照身高排序
        public int compareTo(Person o) {
            return height - o.height;
        }

    }
}

结果：

身高:175
身高:180

但是如果在插入元素后再修改某个元素的值，那么Set不会重新排序。

public static void main(String[] args) {
        SortedSet<Person> set = new TreeSet<Person>();
        // 身高180CM
        set.add(new Person(180));
        // 身高175CM
        set.add(new Person(175));
        // 身高最矮的人大变身
        set.first().setHeight(185);
        for (Person p : set) {
            System.out.println("身高:" + p.getHeight());
        }
    }

结果：

身高:185
身高:180

解决方法如下：

• Set集合重排序，重新生成一个Set对象，也就是对原有Set对象重新排序，set = new TreeSet<Person>(new ArrayList<Person>(set))。为什么不使用TreeSet<SortedSet<E> s>这个构造函数？不行，该构造函数只是原Set的浅拷贝，如果里面有相同的元素则不进行排序

import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;

public class Client {
    public static void main(String[] args) {
        SortedSet<Person> set = new TreeSet<Person>();
        // 身高180CM
        set.add(new Person(180));
        // 身高175CM
        set.add(new Person(175));
        // 身高最矮的人大变身
        set.first().setHeight(185);
        //set重排序
        set = new TreeSet<Person>(new ArrayList<Person>(set));
　　　　　　 //set = new TreeSet(set);该构造函数只是原Set的浅拷贝，如果里面有相同的元素，是不会重新排序的
        for (Person p : set) {
            System.out.println("身高:" + p.getHeight());
        }
    }

    static class Person implements Comparable<Person> {
        // 身高
        private int height;

        public Person(int _age) {
            height = _age;
        }

        public int getHeight() {
            return height;
        }

        public void setHeight(int height) {
            this.height = height;
        }

        // 按照身高排序
        public int compareTo(Person o) {
            return height - o.height;
        }

    }
}

• 如果不考虑重复，可以使用List实现，用Collections.sort()进行排序