Android源码简单集合之HashMap

学习无止境，探索无止境。

1. HashMap简介

HashMap是JDK提供的集合工具类，采用key/value的方式存储键值对，每个key对应一个value。

1.1. 特点：

• 高效查询和修改
• 平均时间复杂度O(1)
• 线程不安全
• 乱序存储

1.2. 继承关系：

HashMap继承了AbstractMap，实现了Map、Serializable和Cloneable接口。

• HashMap支持Map的所有方法
• HashMap支持序列化
• HashMap支持克隆

根据图中的继承关系，发现一个有趣的问题，为什么HashMap继承了AbstractMap，同时实现Map接口？

比较合理的解释：这是个错误，如果真的有什么作用的话，可以获取到HashMap实现的接口，通过HashMap.class.getInterfaces()方法。答案链接

1.3. 存储结构：

在HashMap中采用了数组+链表+红黑树的结构存储数据
在查找和修改数据时，根据元素的hash值计算出在数组中的索引位置，然后在位置所记录的链表中查找和修改对应的元素。

当单链表的元素长度达到8个时，链表转换成红黑树，提高效率。

当红黑树的元素个数小于等于6个时，将红黑树转化为单链表。

数组的查询的时间复杂度为O(1)，链表长度为n时查询的时间复杂度为O(n)，红黑树的元素为n时查询的时间复杂度为O(log n)

2. 源码分析

2.1. 属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;	// 16，数组默认初始大小
static final int MAXIMUM_CAPACITY = 1 << 30;		// 1073741824，数组最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;		// 装载因子默认值
static final int TREEIFY_THRESHOLD = 8;		        // 树化因子，当链表长度达到8时转成红黑树
static final int UNTREEIFY_THRESHOLD = 6;		// 反树化因子，当红黑树元素降为6时转成链表
static final int MIN_TREEIFY_CAPACITY = 64;		// 当数组大小达到64的时候进行树化
transient Node<K,V>[] table;				// 数组
transient Set<Map.Entry<K,V>> entrySet;			// 用于遍历的set缓存
transient int size;					// 数组大小
transient int modCount;					// 记录修改次数
int threshold;						// 扩容因子，当数组大小大于该参数时，数组扩容
final float loadFactor;					// 装载因子，用于计算扩容因子大小
复制代码

2.2. 内部节点

2.2.1. Node节点

Node节点是数组中的元素和单链表的节点。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;			// 元素hash
        final K key;			// 元素key
        V value;			// 元素value
        Node<K,V> next;			// 元素的下一个节点
}
复制代码

2.2.2. TreeNode节点

红黑树的典型节点。

// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
        TreeNode<K,V> parent;  	// 父节点
        TreeNode<K,V> left;	// 左子节点
        TreeNode<K,V> right;	// 右子节点
        TreeNode<K,V> prev;    	// 前置节点，删除时快速定位前置节点
        boolean red;		// 红或黑节点
}
复制代码

2.3. HashMap构造方法

// 设置数组初始容量和加载因子
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);    // 根据数组容量和装载因子计算扩容因子
}

// 数组初始容量参数构造方法，调用HashMap(int, float)，加载因子采用默认值
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 空参构造方法，所有属性采用默认值
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 根据map创建新的Map集合
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
复制代码

2.4. get方法

public V get(Object key) {
    Node<K,V> e;
    // hash(key) 计算key的hash值，用于散列在数组中的位置
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

// 查询节点方法
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;
    Node<K,V> first, e;
    int n;   // 记录table数组长度
    K k;
    // table是数组
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {   // (n - 1) & hash 散列在数组中的索引位置，first是数组索引处记录的表头节点

        // 从表头开始查询，hash值和key是否相同
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;   // first节点匹配
        // 取出下一个节点
        if ((e = first.next) != null) {
            // 节点是红黑树节点，按照树的结构查询
            if (first instanceof TreeNode)
                // 查询树节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // 按照链表的方式查询，比对单链表节点的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;
}

// 查询树节点方法
final TreeNode<K,V> getTreeNode(int h, Object k) {
    // (parent != null) ? root() : this 先查询到红黑树的根节点，然后从根节点开始 find
    return ((parent != null) ? root() : this).find(h, k, null);
}

// 根节点方法
final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        // 当前节点的父节点是null，则该节点是根节点
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

// 红黑树是有序的存储结构，左节点比父节点小，右节点比父节点大
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        // ph: 父节点hash
        int ph, dir;
        K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            // 左节点
            p = pl;
        else if (ph < h)
            // 右节点
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // 找到节点直接返回
            return p;
        else if (pl == null)
            // 左节点为null，查右节点
            p = pr;
        else if (pr == null)
            // 右节点为null，查左节点
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            // 通过compare方法比较key值的大小决定使用左子树还是右子树
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            // 如果以上条件都不通过，则尝试在右子树查找
            return q;
        else
            // 都没找到就在左子树查找
            p = pl;
    } while (p != null);
    return null;
}
复制代码

• 计算key的hash值
• 通过hash值散列在数组中的索引位置
• 如果索引位置元素为空，则返回null
• 如果索引位置的头结点hash值和key值匹配，则返回头结点
• 如果取出头结点的next节点为树节点，通过getTreeNode方法查找树中有匹配节点，则返回该节点
  1. 节点是树节点，红黑树查询方式，扩展下红黑树的存储是有序且平衡的，查询效果类似与二分方式，红黑树知识
• 如果上述三种情况都不是，则遍历链表有匹配节点，则返回该节点

2.5. put方法

public V put(K key, V value) {
    // hash(key) 计算key的hash值，用于散列在数组中的位置
    return putVal(hash(key), key, value, false, true);
}

// 修改方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    // 存储元素的数组为空时，通过resize方法对数组进行初始化，数组初始长度未指定时，默认为16
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // p是tab[(n-1) & hash]，进行hash散列计算出数组索引，在数组索引处元素为空，直接创建新节点放入数组，作为表头
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 元素在链表中或树中
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 在数组索引处元素非空，比较hash值和key是否相同，相同则更新表头元素
            e = p;
        else if (p instanceof TreeNode)
            // p元素是树节点，通过红黑树的方式进行修改
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍历单链表节点
            for (int binCount = 0; ; ++binCount) {
                // 取出下一个节点，如果节点为null，创建新节点直接放入表尾，退出遍历
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD树化因子，链表长度大于等于树化因子8，将链表树化
                    // 减一是因为，表头作为数组元素，不计入树化范围
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到key相同的节点，退出遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 继续下一个节点
                p = e;
            }
        }
        // e不为空，说明链表中存在key相同的节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 将节点的值替换为新值
            // onlyIfAbsent为true时，不改变旧值，通过该方法putIfAbsent不会修改旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 修改操作，计数加一
    ++modCount;
    // 元素数量大于扩容因子，进行扩容
    if (++size > threshold)
        resize();
    // 节点插入后继续的工作，LinkedHashMap有用到
    afterNodeInsertion(evict);
    return null;
}

// 树化方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果数组长度小于树化长度64，则对数组进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将链表节点，替换成树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 真正进行树化的操作
            hd.treeify(tab);
    }
}

// 扩容方法
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;   // 旧数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;    // 旧容量
    int oldThr = threshold;    // 旧扩容因子
    int newCap, newThr = 0;
    // 原容量大于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)
            // 扩容后容量小于上限 且 原容量大于默认初始容量(16)时，扩容因子扩大一倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
    // 不是通过默认构造方法创建的map，首次插入元素会走到这里
    // 如果旧容量为0 且 旧扩容因子大于0，则把新容量赋值为旧扩容因子
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
    // 调用默认构造方法创建的map，第一次插入元素会走到这里
    // 将容量置为默认大小(16)，新扩容因子为 容量*装载因子
        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置为新数组
    table = newTab;
    if (oldTab != null) {
    // 将旧数组内的元素散列后放入新数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果数组j索引处只有一个元素，则重新散列并放到新数组中
                // 因为每次都扩容两倍，所以这里的第一个元素搬移到新桶的时候新桶肯定还没有元素
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果第一个元素是树节点，则把这颗树打散成两颗树插入到新桶中去
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 数组j索引处，有链表
                else { // preserve order
                    // 将链表分化成两个链表
                    // eg: 容量为4，数组j=3处的链表有3、4、7元素，分化后为
                    // 3 & 4 == 0, 放入低位链表
                    // 4 & 4 != 0, 放入高位链表
                    // 7 & 4 != 0, 放入低位链表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    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);
                    // 低位链表放入数组j位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 高位链表放入数组j+oldCap位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
复制代码

put方法流程图如下：

• 计算key的hash值
• 如果数组数量为0，则初始化数组
• 通过hash值散列数组中的索引位置
• 如果数组索引处没有元素，则直接插入新节点
• 如果数组索引处的元素hash值和key值匹配，则索直接修改索引处节点
• 如果数组索引处节点是树节点，则调用putTreeVal方法修改或插入树节点
• 如果不是以上三种情况，如果遍历数组索引处的链表有匹配节点，则修改链表中匹配节点的值
• 遍历数组索引处的链表没有匹配节点，则在链表最后插入一个新节点
• 如果插入了新元素，如果链表长度大于等于7(8-1)需要树化，如果元素数量加1大于扩容因子需要扩容

2.6. remove方法

public V remove(Object key) {
    Node<K,V> e;
    // hash(key) 计算key的hash值，用于散列在数组中的位置
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

// 删除节点的方法
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;
    // p表头节点
    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;
        // 比较表头hash值和key值是否相同，如果相同，则p节点为要查询的节点node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 依次遍历链表或树的后续节点
        else if ((e = p.next) != null) {
            // p为树节点，按照树节点方式查询到node节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
            // 遍历单链表节点，找到匹配的node节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // node不为空，说明找到匹配节点
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // node节点为TreeNode类型，删除树节点，同时要保证红黑树的平衡
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // node为表头时，将表头的next节点作为新表头
            else if (node == p)
                tab[index] = node.next;
            // 将node节点的前置节点的next指向node节点的next
            else
                p.next = node.next;
            // 修改操作，计数加一
            ++modCount;
            // 元素数量减一
            --size;
            // 删除节点后的工作，LinkedHashMap会用到
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}
复制代码

• 计算key的hash值
• 通过hash值散列在数组中的索引位置
• 如果数组索引处的元素为空时，结束
• 如果数组索引处的元素hash值和key值匹配，则头结点为要删除的节点，记录节点
• 从头结点的next节点开始，如果第一个next节点是树节点，通过getTreeNode查找树中有匹配节点，记录节点
• 如果上述三种情况都不是，如果遍历数组索引处的链表有匹配节点，记录节点
• 如果记录节点不为空，则说明map中有该节点
• 如果记录节点是树节点，通过removeTreeNode方法删除该节点
• 如果记录的节点是数组元素，将数组元素的next节点放入数组索引处
• 如果是链表中节点，将p的next指向记录节点的next节点，p是记录节点的前置节点

通过对源码的分析，以下问题也可以轻松得出结论：

1. 链表和树的转换临界问题？

• 链表长度(含表头)大于等于8时且数组长度大于64时，链表进行树化
• 树节点数量小于等于6时，树转成链表

2. 元素添加时的扩容问题？

• 当添加新元素后，元素数量大于扩容因子时，数组扩大一倍，扩容因子=数组长度(默认16)*装载因子(默认0.75)

3. 扩容时重新hash散列的规则问题？

• 数组容量扩大，旧数组中散列的元素位置，需要重新散列，同一个链表中的元素划分到低位链表(hash & oldCap == 0)和高位链表(hash & oldCap != 0)两个链表中，oldCap表示旧数组长度

补充: 关于红黑树问题，可以参考相关知识，具体去分析在红黑树中是如何实现节点的插入和删除节点，需要了解红黑树的左旋，右旋等保持树平衡的问题。

结语: HashMap的主要操作已经分析完毕，HashMap的数据存储结构采用了，数组+链表+红黑树的方式，在存储大量元素时，通过红黑树结构会更加高效。