Java类源码学习(2)-HashMap-1

HashMap是最常用的Map实现

因为源码很长，先列举一些关键点。这些信息在常规使用中可能不容易被了解到

 

1.HashMap中的元素按照hash值分为不同的“桶”（bin），如果散列特性好，元素在桶中分布会比较均匀

2.实际存储用的hash值并非直接使用key.hashCode()，而是又做了一层散列，避免原生的hashCode()散列性不好

3.单个桶尺寸过大时，桶会重构为一个红黑树，以保证O(logN)的效率下限

4.key类型推荐实现Comparable，有助于提高效率

5.KeySet、Values、EntrySet三个视图集合只支持update/remove操作，不支持add

6.迭代子利用modCount属性来实现乐观锁，来如发生竞态的写操作，则迭代子将直接失效（fast-fail）

7.代码用了很多赋值表达式来精简代码量，但是略影响可读性

 

为突出重点，部分相似和非关键代码只保留类/方法签名，不保留实现了

1.java8新增特性：Splitorator（分片迭代子）、

2.KeySet、Values、EntrySet三个辅助集合基本类似，这里只保留KeySet实现

3.简单的getter/setter不保留

 

 以下为精简后的源码，因为量太大一篇放不下，这里先放第一部分，包括主要的入口方法实现。下一篇继续

 

/**
 * <pre>
 *  以哈希表方式实现的Map接口，允许key和value为null
 *  （除非线程安全及允许null值外，HashMap基本与Hashtable等价）
 *  
 *  本类不保证元素的顺序，特别地，顺序也可能随时间改变
 *  
 *  在散列特性较好（元素基本均匀分布于bucket）时，本类get和put操作均为O(1)量级
 *  遍历整个map的时间正比于：HashMap的容量（capacity）+元素总数（注意不只是元素数）
 *  因此最好不要把初始容量设置过高或负载因子（load factor）设置过低
 *  
 *  容量指HashMap中桶的个数，负载因子指HashMap填充到多大比例时允许自动扩容
 *  当size>load factor*capacity时, 哈希表将重组（rehashed），其内部结构会发生改变。rehash以后桶的数量将大致翻倍
 *  根据经验，负载因子=0.75（默认值）时时空效率达到较好的平衡值
 *  设置初始容量时，最好综合考虑元素数的估计值和负载因子，从而减少rehash的次数
 *  
 *  注意如果很多key的hashCode相同必然会降低HashMap的速度
 *  为改善这点，当key实现{@link Comparable}时，本类会利用Comparable的顺序来处理hashCode相同
 *  
 *  本类不是线程同步的，如果多线程访问HashMap，且至少有一个线程进行了结构更改，那么这个需要在外层synchronize 
 *  （结构更改指增删元素，不包含更新已有key的value值）
 *  使用Collections.synchronizedMap(new HashMap(...)是另一种同步方式
 * 
 * 本类返回的所有迭代子都是fail-fast的
 * 即迭代子生成后如果发生任何结构更改（迭代子自身的remove方法除外），迭代子都会抛出{@link ConcurrentModificationException}
 * 注意fail-fast特征并不能严格保证，而只是尽可能实现（有可能漏抛）
 * 因此不能利用是否抛ConcurrentModificationException来保证程序的正确性，这个异常的作用是辅助发现bug
 * 
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 * 
 * @author Doug Lea,Josh Bloch,Arthur van Hoff,Neal Gafter
 * @see Object#hashCode(),Collection,Map,TreeMap,Hashtable
 * @since 1.2
 */
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {

    /**
     * 实现说明
     * 
     * <pre>
     * 本类通常是由桶组成的哈希表，然而当桶的尺寸过大时，会将节点重构为TreeNode（每个节点类似java.util.TreeMap）
     * 大部分方法实现会判断节点的instanceof，如果是TreeNode，则会采取不同的实现方式
     * TreeNode元素支持普通元素的所有操作（对外透明），但提供更快的查询速度
     * 
     * 包含TreeNode的桶首先按hashCode排序，在tie时如果实现了Comparable，则会根据Comparable决定顺序
     * （这里通过反射来判断，参见comparableClassFor方法）
     * TreeNode机制使得在散列特性不好的情况下，也能保证最差O(log n)的时间性能
     * 
     * 由于TreeNode的尺寸是常规节点大约2倍，因此仅当桶的尺寸大于TREEIFY_THRESHOLD时才会使用TreeNode
     * 如果TreeNode的尺寸减小到一定程度（由于remove或resize），还会重新变回普通节点
     * 如果散列值的随机性较好，则桶的尺寸与桶数大致服从Poisson分布，因此基本不会用到TreeNode
     * (http://en.wikipedia.org/wiki/Poisson_distribution)
     * 
     * 一个TreeNode桶的根节点通常是第一个节点，但有些时候（目前只有Iterator.remove）也会是其他元素
     * but can be recovered following parent links  (method TreeNode.root()).
     * 
     * 所有具体实现的内部方法都包含hashcode参数（通常在调用public方法是生成），用以在互相调用时不必重新计算hashCode
     * 大部分方法包含tab参数，其值大部分情况下就是当前的哈希表自身，但在resizing或converting时可能不同
     * 
     * 当桶列表发生建树（treeify）、分裂、退化（untreeify）时，仍然维护其原先链结构(i.e., Node.next) 
     * 树结构中按照hash值、Comparator、tie-breakers三层优先方式进行排序
     * 
     * 树结构与链结构的转换在子类LinkedHashMap中会更复杂一些，本类中预留了一些回调方法给LinkedHashMap
     */

    // 一些常量/////////////////

    // 默认的初始容量，必须是2的幂次
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 建树阈值，桶内元素大于这个数值时会转为TreeNode桶
    // 这个数值至少为8以兼容remove操作时退化为普通节点的机制
    static final int TREEIFY_THRESHOLD = 8;
    // 退树阈值，TreeNode桶内元素小于这个数值时会退化为普通节点
    // 数值必须小于TREEIFY_THRESHOLD，至少为6
    static final int UNTREEIFY_THRESHOLD = 6;
    // 最小的建树容量，这个数值不能小于4 * TREEIFY_THRESHOLD以免resize和treeify机制相互冲突
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * 基础的桶节点（bin node），大部分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;
        }

        @Override
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

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

        @Override
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

    // 一些静态辅助方法/////////////////////

    /**
     * 计算key的hashCode，并将高低16字节异或（注意不是直接key.hashCode()拿来用）
     * 
     * 由于容量是2的幂次，仅高位不同的hashCode总会落到同一个桶（例如整数部分相同的若干浮点数）
     * 这使得原始的hashCode很可能造成不好的散列特性，因此通过xor操作将高位的影响扩散到低位
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 通过反射判断对象x是否实现Comparable<C>接口
     *
     * @return 如果实现了Comparable，返回x的实际类型，也就是Class<C>，否则返回null.
     */
    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c;
            Type[] ts, as;
            Type t;
            ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) {
                    if (((t = ts[i]) instanceof ParameterizedType)
                            && ((p = (ParameterizedType) t).getRawType() == Comparable.class)
                            && (as = p.getActualTypeArguments()) != null && as.length == 1
                            && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

    /**
     * 如果x实际类型是kc，则返回k.compareTo(x)，否则返回0
     * 
     * @param kc 必须实现Comparable
     * @param k 类型为kc
     * @param x 类型无限制
     */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x));
    }

    /**
     * 返回不小于cap的最小的2的幂次
     */
    static final int tableSizeFor(int cap) {
        // 低位全部用1填充
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        // 上下限
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    // 实例属性/////////////////////

    // 实际数据的存储结构，尺寸可能变更
    transient Node<K, V>[] table;
    // entrySet()缓存
    transient Set<Map.Entry<K, V>> entrySet;
    // 实际元素个数
    transient int size;
    // HashMap发生结构变更的计数器，结构变更包括增删元素、rehash等，这个属性为实现迭代子的fast-fail特性
    transient int modCount;
    // 下一个resize的元素个数 (capacity * load factor).
    int threshold;
    // 负载因子
    final float loadFactor;

    // public方法/////////////////////

    /**
     * 含参构造函数
     *
     * @param initialCapacity
     * @param loadFactor
     * @throws IllegalArgumentException initialCapacity<0或loadFactor<=0
     */
    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 other fields defaulted
    }

    /**
     * 根据已有Map构造一个新的HashMap，负载因子取默认值，初始容量根据m.size()确定
     *
     * @throws NullPointerException if m==null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    /**
     * 将m的所有元素放入本对象，实现Map.putAll和构造函数
     *
     * @param m the map
     * @param evict 初始化调用为false，否则为true
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) {
                // 初始化情形，根据m.size初始化threshold
                float ft = (s / loadFactor) + 1.0F;
                int t = ((ft < MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            } else if (s > threshold) {
                // 非初始化，如果m.size已经超过threshold，则立刻resize
                // 注意不包含现有元素，putVal()还有尺寸操作
                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);
            }
        }
    }

    /**
     * 返回key对应的value，如果没有返回null
     *
     * 是否包含通过key.equals()确定
     *
     * @return 注意返回null不一定代表key不存在，有可能对应的value就是null。如需区分可使用{@link #containsKey containsKey}
     * @see #put(Object, Object)
     */
    @Override
    public V get(Object key) {
        Node<K, V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * get的实现
     *
     * @param hash
     * @return the node 不存在返回null
     */
    final Node<K, V> getNode(int hash, Object key) {
        Node<K, V>[] tab; // table的快照
        Node<K, V> first, e;
        int n;
        K k;
        // first = tab[(n - 1) & hash]是hash对应桶的第一个元素
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k)))) {
                return first; // 第一个equal就直接返回了
            }

            // 否则如果是TreeNode就调用TreeNode的get，不是就直接根据.next遍历桶
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K, V>) first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    /**
     * 是否包含，这个实际逻辑与get基本是一样的
     */
    @Override
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

    /**
     * 放入一个kv对，如果key已经存在，则value被替换
     *
     * @return 如果原先包含key，则返回旧的value，否则返回null
     */
    @Override
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * put的实现
     *
     * @param hash
     * @param onlyIfAbsent true表示仅当key不存在的情况才执行put（不修改已存在的值）
     * @param evict false表示创建过程中
     * @return 如果原先包含key，则返回旧的value，否则返回null
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            // 初始化情况
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            // key对应的桶不存在情况（key也必然不存在），new一个新node就行了
            tab[i] = newNode(hash, key, value, null);
        else { // 桶存在情况
            Node<K, V> e; // 表示key的（可能有的）现有节点
            K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; // 第一个就是，直接拿过来
            else if (p instanceof TreeNode) {
                // TreeNode情况
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            } else {
                // 非TreeNode，循环遍历桶
                for (int binCount = 0;; ++binCount) {
                    if ((e = p.next) == null) { // 确实没有，new一个新node
                        p.next = newNode(hash, key, value, null);
                        // 如果桶的尺寸超过了TREEIFY_THRESHOLD，这个桶要转化为树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break; // 找到了，退出循环
                    p = e;
                }
            }
            if (e != null) { // 所有的已存在情况，更新value并返回旧value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); // 子类回调
                return oldValue;
            }
        }

        // 到这说明新加了节点，modCount+1
        // 注意这里只处理增加节点，如果触发resize或者treeify，会在对应方法里继续维护modCount
        ++modCount;
        if (++size > threshold) // size超过阈值，触发resize
            resize();
        afterNodeInsertion(evict); // 子类回调
        return null;
    }

    /**
     * 初始化或扩容
     * 
     * 由于容量是2的幂次，resize后元素下标或者不变，或者增加2的幂次
     *
     * @return 扩容后的表
     */
    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 // 扩容，容量*2
                    && oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        } else if (oldThr > 0) // 初始化情况
            newCap = oldThr;
        else { // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }

        // 更新threshold
        if (newThr == 0) {
            float ft = newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ? (int) ft
                    : Integer.MAX_VALUE);
        }
        threshold = newThr;

        @SuppressWarnings({ "unchecked" })
        Node<K, V>[] newTab = new Node[newCap]; // 新表
        table = newTab;
        if (oldTab != null) { // 移动旧表的元素
            for (int j = 0; j < oldCap; ++j) {
                Node<K, V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null; // 旧表置null以便空间快速回收
                    if (e.next == null) { // 只有一个元素的桶，直接扔到新的桶（新桶一定是空的）
                        newTab[e.hash & (newCap - 1)] = e;
                    } else if (e instanceof TreeNode) { // 处理TreeNode分裂
                        ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    } else { // 普通的桶，逐个处理
                        Node<K, V> loHead = null, loTail = null; // 原桶的首位指针
                        Node<K, V> hiHead = null, hiTail = null; // 新桶(+oldCap)的首位指针
                        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) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    /**
     * 将指定的桶转化为TreeNode
     */
    final void treeifyBin(Node<K, V>[] tab, int hash) {
        int n, index;
        Node<K, V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize(); // 如果容量小于MIN_TREEIFY_CAPACITY，则直接扩容
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K, V> hd = null, tl = null;
            do { // 先把Node链表转成TreeNode链表
                TreeNode<K, V> p = replacementTreeNode(e, null); // 当前节点生成的TreeNode
                if (tl == null) {
                    hd = p;
                } else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);

            // 然后将TreeNode链表转成树
            if ((tab[index] = hd) != null) {
                hd.treeify(tab);
            }
        }
    }

    /**
     * 批量put
     */
    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

    /**
     * 删除对应Key的元素
     *
     * @param key 注意是Object，类型不要传错
     * @return 如果key存在，返回删除前的value，否则返回null
     */
    @Override
    public V remove(Object key) {
        Node<K, V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
    }

    /**
     * 删除节点实现
     *
     * @param hash
     * @param key
     * @param value 如果matchValue=true，表示匹配的value，否则无作用
     * @param matchValue true表示仅当key对应value等于matchValue时才删除
     * @param movable false表示不移动其他元素（迭代子使用）
     * @return 如果删了，返回被删的元素，否则返回null
     */
    final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue,
            boolean movable) {
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, index;
        if ((tab = table) != null && (n = tab.length) > 0
                && (p = tab[index = (n - 1) & hash]) != null) {
            Node<K, V> node = null, e; // node为待删元素
            K k;
            V v;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                node = p; // 第一个就匹配，直接就他了
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode) // 如果是TreeNode，从TreeNode取key的元素
                    node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
                else { // 否则遍历链表找
                    do {
                        if (e.hash == hash
                                && ((k = e.key) == key || (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }

            if (node != null
                    && (!matchValue || (v = node.value) == value || (value != null && value
                            .equals(v)))) { // 这条件表示确实要删

                // TreeNode就按TreeNode删，否则在链表删
                if (node instanceof TreeNode) {
                    ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                } else if (node == p)
                    tab[index] = node.next;
                else {
                    p.next = node.next;
                }
                ++modCount; // 删除元素造成的结构变更
                --size;
                afterNodeRemoval(node); // 子类回调
                return node;
            }
        }
        return null;
    }

    /**
     * 清空（全部删除）
     */
    @Override
    public void clear() {
        Node<K, V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i) { // 所有的桶都置为null
                tab[i] = null;
            }
        }
    }

    /**
     * 包含（一个或多个）value。因为没有倒排，这个方法要遍历全表，慎用
     *
     * @param value
     */
    @Override
    public boolean containsValue(Object value) {
        Node<K, V>[] tab;
        V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) { // 遍历表
                for (Node<K, V> e = tab[i]; e != null; e = e.next) {
                    // 遍历桶。注意TreeNode还是维持打平的链表关系，所以不用特别处理
                    if ((v = e.value) == value || (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }