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

2、HashMap的部分属性

    private static final long serialVersionUID = 362498820763181265L;

     //The default initial capacity - MUST be a power of two.

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //jdk1.6直接写16，这效率更快？？

     // The maximum capacity,MUST be a power of two <= 1<<30.

    static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次方

    static final float DEFAULT_LOAD_FACTOR = 0.75f; //填充比，装载因子

    /**（jdk1.8新加）

     * The bin count threshold for using a tree rather than list for a

     * bin.当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树.

     * 2< value<=8 时to mesh with assumptions in  tree removal about conversion back to plain bins upon shrinkage.

     *链表转为树，binCount>=TREEIFY_THRESHOLD-1，-1 for 1st。

     */ //当某个桶中的键值对数量大于8个【9个起】，且桶数量大于等于64，则将底层实现从链表转为红黑树   

    static final int TREEIFY_THRESHOLD= 8; //jdk1.8新加

    static final int UNTREEIFY_THRESHOLD = 6; //jdk1.8新加

    static final int MIN_TREEIFY_CAPACITY = 64; //jdk1.8新加

    /* ---------------- Fields -------------- */

    // jdk1.6 为 transient Entry[] table;

    transient Node<K,V>[] table; //存储元素(位桶)的数组,length power of two

    transient Set<Map.Entry<K,V>> entrySet;

    transient int size; // key-value对，实际容量

    transient int modCount; //结构改变次数，fast-fail机制

    int threshold; // 新的扩容resize临界值,当实际大小(容量*填充比)大于临界值时，会进行2倍扩容

    final float loadFactor;

Node 内部类

        是HashMap内部类（jdk1.6就是Entry），继承自 Map.Entry这个内部接口，它就是存储一对映射关系的最小单元，也就是说key，value实际存储在Node中。与1.6相比，修改了 hashCode()、equals()方法【直接调用Object的hashCode、equals方法，而不是copy代码过来】，去掉了toString()、recordAccess(HashMap<K,V> m)【the value in an entry is overwritten时调用】、recordRemoval(HashMap<K,V> m)【remove entry时调用】方法。【键值对】

static class Node<K,V>implements Map.Entry<K,V> {
        final int hash; //结点的哈希值，不可变
        final K key;
        V value;
        Node<K,V> next; //指向下一个节点
 
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
      // 由直接实现 变为 调用Object的HashCode，实际是一样的
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        } //按位异或^不同为真,数a两次异或同一个数b(a=a^b^b)仍然为原值a。
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            returnoldValue;
        }  // 优化逻辑
        public final boolean equals(Object o) {//改为调用Object的equals
            if (o == this) //内存地址(1.8新增)
                return true;
            if (o instanceof Map.Entry) {//1.6中!(instanceof)返回false
                Map.Entry<?,?> e = (Map.Entry<?,?>)o; //新加<?,?>泛型
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
/*  jdk 1.6 Entry 的equals方法
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;
        } */

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev; // needed to unlink next upon deletion,节点的前一个节点
        boolean red; //true表示红节点，false表示黑节点
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        /**
         * Returns root of tree containing this node.获取红黑树的根
         */
        final TreeNode<K,V> root() { 
           for (TreeNode<K,V> r=this, p;;){//p定义,int a=1,b;不能直接输出b(未初始化)
                if ((p = r.parent) == null)  //若改为类似并查集的路径压缩（结构改变）
                    return r;
                r = p;
            }
        }
        /**
         * Ensures that the given root is the first node of its bin.
         */ //确保root是桶中的第一个元素，将root移到桶中的第一个【平衡思想】
        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {}
        /**
         * Finds the node starting at root p with the given hash and key.
         * The kc argument caches comparableClassFor(key) upon first use
         * comparing keys.
         *///查找hash为h，key为k的节点  
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) { // 详见get相关
              TreeNode<K,V> p = this;   ……   }
        /**
         * Calls find for root node.
         */ //获取树节点，通过根节点查找 
        final TreeNode<K,V> getTreeNode(int h, Object k) { // 详见get相关
            return ((parent != null) ? root() : this).find(h, k, null);
        }
        /**
         * Tie-breaking utility for ordering insertions when equal
         * hashCodes and non-comparable. We don't require a total
         * order, just a consistent insertion rule to maintain
         * equivalence across rebalancings. Tie-breaking further than
         * necessary simplifies testing a bit.
         */ //比较2个对象的大小 
        static int tieBreakOrder(Object a, Object b) {}
        /**
         * Forms tree of the nodes linked from this node.
         * @return root of tree
         */ //将链表转为二叉树
        finalvoid treeify(Node<K,V>[] tab) {} //根节点设置为黑色 
        /**
         * Returns a list of non-TreeNodes replacing those linked from
         * this node.
         */ //将二叉树转为链表 
        final Node<K,V> untreeify(HashMap<K,V> map) {}
        /**
         * Tree version of putVal.
         */ //添加一个键值对 
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       inth, K k, V v) {}
        /**
         * Removes the given node, that must be present before this call.
         * This is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. So instead we swap the tree
         * linkages. If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {}
        /**
         * Splits nodes in a tree bin into lower and upper tree bins,
         * or untreeifies if now too small. Called only from resize;
         * see above discussion about split bits and indices.
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */ //将结点太多的桶分割  
        finalvoid split(HashMap<K,V> map, Node<K,V>[] tab, intindex, intbit) {}
        /* --------------------------------------------------*/
        // Red-black tree methods, all adapted from CLR
        //左旋转
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {}
        //右旋转
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {}
         //保证插入后平衡，共5种插入情况
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {}
         //删除后调整平衡 ，共6种删除情况
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {}
        /**
         * Recursive invariant check
         */ //检测是否符合红黑树 
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {}
}

3、HashMap的4种构造方法

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;
       this.threshold=tableSizeFor(initialCapacity);
    }

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; //all default即16;0.75
    }

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

public HashMap(Map<? extends K, ? extends V> m) { // 参数本就是Map
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
        putMapEntries(m, false); // 仅putAll时传参为true
    }

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) {// pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY); // 取较小值
                if (t > threshold) // t 大于扩容临界值
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict); //HashMap核心方法，后讲
            }
        }
    }

简而言之：length为2的幂保证了按位与最后一位的有效性，使哈希表散列更均匀。

// Initializes or doubles table size，两倍扩容并初始化table
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0; // 新容量，新阀值
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab; //到达极限，无法扩容
            }
            else if((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold阀值
       }
      // oldCap=0 ,oldThr>0，threshold(新的扩容resize临界值)
       else if (oldThr > 0) 
           newCap = oldThr; //新容量=旧阀值（扩容临界值）
       else {     // oldCap=0 ,oldThr=0，调用默认值来初始化
         newCap = DEFAULT_INITIAL_CAPACITY;
         newThr=(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr== 0) { //新阀值为0，则需要计算新的阀值 
           float ft = (float)newCap * loadFactor;
           newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr; //设置新的阀值
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建新的桶
        table = newTab; 
         // table初始化,bucket copy到新bucket，分链表和红黑树
        if (oldTab != null) { // 不为空则挨个copy，影响效率！！！
            for (int j = 0; j < oldCap; ++j) {
               Node<K,V> e;
               if ((e = oldTab[j]) != null) { //先赋值再判断
                  oldTab[j] = null; //置null，主动GC
                  //如果该桶只有一个元素，重新计算桶位，则直接赋到新的桶里面
                  if (e.next == null) 
                //1.6的indexFor，计算key;tableSizeFor性能优化
                    newTab[e.hash &(newCap - 1)]= e; //hash&(length-1)
                  else if (e instanceof TreeNode) // 红黑树
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                  else { //链表，preserve order保持顺序
                        //一个桶中有多个元素，遍历将它们移到新的bucket或原bucket
                        Node<K,V> loHead = null,loTail = null;//lo原bucket的链表指针
                        Node<K,V> hiHead = null, hiTail = null;//hi新bucket的链表指针
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {//还放在原来的桶
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e; //更新尾指针
                            }
                            else {//放在新桶
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null); //
                        if (loTail != null) { //原bucket位置的尾指针不为空(即还有node)
                            loTail.next = null; //链表最后得有个null
                            newTab[j] = loHead;//链表头指针放在新桶的相同下标(j)处
                        }
                        if (hiTail != null) {  //放在桶 j+oldCap
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;//j+oldCap见下
                        }
                    }
                }
            }
        }
        return newTab;
    }