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

    //默認(rèn)的HashMap的空間大小16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

    //hashMap最大的空間大小
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //HashMap默認(rèn)負(fù)載因子勇边，負(fù)載因子越小，hash沖突機(jī)率越低，至于為什么缨叫，看完下面源碼就知道了
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final Entry<?,?>[] EMPTY_TABLE = {};

    //table就是HashMap實(shí)際存儲數(shù)組的地方
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

    //HashMap 實(shí)際存儲的元素個數(shù)
    transient int size;

    //臨界值（即hashMap 實(shí)際能存儲的大泻帜怼）,公式為(threshold = capacity * loadFactor)
    int threshold;

    //HashMap 負(fù)載因子
    final float loadFactor;



    //HashMap的(key -> value)鍵值對形式其實(shí)是由內(nèi)部類Entry實(shí)現(xiàn)捺檬，那么此處就先貼上這個內(nèi)部類
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
    //保存了對下一個元素的引用预明，說明此處為鏈表
    //為什么此處會用鏈表來實(shí)現(xiàn)役耕？
    //其實(shí)此處用鏈表是為了解決hash一致的時候的沖突
    //當(dāng)兩個或者多個hash一致的時候采转，那么就將這兩個或者多個元素存儲在一個位置，用next來保存對下個元素的引用
        Entry<K,V> next;
        int hash;

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        
        void recordAccess(HashMap<K,V> m) {
        }

        
        void recordRemoval(HashMap<K,V> m) {
        }
    }
    //以上是內(nèi)部類Entry

    //構(gòu)造方法瞬痘， 設(shè)置HashMap的loadFactor 和 threshold, 方法極其簡單故慈，不多說
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

    
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    //構(gòu)造方法，傳入Map, 將Map轉(zhuǎn)換為HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    //初始化HashMap框全， 這個方法下面會詳細(xì)分析
        inflateTable(threshold);
    //這就是將指定Map轉(zhuǎn)換為HashMap的方法察绷，后面會詳細(xì)分析
        putAllForCreate(m);
    }
    
    //初始化HashMap
    private void inflateTable(int toSize) {
        //計算出大于toSize最臨近的2的N此方的值
    //假設(shè)此處傳入6, 那么最臨近的值為2的3次方，也就是8
        int capacity = roundUpToPowerOf2(toSize);
    //由此處可知：threshold = capacity * loadFactor
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    //創(chuàng)建Entry數(shù)組竣况，這個Entry數(shù)組就是HashMap所謂的容器
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

    private static int roundUpToPowerOf2(int number) {
        //當(dāng)臨界值小于HashMap最大容量時克婶， 返回最接近臨界值的2的N次方
    //Integer.highestOneBit方法的作用是用來計算指定number最臨近的2的N此方的數(shù)
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

    //這就是將指定Map轉(zhuǎn)換為HashMap的方法筒严，主要看下面的putForCreate方法
    private void putAllForCreate(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            putForCreate(e.getKey(), e.getValue());
    }

    private void putForCreate(K key, V value) {
    //計算hash值， key為null的時候情萤，hash為0
        int hash = null == key ? 0 : hash(key);
    //根據(jù)hash值鸭蛙，找出當(dāng)前hash在table中的位置
        int i = indexFor(hash, table.length);

        //由于table[i]處可能不止有一個元素（多個會形成一個鏈表），因此筋岛，此處寫這樣一個循環(huán)
    //當(dāng)key存在的時候娶视，直接將key的值設(shè)置為新值
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                e.value = value;
                return;
            }
        }
    //當(dāng)key不存在的時候，就在table的指定位置新創(chuàng)建一個Entry
        createEntry(hash, key, value, i);
    }
    
    //在table的指定位置新創(chuàng)建一個Entry
    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++;
    }


    
    //下面就開始分析我們常用的方法了（put, remove）

    //先看put方法
    public V put(K key, V value) {
    //table為空睁宰，就先初始化
        if (table == EMPTY_TABLE) {
        //這個方法上面已經(jīng)分析過了肪获，主要是在初始化HashMap,包括創(chuàng)建HashMap保存的元素的數(shù)組等操作
            inflateTable(threshold);
        }
    
    //key 為null的情況， 只允許有一個為null的key
        if (key == null)
            return putForNullKey(value);
    //計算hash
        int hash = hash(key);
    //根據(jù)指定hash柒傻，找出在table中的位置
        int i = indexFor(hash, table.length);
    //table中孝赫，同一個位置（也就是同一個hash）可能出現(xiàn)多個元素（鏈表實(shí)現(xiàn)），故此處需要循環(huán)
    //如果key已經(jīng)存在红符，那么直接設(shè)置新值
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
    //key 不存在青柄，就在table指定位置之處新增Entry
        addEntry(hash, key, value, i);
        return null;
    }

    //當(dāng)key為null 的處理情況
    private V putForNullKey(V value) {
    //先看有沒有key為null, 有就直接設(shè)置新值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;、
    //當(dāng)前沒有為null的key就新創(chuàng)建一個entry,其在table的位置為0（也就是第一個）
        addEntry(0, null, value, 0);
        return null;
    }
    
    //在table指定位置新增Entry, 這個方法很重要    
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
        //table容量不夠, 該擴(kuò)容了（兩倍table）预侯，重點(diǎn)來了致开，下面將會詳細(xì)分析
            resize(2 * table.length);
        //計算hash, null為0
            hash = (null != key) ? hash(key) : 0;
        //找出指定hash在table中的位置
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
    
    //擴(kuò)容方法 (newCapacity * loadFactor)
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
    //如果之前的HashMap已經(jīng)擴(kuò)充打最大了，那么就將臨界值threshold設(shè)置為最大的int值
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
    
    //根據(jù)新傳入的capacity創(chuàng)建新Entry數(shù)組萎馅，將table引用指向這個新創(chuàng)建的數(shù)組双戳，此時即完成擴(kuò)容
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
    //擴(kuò)容公式在這兒（newCapacity * loadFactor）
    //通過這個公式也可看出，loadFactor設(shè)置得越小糜芳，遇到hash沖突的幾率就越小
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    //擴(kuò)容之后飒货，重新計算hash，然后再重新根據(jù)hash分配位置峭竣，
    //由此可見膏斤，為了保證效率，如果能指定合適的HashMap的容量邪驮，會更合適
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }


    //上面看了put方法，接下來就看看remove
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    //這就是remove的核心方法
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
    //老規(guī)矩傲茄，先計算hash,然后通過hash尋找在table中的位置
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
    
    //這兒又神奇地回到了怎么刪除鏈表的問題（上次介紹linkedList的時候毅访，介紹過）
    //李四左手牽著張三，右手牽著王五盘榨，要刪除李四喻粹，那么直接讓張三牽著王五的手就OK
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }


}