package java.util;import java.io.*;public class HashMap
    
         extends AbstractMap
     
          implements Map
      
       , Cloneable, Serializable{    /**     * 默认的初始容量，必须是2的幂     */    static final int DEFAULT_INITIAL_CAPACITY = 16;    /**     * MUST be a power of two <= 1<<30.     * 最大容量，如果构造方法没有设置参数将指定一个较高值     */    static final int MAXIMUM_CAPACITY = 1 << 30;    /**     * 默认装载因子。     * 默认的entry数组的长度为16。装载因子的意义在于使得entry数组有冗余，     * 默认即允许25%的冗余，当HashMap的数据的个数超过12（16*0.75）时     * 即会对entry数组进行第一次扩容，后面的再次扩容依次类推。     */    static final float DEFAULT_LOAD_FACTOR = 0.75f;    /**     * 存储实体的数组,可调整。数据长度总是2的幂     * transient 序列化时忽略该字段。数组存放的是实体的引用，序列化时必须遍历该字段逐个实体序列化。     */    transient Entry[] table;    /**     * 键值对的数目     * transient 序列化时忽略该字段。反序列化的时候读取出每对key、value值，再存入HashMap的数组中     */    transient int size;    /**     * 下一个容量调整值(扩容临界值)     */    int threshold;    /**     * 装载因子     * @serial     */    final float loadFactor;    /**     * map结构被改变的次数     * 结构上的修改是指更改在HashMap中映射的数量或以其他方式修改它的内部结构（例如，刷新）     * 该字段在HashMap使用迭代器遍历的时候使用     */    transient volatile int modCount;    /**     * 根据初始容量和加载因子创建一个空的HashMap     * (初始容量小于0或装载因子小于等于0将报异常)     */    public HashMap(int initialCapacity, float loadFactor) {    	  // 初始容量小于0，抛出非法参数异常        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        // 初始容量大于最大容量，调整初始容量        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        // 加载因子小于等于0或者非浮点数，抛出非法参数异常        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        // Find a power of 2 >= initialCapacity        // 设置capacity为大于initialCapacity且是2的幂的最小值        int capacity = 1;        while (capacity < initialCapacity)            capacity <<= 1;								//设置加载因子        this.loadFactor = loadFactor;        //设置扩容临界值        threshold = (int)(capacity * loadFactor);        //创建数组        table = new Entry[capacity];        //初始化        init();    }    /**     * 根据指定容量创建一个空的HashMap     */    public HashMap(int initialCapacity) {    	  // 调用上面的构造方法，容量为指定的容量，装载因子是默认值        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    /**     * 根据默认初始化容量和默认加载因子(0.75)创建HashMap     */    public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR;        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);        table = new Entry[DEFAULT_INITIAL_CAPACITY];        init();    }    /**     * 通过传入的map创建一个HashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1     * 的较大者，装载因子为默认值     */    public HashMap(Map
        m) {        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);        putAllForCreate(m);    }    // internal utilities    /**     * 初始化方法(钩子方法)     * 所有的构造方法和伪构造方法(clone,readObject)将在HashMap初始化完成之后，元素插入之前调用该方法     */    void init() {    }    /**     * 适用补充hash函数，防止质量较差的hash函数。     * 该方法主要作用是防止质量较差的哈希函数带来过多的冲突（碰撞）问题。     * Java中int值占4个字节，即32位。根据这32位值进行移位、异或运算得到一个值。     */    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    /**     * 返回Hash code h的值在存储数组中的索引     * 为啥和length-1进行与运算，因为这样可以保证结果的最大值是length-1，不会产生数组越界问题。     */    static int indexFor(int h, int length) {        return h & (length-1);    }    /**     * 键存储值对的数量     */    public int size() {        return size;    }    /**     * 判断map是否为空     */    public boolean isEmpty() {        return size == 0;    }    /**     * 根据key查询value     *     * @see #put(Object, Object)     */    public V get(Object key) {    		//key为空        if (key == null)            return getForNullKey();                //计算key哈希        int hash = hash(key.hashCode());        //遍历链表        for (Entry
       
         e = table[indexFor(hash, table.length)]; e != null; e = e.next) {            Object k;            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))                return e.value;        }        return null;    }    /**     * 查询key为null时的值     */    private V getForNullKey() {    		//遍历索引为零的链表，key为null时映射的索引位置为0        for (Entry
        
          e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;    }    /**     * 是否包含key     */    public boolean containsKey(Object key) {        return getEntry(key) != null;    }    /**     * 根据key获取对应的值，没有则返回空     */    final Entry
         
           getEntry(Object key) {     //计算哈希值        int hash = (key == null) ? 0 : hash(key.hashCode());        //遍历链表，查询对应的值        for (Entry
          
            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;    }    /**     * 将指定的值映射指定的键。如果指定的键已存在映射关系，则旧值会被替换。     */    public V put(K key, V value) {     //如果key为空，则调用putForNullKey方法        if (key == null)            return putForNullKey(value);        //调用补充hash方法(防止低质量hash方法造成冲突过多问题)        int hash = hash(key.hashCode());        //获取hash code对应的存储数组索引        int i = indexFor(hash, table.length);        //遍历目标存储数组单元下的链表        for (Entry
           
             e = table[i]; e != null; e = e.next) {            Object k;            //如果已存在键值对值的hash等于将要插入兼职对值的hash，并且已存在键值对键等于将要插入键值对键            //(内存地址相等或者equals)            //即同键值覆盖            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                V oldValue = e.value;                e.value = value;                e.recordAccess(this);                //返回旧值                return oldValue;            }        } //修改记录Map改变次数的值        modCount++;        //添加键值对        addEntry(hash, key, value, i);        return null;    }    /**     * 空键插入(私有方法)     */    private V putForNullKey(V value) {       //先遍历数组，如果存在key为空的，先替换值并返回旧值        for (Entry
            
              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++;        //添加值        addEntry(0, null, value, 0);        return null;    }    /**     * 该方法被构造函数和伪构造函数(clone,readObject)用来替代put方法。     * 该方法不扩展数组，不检查map修改次数，方法体调用createEntry方法而非addEntry     *     */    private void putForCreate(K key, V value) {        int hash = (key == null) ? 0 : hash(key.hashCode());        int i = indexFor(hash, table.length);        /**         * Look for preexisting entry for key.  This will never happen for         * clone or deserialize.  It will only happen for construction if the         * input Map is a sorted map whose ordering is inconsistent w/ equals.         *         * 遍历已存在的键，如果和当前key相等，则值替换后返回         */        for (Entry
             
               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;            }        } // 没有则创建        createEntry(hash, key, value, i);    } /**  *  将指定map中数据插入到当前map中  */    private void putAllForCreate(Map
               m) {        for (Iterator
              > i = m.entrySet().iterator(); i.hasNext(); ) {            Map.Entry
               e = i.next();            putForCreate(e.getKey(), e.getValue());        }    }    /**     * 将当前数据复制到容量更大的数组中。     * 该方法在存储数量达到临界值时自动被调用     *     * 如果当前容量已达到最大值，该方法不在调整map容量大小，但会设置扩容临界值为Integer.MAX_VALUE。     * 这具有防止将来调用的效果     */    void resize(int newCapacity) {     // 如果旧数组到达最大值，设置扩容临界值为Integer.MAX_VALUE        Entry[] oldTable = table;        int oldCapacity = oldTable.length;        if (oldCapacity == MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return;        } //创建指定容量的新数组存储旧数据        Entry[] newTable = new Entry[newCapacity];        transfer(newTable);        table = newTable;        //重新设置扩容临界值        threshold = (int)(newCapacity * loadFactor);    }    /**     * Transfers all entries from current table to newTable.     * 将所有数据从当前数组复制到新数组     *     * HashMap之所以不能保持元素的顺序有以下几点原因：     * 第一，插入元素的时候对元素进行哈希处理，不同元素分配到table的不同位置；     * 第二，容量拓展的时候又进行了hash处理；     * 第三，复制原表内容的时候链表被倒置。     */    void transfer(Entry[] newTable) {       //保留原数组引用        Entry[] src = table;        //新的容量        int newCapacity = newTable.length;        //遍历源数组        for (int j = 0; j < src.length; j++) {         //获取元素e            Entry
              
                e = src[j];            if (e != null) {             // 将原数组中的元素置为null                src[j] = null;                do {                 //循环链表                    Entry
               
                 next = e.next;                    // 根据新的容量计算e在新数组中的索引                    int i = indexFor(e.hash, newCapacity);                    // 将e插入到newTable[i]指向的链表的头部                    e.next = newTable[i];                    newTable[i] = e;                    e = next;                } while (e != null);            }        }    }    /**     *     * 复制所有指定map的映射到当前的map。     * 重复的映射会被替换。(即当前map中的key和指定参数map的key相同，值会被替换)     */    public void putAll(Map
                 m) {        int numKeysToBeAdded = m.size();        if (numKeysToBeAdded == 0)            return;        /*         *  为什么判断条件是numKeysToBeAdded，         *  不是(numKeysToBeAdded+table.length)>threshold?         *         *  这是一种保守的做法，明显地，我们应该在(numKeysToBeAdded+table.length)>threshold         *  的时候去拓展容量，但是考虑到将被添加的元素可能会有Key与原本存在的Key相同的情况，         *  所以采用保守的做法，避免拓展到过大的容量。         */        if (numKeysToBeAdded > threshold) {         //计算目标容量            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);            //目标容量超过最大值， targetCapacity = MAXIMUM_CAPACITY;            if (targetCapacity > MAXIMUM_CAPACITY)                targetCapacity = MAXIMUM_CAPACITY;              //获取大于目标容量最小的2的冥，这就是信容量            int newCapacity = table.length;            while (newCapacity < targetCapacity)                newCapacity <<= 1;            //新容量大于当前数组长度，则扩容            if (newCapacity > table.length)                resize(newCapacity);        } //遍历m中的数据，插入到当前的map中        for (Iterator
                > i = m.entrySet().iterator(); i.hasNext(); ) {            Map.Entry
                 e = i.next();            put(e.getKey(), e.getValue());        }    }    /**     *     * 根据key删除键值对     */    public V remove(Object key) {        Entry
                
                  e = removeEntryForKey(key);        return (e == null ? null : e.value);    }    /**     * 根据key删除键值对     */    final Entry
                 
                   removeEntryForKey(Object key) {     //计算key哈希        int hash = (key == null) ? 0 : hash(key.hashCode());        //计算数组索引        int i = indexFor(hash, table.length);        //链表前一个        Entry
                  
                    prev = table[i];        Entry
                   
                     e = prev; //遍历链表，并删除        while (e != null) {            Entry
                    
                      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;    }    /**     * Special version of remove for EntrySet.     */    final Entry
                     
                       removeMapping(Object o) {        if (!(o instanceof Map.Entry))            return null;        Map.Entry
                      
                        entry = (Map.Entry
                       
                        ) o;        Object key = entry.getKey();        int hash = (key == null) ? 0 : hash(key.hashCode());        int i = indexFor(hash, table.length);        Entry
                        
                          prev = table[i];        Entry
                         
                           e = prev;        while (e != null) {            Entry
                          
                            next = e.next;            if (e.hash == hash && e.equals(entry)) {                modCount++;                size--;                if (prev == e)                    table[i] = next;                else                    prev.next = next;                e.recordRemoval(this);                return e;            }            prev = e;            e = next;        }        return e;    }    /**     *     * 清空map     */    public void clear() {        modCount++;        Entry[] tab = table;        //清空数组        for (int i = 0; i < tab.length; i++)            tab[i] = null;        size = 0;    }    /**     *     * 是否包含指定值     *     */    public boolean containsValue(Object value) {      //value为空  if (value == null)             return containsNullValue();    //遍历数组和链表(双重循环，较耗时)  Entry[] tab = table;         for (int i = 0; i < tab.length ; i++)             for (Entry e = tab[i] ; e != null ; e = e.next)                 if (value.equals(e.value))                     return true;  return false;    }    /**     *     * 是否包含为null的value     */    private boolean containsNullValue() {     //遍历数组和链表(双重循环，较耗时) Entry[] tab = table;         for (int i = 0; i < tab.length ; i++)             for (Entry e = tab[i] ; e != null ; e = e.next)                 if (e.value == null)                     return true; return false;    }    /**     * Returns a shallow copy of this 
                           HashMap instance: the keys and     * values themselves are not cloned.     *     * 克隆(只复制引用)      *      */    public Object clone() {        HashMap
                           
                             result = null; try { //创建一个空的Map     result = (HashMap
                            
                             )super.clone(); } catch (CloneNotSupportedException e) {     // assert false; }        result.table = new Entry[table.length];        result.entrySet = null;        result.modCount = 0;        result.size = 0;        result.init();        //将当前的键值对插入到新的Map        result.putAllForCreate(this);        return result;    }    static class Entry
                             
                               implements Map.Entry
                              
                                {        final K key;        V value;        //对下一个节点的引用        Entry
                               
                                 next;        final int hash;        /**         * Creates new entry.         */        Entry(int h, K k, V v, Entry
                                
                                  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;            //返回是旧的Value            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();            // Key相等且Value相等则两个Entry相等            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;        } // hashCode是Key的hashCode和Value的hashCode的异或的结果        public final int hashCode() {            return (key==null   ? 0 : key.hashCode()) ^                   (value==null ? 0 : value.hashCode());        } // 覆写toString方法，方便调试和查看输出        public final String toString() {            return getKey() + "=" + getValue();        }        /**         * 当调用put(k,v)方法存入键值对时，如果k已经存在，则该方法被调用。         * (没有函数体、default作用域，why？)         */        void recordAccess(HashMap
                                 
                                   m) {        }        /**         * 当Entry被从HashMap中移除时被调用。         * (没有函数体、default作用域，why？)         */        void recordRemoval(HashMap
                                  
                                    m) {        }    }    /**     *     * 根据指定的键，值和哈希码添加新条目到指定的容器     *      */    void addEntry(int hash, K key, V value, int bucketIndex) {     //获取链表头结点 Entry
                                   
                                     e = table[bucketIndex]; //在链表头插入新节点，next指向原来的头结点        table[bucketIndex] = new Entry
                                    
                                     (hash, key, value, e);        //如果size达到扩容临界值，则扩容        if (size++ >= threshold)            resize(2 * table.length);    }    /**     * Like addEntry except that this version is used when creating entries     * as part of Map construction or "pseudo-construction" (cloning,     * deserialization).  This version needn't worry about resizing the table.     *     * Subclass overrides this to alter the behavior of HashMap(Map),     * clone, and readObject.     */    void createEntry(int hash, K key, V value, int bucketIndex) { Entry
                                     
                                       e = table[bucketIndex];        table[bucketIndex] = new Entry
                                      
                                       (hash, key, value, e);        size++;    }    private abstract class HashIterator
                                       
                                         implements Iterator
                                        
                                          {        Entry
                                         
                                           next; // next entry to return        int expectedModCount; // For fast-fail        int index; // current slot        Entry
                                          
                                            current; // current entry        HashIterator() {            expectedModCount = modCount;            if (size > 0) { // advance to first entry             //设置next指向数组第一项                Entry[] t = table;                while (index < t.length && (next = t[index++]) == null)                    ;            }        }        public final boolean hasNext() {            return next != null;        }        final Entry
                                           
                                             nextEntry() {         //迭代过程中map被修改，抛出异常            if (modCount != expectedModCount)                throw new ConcurrentModificationException();            //获取下一项引用            Entry
                                            
                                              e = next;            //为空，抛出异常            if (e == null)                throw new NoSuchElementException(); //(next引用指向下一项的下一项)如果下一项为链表的最后一项，则执行if里面代码(next指向数组的下一个非空索引)            if ((next = e.next) == null) {                Entry[] t = table;                while (index < t.length && (next = t[index++]) == null)                    ;            }            //将当前应用执行下一项，并返回      current = e;            return e;        }        public void remove() {            if (current == null)                throw new IllegalStateException();            if (modCount != expectedModCount)                throw new ConcurrentModificationException();            Object k = current.key;            current = null;            HashMap.this.removeEntryForKey(k);            expectedModCount = modCount;        }    }    private final class ValueIterator extends HashIterator
                                             
                                               {        public V next() {            return nextEntry().value;        }    }    private final class KeyIterator extends HashIterator
                                              
                                                {        public K next() {            return nextEntry().getKey();        }    }    private final class EntryIterator extends HashIterator
                                               
                                                
                                                 > {        public Map.Entry
                                                 
                                                   next() {            return nextEntry();        }    }    // Subclass overrides these to alter behavior of views' iterator() method    Iterator
                                                  
                                                    newKeyIterator()   {        return new KeyIterator();    }    Iterator
                                                   
                                                     newValueIterator()   {        return new ValueIterator();    }    Iterator
                                                    
                                                     
                                                      > newEntryIterator()   {        return new EntryIterator();    }    // Views    private transient Set
                                                      
                                                       
                                                        > entrySet = null;    /**     * Returns a {@link Set} view of the keys contained in this map.     * The set is backed by the map, so changes to the map are     * reflected in the set, and vice-versa.  If the map is modified     * while an iteration over the set is in progress (except through     * the iterator's own 
                                                        remove operation), the results of     * the iteration are undefined.  The set supports element removal,     * which removes the corresponding mapping from the map, via the     * 
                                                        Iterator.remove, 
                                                        Set.remove,     * 
                                                        removeAll, 
                                                        retainAll, and 
                                                        clear     * operations.  It does not support the 
                                                        add or 
                                                        addAll     * operations.     */    public Set
                                                        
                                                          keySet() {        Set
                                                         
                                                           ks = keySet;        return (ks != null ? ks : (keySet = new KeySet()));    }    private final class KeySet extends AbstractSet
                                                          
                                                            {        public Iterator
                                                           
                                                             iterator() {            return newKeyIterator();        }        public int size() {            return size;        }        public boolean contains(Object o) {            return containsKey(o);        }        public boolean remove(Object o) {            return HashMap.this.removeEntryForKey(o) != null;        }        public void clear() {            HashMap.this.clear();        }    }    /**     * Returns a {@link Collection} view of the values contained in this map.     * The collection is backed by the map, so changes to the map are     * reflected in the collection, and vice-versa.  If the map is     * modified while an iteration over the collection is in progress     * (except through the iterator's own 
                                                            remove operation),     * the results of the iteration are undefined.  The collection     * supports element removal, which removes the corresponding     * mapping from the map, via the 
                                                            Iterator.remove,     * 
                                                            Collection.remove, 
                                                            removeAll,     * 
                                                            retainAll and 
                                                            clear operations.  It does not     * support the 
                                                            add or 
                                                            addAll operations.     */    public Collection
                                                            
                                                              values() {        Collection
                                                             
                                                               vs = values;        return (vs != null ? vs : (values = new Values()));    }    private final class Values extends AbstractCollection
                                                              
                                                                {        public Iterator
                                                               
                                                                 iterator() {            return newValueIterator();        }        public int size() {            return size;        }        public boolean contains(Object o) {            return containsValue(o);        }        public void clear() {            HashMap.this.clear();        }    }    /**     *     * 获取键值对value集合     *     * @return a set view of the mappings contained in this map     */    public Set
                                                                
                                                                 
                                                                  > entrySet() { return entrySet0();    } /**  * 获取键值对value集合(获得一个代理类)  */    private Set
                                                                  
                                                                   
                                                                    > entrySet0() {        Set
                                                                    
                                                                     
                                                                      > es = entrySet;        return es != null ? es : (entrySet = new EntrySet());    } /**  * 代理类(没有定义自己的数据,通过迭代器直接遍历map中的数组链表)  */    private final class EntrySet extends AbstractSet
                                                                      
                                                                       
                                                                        > {        public Iterator
                                                                        
                                                                         
                                                                          > iterator() {         //该代理通过迭代器遍历map数据，本身不存储数据            return newEntryIterator();        }        public boolean contains(Object o) {            if (!(o instanceof Map.Entry))                return false;            Map.Entry
                                                                          
                                                                            e = (Map.Entry
                                                                           
                                                                            ) o;            //调用外部类的getEntry方法            Entry
                                                                            
                                                                              candidate = getEntry(e.getKey());            return candidate != null && candidate.equals(e);        }        public boolean remove(Object o) {            return removeMapping(o) != null;        }        public int size() {            return size;        }        public void clear() {            HashMap.this.clear();        }    }    /**     * Save the state of the 
                                                                             HashMap instance to a stream (i.e.,     * serialize it).     *     * @serialData The 
                                                                             capacity of the HashMap (the length of the     *    bucket array) is emitted (int), followed by the     *    
                                                                             size (an int, the number of key-value     *    mappings), followed by the key (Object) and value (Object)     *    for each key-value mapping.  The key-value mappings are     *    emitted in no particular order.     */    private void writeObject(java.io.ObjectOutputStream s)        throws IOException    { Iterator
                                                                             
                                                                              
                                                                               > i = (size > 0) ? entrySet0().iterator() : null; //调用默认的序列化流(序列化threshold, loadfactor等私有变量) s.defaultWriteObject(); // 序列化数组长度 s.writeInt(table.length); // 序列化键值对数 s.writeInt(size);        // 序列化键值对值(非引用) if (i != null) {     while (i.hasNext()) { Map.Entry
                                                                               
                                                                                 e = i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue());     }   }    }    private static final long serialVersionUID = 362498820763181265L;    /**     * 反序列化     */    private void readObject(java.io.ObjectInputStream s)         throws IOException, ClassNotFoundException    { // 根据私有成员创建HashMap s.defaultReadObject();   //根据数组长度初始化数组  int numBuckets = s.readInt();  table = new Entry[numBuckets];  //钩子方法(子类如果要在初始化之前处理某些业务，可覆写该方法)      init();  // Give subclass a chance to do its thing.  //读取要存储键值对的数量    int size = s.readInt(); // 根据键值对数量从流中循环读取并建立键值对 for (int i=0; i