android进阶篇05、HashMap源码解析

一、构造方法与主要成员属性

hashMap在java1.8之前使用数组+链表的方式实现，从java1.8开始使用数组+链表+红黑树的方式实现；

1、构造方法

HashMap中公有的构造方法有以下四种；

第一种可以自己指定初始容量和加载因子，注释1处作用是将我们传入的初始容量变为2的次幂，使用2的次幂主要是为了提高计算性能，包括扩容和index的计算时，因为在通过hash值计算index索引值的时候，方法是hash值对容量求模，其实也就是按位&，如果是2的次幂，那2的次幂-1用二进制表示就是全为1，可以充分利用每一位，从而提高效率；

第二种通过传入初始容量，然后加载因子就是默认的0.75；

第三种无参构造方法，默认初始容量是16，默认加载因子0.75；

第四种通过另一个map创建一个新map；

//一
public HashMap(int initialCapacity, float loadFactor) { 
    、、、
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); //1
}

//二
/**
 * 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 default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//四
/**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
复制代码

2、主要成员属性

注释1处表示初始容量16；将1左移四位，二进制也就是10000，即16；

注释2处表示最大容量，即2的30次方；

注释3处表示初始默认加载因子，为0.75，当元素大于容量*加载因子时，就需要进行扩容操作了；

注释4处同一个索引处hash碰撞的个数达到8个以上时，并且总元素个数大于64，转用红黑树存储，而不再使用链表，在后边分析put方法时会详细介绍；

注释5处的table是hashMap中存储元素的数组；

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //1

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30; //2

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f; //3

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8; //4

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table; //5
复制代码

3、节点内部类

链表节点，当发生hash碰撞时，同一个索引下的元素使用链表存储；

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;
    }
    、、、
}
复制代码

红黑树节点，当发生hash碰撞时，同一个索引下的元素的个数大于8个时会由链表转为红黑树存储；

static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<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;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    、、、
}
复制代码

二、主要方法介绍

1、put方法

首先介绍最常用的put方法，put方法中又调用了putVal方法；

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
复制代码

我们接着看真正执行put操作的putVal方法；从注释可知，第一个参数为key的hash值，第二个参数为key，第三个参数为value，第四个参数为true表示不会修改已经存在的键值对，第五个参数为false表示table为创建模式，我们在这个方法中并没有用到这个参数；返回值是key对应的oldValue，如果没有则为null；

注释1处表示table为空时，首先初始化table，这个table默认初始化就是在第一次put的时候，并不是在构造方法或者别的地方，这样设计也是为了优化性能；

注释2处表示索引i处没有元素，不存在hash碰撞，此时直接将键值对插入table[i]处，我们看注释2处上一句计算索引i是怎么计算的，i = (n – 1) & hash，这个操作等同于hash值对容量n求模，不过这种&运行效率更高；注释2处的newNode即返回了一个链表的Node节点，从而也印证了元素存储的是链表；

注释3处else分支表示发生hash碰撞；

注释4处表示链表的第一个元素的key就跟要插入的key相同，直接将p赋值给e，后边统一操作；

注释5处表示如果此索引内的元素已经是用红黑树存储了，那么也通过红黑树的方式插入数据；

注释6处表示到达了链表最后一个节点，则在注释7处直接在链表尾部插入元素即可；

注释8处表示某个索引内的hash碰撞数到达8个时，转为红黑树存储；

注释9处表示已经存在key值，直接break跳出循环后续操作；

注释10处将e赋值给p，表示继续遍历hash碰撞中的下一个元素(注释6处)；

注释11处的分支表示原来存在key对应的键值对，首先在注释11处将oldValue保存，然后在注释12处将value值设置为新value值，最后在注释13处返回key对应的oldValue；

注释14表示原来不存在key对应的键值对，因此需要元素个数+1；如果注释14元素个数大于阈值，则会在注释15处执行resize进行扩容，也就是重新对HashMap中的元素进行存放；

注释16返回null表示原来不存在此key对应的键值对；

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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; //1
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = new Node(hash, key, value, null); //2
    else { //3
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; //4
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //5
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { //6
                    p.next = new Node(hash, key, value, null); //7
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash); //8
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break; //9
                p = e; //10
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value; //11
            if (!onlyIfAbsent || oldValue == null)
                e.value = value; //12
            afterNodeAccess(e);
            return oldValue; //13
        }
    }
    ++modCount;
    if (++size > threshold) //14
        resize(); //15
    afterNodeInsertion(evict);
    return null; //16
}
复制代码

2、get方法

分析完了放元素的方法，我们再来分析一下取元素的方法get；可见get方法又调用了getNode方法；

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
复制代码

我们接着看真正执行get操作的getNode方法，这个方法跟put方法其实是对应的，理解了put再理解get很容易；

注释1处表示此key对应的索引处不存在hash碰撞，我们直接方法返回此索引处的元素即可；

注释2处的分支表示存在hash碰撞；

注释3处表示hash碰撞内的元素是通过红黑树存储的；

注释4处表示是通过链表存储的，通过注释4处的do while循环去遍历链表，如果找到就通过注释5处的return语句返回；

注释6处表示遍历完HashMap也没找到key对应的节点，返回null；

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    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; //1
        if ((e = first.next) != null) { //2
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key); //3
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e; //5
            } while ((e = e.next) != null); //4
        }
    }
    return null; //6
}
复制代码

3、remove方法

增删改查现在只剩删除方法了(put方法包含了增和改，get方法包含查)，最后看一下删除方法remove；

注释1处的分支代表此key对应的键值对不存在hash碰撞，因此直接将此索引处的元素p赋值给node；

注释2处表示存在hash碰撞并且是红黑树存储方式，则通过红黑树的查询方式将此节点查询出来并赋给node节点；

注释3处表示存在hash碰撞并且存储方式是链表，此时通过do while循环遍历查找元素；

注释4处的分支表示查找到了此node节点，对此node节点真正执行删除操作了；

注释5表示从红黑树中删除节点；

注释6表示直接将此索引处的值指向node的next；

注释7表示从链表中删除节点；

注释8返回删除的节点；

注释9表示此HashMap中不存在此key对应的键值对，直接返回null；

/**
 * Implements Map.remove and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
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; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //1
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                //2
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key); 
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                         //3
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //4
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                //5
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                //6
                tab[index] = node.next;
            else
                //7
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            //8
            return node;
        }
    }
    //9
    return null;
}
复制代码