//這里只看這一小部分，其他重點的在下面詳細解釋  static class Entry<K,V> implements Map.Entry<K,V> { final K key; //就是我們說的map的key V value; //value值，這兩個都不陌生 Entry<K,V> next;//指向下一個entry對象 int hash;//通過key算過來的你hashcode值。

//1、哈希表基于map接口的實現(xiàn)，這個實現(xiàn)提供了map所有的操作，并且提供了key和value可以為null，(HashMap和HashTable大致上市一樣的除了hashmap是異步的和允許key和value為null)，
這個類不確定map中元素的位置，特別要提的是，這個類也不確定元素的位置隨著時間會不會保持不變。 Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. 
(The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map;
 in particular, it does not guarantee that the order will remain constant over time. //假設(shè)哈希函數(shù)將元素合適的分到了每個桶(其實就是指的數(shù)組中位置上的鏈表)中，則這個實現(xiàn)為基本的操作(get、put)提供了穩(wěn)定的性能，迭代這個集合視圖需要的時間跟hashMap實例(key-value映射的數(shù)量)的容量(在桶中)
成正比，因此，如果迭代的性能很重要的話，就不要將初始容量設(shè)置的太高或者loadfactor設(shè)置的太低，【這里的桶，相當于在數(shù)組中每個位置上放一個桶裝元素】 This implementation provides constant-time performance for the basic operations (getandput), assuming the hash function disperses the elements properly among the buckets.
 Iteration over collection views requires time proportional to the "capacity" of theHashMapinstance (the number of buckets) plus its size (the number of key-value mappings
). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important. //HashMap的實例有兩個參數(shù)影響性能，初始化容量(initialCapacity)和loadFactor加載因子，在哈希表中這個容量是桶的數(shù)量【也就是數(shù)組的長度】，一個初始化容量僅僅是在哈希表被創(chuàng)建時容量，在
容量自動增長之前加載因子是衡量哈希表被允許達到的多少的。當entry的數(shù)量在哈希表中超過了加載因子乘以當前的容量，那么哈希表被修改(內(nèi)部的數(shù)據(jù)結(jié)構(gòu)會被重新建立)所以哈希表有大約兩倍的桶的數(shù)量 An instance ofHashMaphas two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, 
and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before
 its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table 
is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets. //通常來講，默認的加載因子(0.75)能夠在時間和空間上提供一個好的平衡，更高的值會減少空間上的開支但是會增加查詢花費的時間（體現(xiàn)在HashMap類中g(shù)et、put方法上），當設(shè)置初始化容量時，應(yīng)該考慮到map中會存放
entry的數(shù)量和加載因子，以便最少次數(shù)的進行rehash操作，如果初始容量大于最大條目數(shù)除以加載因子，則不會發(fā)生 rehash 操作。  As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup
 cost (reflected in most of the operations of theHashMapclass, includinggetandput). The expected number of entries in the map and its load factor should be taken 
into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of
 entries divided by the load factor, no rehash operations will ever occur. //如果很多映射關(guān)系要存儲在HashMap實例中，則相對于按需執(zhí)行自動的 rehash 操作以增大表的容量來說，使用足夠大的初始容量創(chuàng)建它將使得映射關(guān)系能更有效地存儲。 If many mappings are to be stored in aHashMapinstance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting 
it perform automatic rehashing as needed to grow the table

    static final Entry<?,?>[] EMPTY_TABLE = {}; /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

    /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75). */ //看上面的注釋就已經(jīng)知道，DEFAULT_INITIAL_CAPACITY=16，DEFAULT_LOAD_FACTOR=0.75 //初始化容量：也就是初始化數(shù)組的大小
//加載因子：數(shù)組上的存放數(shù)據(jù)疏密程度。 public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /** * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /** * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param initialCapacity the initial capacity
     * @param loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)//initialCapacity不能小于0 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)//initialCapacity大于最大容量時 initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor))//isNaN的作用是檢測loadFactor是否是一個浮點數(shù) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //初始化loadFactor threshold = initialCapacity;//將threshold變?yōu)?6，其實這里賦值為16沒什么用，只是單純的記錄一下這個16的值，好在后面講此值給數(shù)組的長度。后面再初始化數(shù)組長度的時候，就會把該值給重新賦值 init();//一個空的初始化方法 }

//將參數(shù)Map轉(zhuǎn)換為一個HashMap。 public HashMap(Map<? extends K, ? extends V> m) { //根據(jù)m中的size來設(shè)置初始化容量為多少合適，如果(m.size()/DEFAULT_LOAD_FACTOR)+1>DEFAULT_INITLAL_CAPACITY那么久取(m.size()/DEFAULT_LOAD_FACTOR)+1為初始化容量，反之取默認的，而加載因子就一直是默認的0.75 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); //增大table的容量的方法，table也就是鏈表散列的數(shù)組。threshold就是初始化的大小(m.size()/DEFAULT_LOAD_FACTOR)+1或者DEFAULT_INITLAL_CAPACITY16 inflateTable(threshold);

        putAllForCreate(m);
    }

    /** * Inflates the table. */ //擴展table的功能 private void inflateTable(int toSize) { // Find a power of 2 >= toSize //返回一個大于等于 最接近toSize的2的冪數(shù)。 什么意思呢？2的3次方的冪數(shù)就是8.2的冪數(shù)就是每次都市2的幾次方，2的冪數(shù)有可能是1，2，4，8，16等。
比如toSize=16，則16的2的冪數(shù)就是2的4次方還是16，比如toSize=17，那么最接近他的2的冪數(shù)就是2的5次方，也就是32.
//這里不點進去看了，因為里面就是為了實現(xiàn)上面這個目的而寫的一些算法，有興趣的可以自己去讀一讀 int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//設(shè)置一個需要擴增數(shù)組的一個標準 上面也有說到這個變量，不清楚的回頭再看看 //將table數(shù)組大大小改變?yōu)閏apacity。 table = new Entry[capacity]; //初始化一個容量為capacity的哈希表，等用到的時候才真正初始化，返回值是boolean，先放一放。。。。。。。。。。 initHashSeedAsNeeded(capacity);
    }

//添加元素 public V put(K key, V value) { if (table == EMPTY_TABLE) {//判斷是不是一個空的數(shù)組，也就是數(shù)組沒有長度，通過構(gòu)造方法創(chuàng)建，還沒開始用，所以長度為0，這里就開始對數(shù)組進行增長。 inflateTable(threshold);//這個方法在第四個構(gòu)造方法中介紹過，就是用來將數(shù)組變?yōu)榇笥诘扔趖hreshold的2次冪。一開始threshold為16，那么根據(jù)算法，數(shù)組的開始長度也就是為16. } if (key == null)//這里可以看到，HashMap為什么可以使用null值了。 return putForNullKey(value);//將key為null的值存放到table中去。具體看下面putForNullKey的分析。 int hash = hash(key);//通過hash函數(shù)來將key轉(zhuǎn)換為一個hash值 int i = indexFor(hash, table.length);//通過這個方法，將key轉(zhuǎn)換來的hash值和數(shù)組的長度進行操作，得到在數(shù)組中的位置。 for (Entry<K,V> e = table[i]; e != null; e = e.next) {//在對應(yīng)位置上加入新元素
            Object k;
　　　　　　　//遍歷這個桶中的元素，看有沒有相同的key值。 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//只有相同的hash值并且 (可能key相同但是Key的hashcode不同也算key一樣或者用equals比較得到相同)這說明里面有相同的key值。 V oldValue = e.value;//將老value用新value來替代。 e.value = value;
                e.recordAccess(this); return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);//增加元素，方法內(nèi)部實現(xiàn)很簡單，就是將新增加的元素放第一位。而不是往后追加。 return null;
    }

//key為null的元素，默認放在table數(shù)組中的第一個位置上。并且可以知道，如果第一個位置上有元素，則將原來的值覆蓋掉，如果第一個位置上沒有entry。那么就將自己放在第一個位置。 private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) {//遍歷在數(shù)組第一個位置上的鏈表的每個元素(entry)，其實就一個，因為null就一個。 if (e.key == null) {//如果發(fā)現(xiàn)有key為null的值，將現(xiàn)在的值賦值給原來key為null的value。 V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);//一個空的方法。 return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);//上面的情況是有key為null的元素?，F(xiàn)在這里是沒有key為null的元素，則要在第一個位置上放上自己。請看下面對這個方法的解析。 return null;
    }

    void addEntry(int hash, K key, V value, int bucketIndex) { //增加元素前，看一下元素的個數(shù)是否大于等于了我們規(guī)定存放在數(shù)組中的個數(shù)(threshold=數(shù)組容量*加載因子，只是一個存放判定數(shù)組是否需要擴增標準的變量)，并且在table這個指定位置上有元素，則對數(shù)組進行擴展

//前面一個條件成立，擴展數(shù)組，可以理解，為什么還要加上后面一個條件呢？原因是：我們希望盡量在每個數(shù)組的每個位置上只有一個元素是最好的，數(shù)組的容量是大于threshold的，也就是說size雖然到了要擴增的那個標準，

但是在數(shù)組中可能還是有很多位置上沒有放元素，所以在這些位置上增加元素是合理的，不需要擴增。只有等到在size達到了擴增的標準并且添加元素的位置上有別的元素的情況下，才進行闊增。 if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//擴增數(shù)組，看下面的分析。 hash = (null != key) ? hash(key) : 0;//擴增完數(shù)組后，原來的那些參數(shù)就沒用了。需要重新計算，計算添加元素的hash值 bucketIndex = indexFor(hash, table.length);//通過hash值和數(shù)組的長度來計算出在數(shù)組中哪個位置 }

        createEntry(hash, key, value, bucketIndex);//如果沒有擴增，則直接用傳過來的參數(shù)進行創(chuàng)建entry，很簡單，將添加進入的元素放桶中的第一個元素，也就是數(shù)組對應(yīng)位置就是該元素，然后把之后的元素給現(xiàn)在元素的next，具體可以看這個方法的源碼，很簡單 }

   void resize(int newCapacity) {
        Entry[] oldTable = table;//將老的數(shù)組存放在oldTable中 int oldCapacity = oldTable.length;//老的數(shù)組容量 if (oldCapacity == MAXIMUM_CAPACITY) {//判斷老的容量 threshold = Integer.MAX_VALUE;//數(shù)組已經(jīng)擴增到最大值了，所以將判定的標準增加到最大。 return;
        }

        Entry[] newTable = new Entry[newCapacity];//創(chuàng)建一個是原先兩倍大小的數(shù)組。 transfer(newTable, initHashSeedAsNeeded(newCapacity));//因為新數(shù)組的長度改變了，所以每個元素在新數(shù)組中的位置也會改變，所以需要將每個元素的key得到的hashcode值重新算一遍，放入新數(shù)組中 table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//這里就可以知道threshold的真正作用了，就是上面說的，作為判定是否需要擴增數(shù)組的一個標準。 }

    void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) {//遍歷老數(shù)組中的每一個桶，其實就是遍歷數(shù)組的每一個位置。 while(null != e) {//遍歷桶中的元素。e==null的情況是在一個桶中的最后一個元素的next為指向null，或者一開始這個桶就是空的。則需要遍歷下一個桶。 Entry<K,V> next = e.next;//將e元素的下一個元素保存到next中。 if (rehash) {//
                    e.hash = null == e.key ? 0 : hash(e.key);//將每個元素的hash值算出來，通過的是每個元素的key，這個算法感興趣的就點進去看。key和value為null的hash就為0，所以都在數(shù)組的第一個位置。 } int i = indexFor(e.hash, newCapacity);//通過每個元素的hash值和所在數(shù)組的長度，計算出放在數(shù)組中哪個位置，這里就揭示了一開始我們的疑惑，不知道通過hash值怎么得到對應(yīng)數(shù)組中的位置。 e.next = newTable[i];//每次在桶中添加新的數(shù)據(jù)，都是把新數(shù)據(jù)放在開頭，舊數(shù)據(jù)放后面，這個桶就相當于是一個棧，先進去的就在最底層。 newTable[i] = e;//將自己放入數(shù)組中的對應(yīng)位置 e = next;//桶中下一個元素。 }
        }
    }

    static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1);//通過與運算，將h的二進制，和length-1的二進制進行與運算得出的結(jié)果就是數(shù)組中的位置。 }

//通過key刪除entry并返回其value值， public V remove(Object key) { //通過removeEntryForKey來完成刪除功能 Entry<K,V> e = removeEntryForKey(key); //返回值。 return (e == null ? null : e.value);
    }

   final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) {//看hashMap中有沒有值 return null;
        } int hash = (key == null) ? 0 : hash(key);//看key是不是為null，如果為null，就直接返回0，否則通過hash函數(shù)計算出hash值 int i = indexFor(hash, table.length);//得到在數(shù)組中的位置。 Entry<K,V> prev = table[i];
        Entry<K,V> e = prev; while (e != null) {//開始遍歷桶中所有的元素，看有沒有該key值，這個下面，prev代表前一個元素、e代表當前要檢測的元素，next代表e的后一個元素，除了第一次prev=e，其他時候都市像前面這樣。 Entry<K,V> next = e.next;//next記下一個元素 Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {//判斷是該key值， modCount++;
                size--;//要刪除元素了，size自減 if (prev == e)//只有在剛開始，自己處于第一個元素的時候，這個才會等于，其他情況prev代表的是刪除元素的前一個元素， table[i] = next;//如果是第一個元素，直接把桶中第一個元素指向next，在next中保存著原先的第二個元素，現(xiàn)在變?yōu)榈谝粋€元素了 else //刪除的就不是第一個元素，而是之后的，由于是單鏈表，就只需要改變一個指向引用，就是在要刪除的元素之前的元素的next指向要刪除的元素的next。 prev.next = next;//next：刪除元素之后的一個元素，prev：刪除元素的前一個元素，所以就有了這句話 e.recordRemoval(this);//一個空方法 return e;
            }
            prev = e;//記錄要刪除元素的前一個元素 e = next;//這個就是可能要刪除的元素。 } return e;
    }

//通過key獲得value，知道了hashMap的原理后，其實這些都市大同小異。 public V get(Object key) { if (key == null)//判斷是否為null return getForNullKey();//這個方法里太簡單了，做兩件事情，第一，如果size=0，返回null，反之到數(shù)組的第一個位置獲取null對應(yīng)的value值，前提是有，沒有也返回null。 Entry<K,V> entry = getEntry(key);//通過key獲得entry對象，看一下里面是如何獲得的，我猜跟那個通過key刪除元素差不多。也還是先找到對應(yīng)位置，然后遍歷鏈表。 return null == entry ? null : entry.getValue();//返回 }

//和remove(key)這個方法的邏輯一樣，但是簡單得多，因為不用刪除，只需要找到然后返回entry對象即可 final Entry<K,V> getEntry(Object key) { if (size == 0) { return null;
        } int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e;
        } return null;
    }