摘要：代碼實(shí)現(xiàn)表的長度，即具體有多少個(gè)位置選擇一個(gè)合適的素?cái)?shù)取的絕對(duì)值修改添加即除以由于在方法中有對(duì)進(jìn)行操作，在往新哈希表中存數(shù)據(jù)時(shí)應(yīng)該用計(jì)算相應(yīng)的值哈希表的均攤復(fù)雜度為，有這么好的性能其中一個(gè)原因是它犧牲了順序性。

在Java8開始，當(dāng)哈希沖突達(dá)到一定的程度，每一個(gè)位置從鏈表轉(zhuǎn)化為紅黑樹。

平均每個(gè)地址承載的元素多過一定程度，即擴(kuò)容（N/M >= upperTol）

平均每個(gè)地址承載的元素少過一定程度，即縮容（N/M <= lowerTol）

剛開始我們?cè)跀U(kuò)容的時(shí)候直接是2*M，它可能造成擴(kuò)容后的哈希表分布不均勻，可以按著下面這個(gè)表格來設(shè)置M值。

public class HashTable {

    private final int[] capacity
        = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 
        12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741 };
    
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private static final int initCapacity = 7;
    private int CapacityIndex = 0;
    
    private TreeMap[] hashtable;
    private int size;
    private int M;    //hash表的長度，即具體有多少個(gè)位置（選擇一個(gè)合適的素?cái)?shù)）

    public HashTable(){
        //this.M = M;
        this.M = capacity[CapacityIndex];
        size = 0;
        hashtable = new TreeMap[M];
        for(int i = 0 ; i < M ; i ++)
            hashtable[i] = new TreeMap<>();
    }

    /*public HashTable(){
        this(initCapacity);
    }*/

    private int hash(K key){
        //key.hashCode() & 0x7fffffff 取key.hashCode()的絕對(duì)值
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize(){
        return size;
    }

    public void add(K key, V value){
        TreeMap map = hashtable[hash(key)];
        if(map.containsKey(key))    //修改
            map.put(key, value);
        else{                        //添加
            map.put(key, value);
            size ++;
            
            if(size >= upperTol * M && CapacityIndex+1 < capacity.length)    //即size除以M >=upperTol
                //resize(2 * M);
                CapacityIndex ++;
                resize(capacity[CapacityIndex]);
        }
    }

    public V remove(K key){
        V ret = null;
        TreeMap map = hashtable[hash(key)];
        if(map.containsKey(key)){
            ret = map.remove(key);
            size --;
            
            if(size < lowerTol * M && CapacityIndex-1 >= 0)
                CapacityIndex --;
                //resize(M / 2);
                resize(capacity[CapacityIndex]);
        }
        return ret;
    }

    public void set(K key, V value){
        TreeMap map = hashtable[hash(key)];
        if(!map.containsKey(key))
            throw new IllegalArgumentException(key + " doesn"t exist!");

        map.put(key, value);
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }
    
    private void resize(int newM){
        TreeMap[] newHashTable = new TreeMap[newM];
        for(int i = 0 ; i < newM ; i ++)
            newHashTable[i] = new TreeMap<>();
            
        //由于在hash()方法中有對(duì)M進(jìn)行操作，在往新哈希表中存數(shù)據(jù)時(shí)應(yīng)該用newM計(jì)算hash相應(yīng)的hash值
        int oldM = M;
        this.M = newM;
        
        for(int i = 0 ; i < oldM ; i ++){
            TreeMap map = hashtable[i];
            for(K key: map.keySet())
                newHashTable[hash(key)].put(key, map.get(key));
        }

        this.hashtable = newHashTable;
    }
}

哈希表的均攤復(fù)雜度為O(1)，有這么好的性能其中一個(gè)原因是它犧牲了順序性。