1. 使用shuffle打亂列表

在網(wǎng)站上我們經(jīng)?？吹疥P(guān)鍵字云和標簽云等，用于表明這個關(guān)鍵字或標簽經(jīng)常被查閱。我

使用swap實現(xiàn)：

  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);
    }
  }

最優(yōu)的使用shuffle實現(xiàn)：

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

2. 減少HashMap中元素的數(shù)量

在系統(tǒng)開發(fā)中我們經(jīng)常會使用HashMap作為數(shù)據(jù)集容器,或者是用緩沖池來處理,一般很穩(wěn)定,但偶爾也會出現(xiàn)內(nèi)存溢出的問題(OutOfMemory錯誤),而且這經(jīng)常是與HashMap有關(guān)的.而且這經(jīng)常是與HashMap有關(guān)的.比如我們使用緩沖池操作數(shù)據(jù)時,大批量的增刪改產(chǎn)操作就可能會讓內(nèi)存溢出,下面建立一段模擬程序,重現(xiàn)該問題,看代碼:

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終止前記錄內(nèi)存信息
        rt.addShutdownHook(new Thread() {
            @Override
            public void run() {
                StringBuffer sb = new StringBuffer();
                long heapMaxSize = rt.maxMemory() >> 20;
                sb.append("最大可用內(nèi)存：" + heapMaxSize + "M\n");
                long total = rt.totalMemory() >> 20;
                sb.append("對內(nèi)存大小：" + total + "M\n");
                long free = rt.freeMemory() >> 20;
                sb.append("空閑內(nèi)存：" + free + "M");
                System.out.println(sb);
            }
        });
        // 放入40萬鍵值對
        for (int i = 0; i < 40*10000; i++) {
            map.put("key" + i, "vlaue" + i);
        }
    }
}

運行結(jié)果如下：

Exception in thread "main" 最大可用內(nèi)存：63M
對內(nèi)存大?。?3M
空閑內(nèi)存：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)

內(nèi)存溢出了....可能認為在運行時增加"-Xmx"參數(shù)設(shè)置內(nèi)存大小就可以了,這確實可以,不過浮于表面,沒有真正的從溢出的最根本原因上來解決問題.難道的是String字符串太多了?字符串對象對象加起來撐死最多10MB,而且這里還空閑了7MB內(nèi)存,不應(yīng)該報內(nèi)存溢出？

或者是put方法有缺陷,產(chǎn)生了內(nèi)存泄漏?不可能...這里還有7MB的內(nèi)存可用,應(yīng)該要用盡了才會出現(xiàn)內(nèi)存泄漏啊

用ArrayList做一個對比,把相同數(shù)據(jù)插入到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終止前記錄內(nèi)存信息
        rt.addShutdownHook(new Thread() {
            @Override
            public void run() {
                StringBuffer sb = new StringBuffer();
                long heapMaxSize = rt.maxMemory() >> 20;
                sb.append("最大可用內(nèi)存：" + heapMaxSize + "M\n");
                long total = rt.totalMemory() >> 20;
                sb.append("對內(nèi)存大?。? + total + "M\n");
                long free = rt.freeMemory() >> 20;
                sb.append("空閑內(nèi)存：" + free + "M");
                System.out.println(sb);
            }
        });
        // 放入40萬同樣字符串
        for (int i = 0; i < 400000; i++) {
            list.add("key" + i);
            list.add("vlaue" + i);
        }
    }
}

運行輸出:

最大可用內(nèi)存：63M
對內(nèi)存大小：63M
空閑內(nèi)存：11M

ArrayList運行很正常,沒有出現(xiàn)內(nèi)存溢出的情況,兩個容器,容納的元素相同,數(shù)量相同,ArrayList沒有溢出,但HashMap卻溢出了,很明顯,這與HashMap內(nèi)部的處理機制有很大的關(guān)系.

HashMap在底層也是以數(shù)組方式保存元素的,其中每一個鍵值對就是一個元素 ,也就是說HashMap把鍵值對封裝成了一個Entry對象,然后再把Entry放到了數(shù)組中,我們簡單看一下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底層的數(shù)組變量名叫table,它是Entry類型的數(shù)組,保存的是一個個的鍵值對(在我們的例子中Entry是由兩個String類型組成的).對我們的例子來說,HashMap比ArrayList多了一次封裝,把String類型的鍵值對轉(zhuǎn)換成Entry對象后再放入數(shù)組,這就多了40萬個對象,這應(yīng)該是問題產(chǎn)生的一個原因.

我們知道HashMap的長度也是可以動態(tài)增加的,它的擴容機制與ArrayList稍有不同,其代碼如下:

if (size++ >= threshold)

　　resize(2 * table.length);

在插入鍵值對時,會做長度校驗,如果大于或等于閥值(threshold變量),則數(shù)組長度增大一倍,不過,默認的閥值是多大呢?默認是當(dāng)前長度與加載因子的乘積.

threshold = (int) (newCapacity * loadFactory);

默認的加載因子(loadFactor變量)是0.75,也就是說只要HashMap的size大于數(shù)組長度的0.75倍時,就開始擴容,經(jīng)過計算得知(怎么計算,查找2的N次方大于40萬的最小值即為數(shù)組的最大長度,再乘以0.75就是最后一次擴容點,計算的結(jié)果是19),

在Map的size為393216時,符合了擴容條件,于是393216個元素準備開始大搬家,那就要首先申請一個長度為1048576(當(dāng)前長度的兩倍,2的19次方再乘以2,即2的20次方)的數(shù)組,但問題是此時剩余的內(nèi)存只有7Mb了.不足以支撐此時的運算.于是就報內(nèi)存溢出了.這是第二個原因,也是最根本的原因.

這就解釋了為什么還剩余7MB的時候就報內(nèi)存溢出了.

再考慮下ArrayList的擴容策略,它是在小于數(shù)組長度的時候才會擴容1.5倍,經(jīng)過計算得知,ArrayList的size在超過80萬后(一次加兩個元素,40萬的兩倍),最近的一次擴容會在size為1005308時,也就是說,如果程序設(shè)置了增加元素的上限為502655,同樣會報內(nèi)存溢出,因為他也要申請一個1507963長度的數(shù)組.如果沒有這么大的地方,就報錯了.

綜合來說,HashMap比ArrayList多了一個層Entry的底層對象封裝,多占用了內(nèi)存,并且它的擴容策略是2倍長度的遞增,同時還會依據(jù)閥值判斷規(guī)則進行判斷,因此相對于ArrayList來說,它就會先出現(xiàn)內(nèi)存溢出.

3. 從源碼分析HashSet / HashMap是如何保證不重復(fù)的

HashSet.add()調(diào)用的是HashMap.put()。HashMap判斷依據(jù)是key值。映射到一個hash桶，當(dāng)key值相等時，替換掉舊值，不相等就追加節(jié)點。這樣保證了一個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相當(dāng)于對表大小取余，即i是下標
         * tab[i]=null即這個桶是空的，直接newNode即可
         * p如果不空則賦值為鏈表頭，第一個節(jié)點
         */
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //桶不空即鏈表至少有一個節(jié)點
        else {
            Node<K,V> e; K k;
            //如果key相同則賦給e
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果桶里不是鏈表而是紅黑樹，那根據(jù)hash值放入紅黑樹
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //它是鏈表并且需要尋找下一個節(jié)點進行比較
            else {
                for (int binCount = 0; ; ++binCount) {
                    //鏈表到頭沒找著key相同的，要新增
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //鏈表的節(jié)點總數(shù) >= 8變成紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //找到相等的，不必再往下，跳出for循環(huán)
                    //如果不跳出，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不可更新開關(guān)，put默認false
                //可更新 或 原值為空，則替換為新值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }//end else桶空情況
        //全局修改次數(shù)+1
        ++modCount;
        //size+1 > 閾值（capacity * load factor）
        if (++size > threshold)
            resize();
        //對HashMap來說是空方法，是LinkedHashMap用的
        afterNodeInsertion(evict);
        return null;
    }
}

4. 非穩(wěn)定排序推薦使用List

我們知道Set與List的區(qū)別就是Set中元素不可以重復(fù)（這個重復(fù)是指equals方法的返回值相等），其它方面沒有太大的區(qū)別。在Set的實現(xiàn)類里有一個TreeSet，該類實現(xiàn)了類默認排序為升序的Set集合，如果插入一個元素，默認會按升序排列（當(dāng)然是根據(jù)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;
        }

    }
}

結(jié)果：

身高: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());
        }
    }

結(jié)果：

身高:185
身高:180

解決方法如下：

• Set集合重排序，重新生成一個Set對象，也就是對原有Set對象重新排序，set = new TreeSet<Person>(new ArrayList<Person>(set))。為什么不使用TreeSet<SortedSet<E> s>這個構(gòu)造函數(shù)？不行，該構(gòu)造函數(shù)只是原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);該構(gòu)造函數(shù)只是原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;
        }

    }
}

• 如果不考慮重復(fù)，可以使用List實現(xiàn)，用Collections.sort()進行排序