[数据结构与算法]HashMap源码分析

HashMap源码分析（Java8）

一、put()

Map map = new HashMap();
map.put("one", 1);

1.默认值和重要参数

    /**
     * The load factor used when none specified in constructor.
     默认加载因子0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

	//链表转为红黑树的阈值
	static final int TREEIFY_THRESHOLD = 8;
    /**
     * The next size value at which to resize (capacity * load factor).
     *数组扩容的阈值
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;
    /**
     * 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.构造方法

    /**
     * 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
    }

3.put()

往map中加入数据

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

4.hash()

对key的hashCode进行转换，将高位的影响向低位进行传播，使散列集的分布更合理。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

java中>>表示带符号位右移，正数高位补0、负数不1；>>>为不带符号位右移，不论正数还是负数高位通通补0。

(h = key.hashCode()) ^ (h >>> 16)
java中hashcode是32位的，假设key的hash值为0011 0101 0111 1001 1111 1101 1010 1001
  0011 0101 0111 1001 1111 1101 1010 1001
^ 0000 0000 0000 0000 0011 0101 0111 1001
  0011 0101 0111 1001 1100 1000 1101 0000

5.putVal()

第一次添加数据，会先创建一个保存链表（或红黑树）的数组，将前面处理过的hashCode与数组长度-1进行与运算（tab[i = (n - 1) & hash]），得到数据应该保存的位置。(n - 1，因为是从0开始加入元素)

1. 该位置处没有链表，就创建新节点（传入的数据存在节点中），将新创建的节点作为链表头节点存入该位置。
2. 该位置处有链表，遍历链表，如果链表中的节点key与传入的key相同，就将旧有的value替换成新的value，并返回oldValue；如果遍历完链表都没有找到key相同的节点，就创建新的节点并保存在链表尾（尾插法）。
3. 将节点插入链表后，链表的长度大于等于TREEIFY_THRESHOLD = 8时，会将链表转为红黑树。
4. 第一次put数据或者当数组长度大于threshold时会调用resize()创建数组或对数组进行扩容。
5. 插入数据HashMap的size会加1，修改不会。

    /**
     * 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;//初始化数组tab
        if ((p = tab[i = (n - 1) & hash]) == null)//tab中没有存有与该hash值对应的链表
            tab[i] = newNode(hash, key, value, null);//创建新的节点存入tab
        else {//如果该位置已经存有节点
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//头节点key与要插入节点key值相同
                e = p;
            else if (p instanceof TreeNode)//头节点是树类型节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//不是头节点，往后查找
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {//尾节点
                        p.next = newNode(hash, key, value, null);//创建新的节点添加到链表尾部
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//链表新增节点后长度>=8，将其转换为树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//在链表中找到key相同的节点
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key如果key已经存在
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//新的value替换旧的value
                afterNodeAccess(e);
                return oldValue;//返回旧有的value
            }
        }
        ++modCount;//map被修改过的次数
        if (++size > threshold)//map的size+1，size>阈值对map进行扩容，由于size为int类型，threshold最大值为Integer.MAX_VALUE，
            resize();//size++最多只能加到Integer.MAX_VALUE，也就是map的最大存储容量为Integer.MAX_VALUE。
        afterNodeInsertion(evict);
        return null;
    }

6.resize()

1. 第一次put，保存链表的数组不存在，会创建新数组，新数组的大小为16，设置阈值为0.75*16=12

   newCap = DEFAULT_INITIAL_CAPACITY;//第一次put，设为默认容量16
   newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//初始容量满了，进行扩容的阈值

2. 不是第一次put，也是就是map的大小达到了阈值，就要对map进行扩容，创建大小为原数组大小2倍的新数组，将原数组中的数据存入新数组。阈值也是原阈值的2倍，160.75->160.75=32*0.375也就是扩容一次阈值因子减半。

    /**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *	resize调整大小
     * @return the 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) {//当达到最大容量，就不再扩容，并将阈值设为Int最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&//新数组的大小为原数组大小的2倍
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold//阈值也是原阈值的2倍16*0.75->16*0.75=32*0.375也就是扩容一次阈值因子减半
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;//第一次put，设为默认容量16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//初始容量满了，进行扩容的阈值
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;//初始阈值0.75*16=12
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建Node数组，用于存放链表的引用
        table = newTab;//将新数组的引用赋给table
        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)//如果链表只有一个头节点
                    //e.hash & (newCap - 1)=e.hash%newCap，由于位运算较快所以用位运算
                        newTab[e.hash & (newCap - 1)] = e;//就将该节点存入新数组
                    else if (e instanceof TreeNode)//如果数组元素的类型是红黑树
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
							/*假设j=9,oldCap = 16，newCap = 32在存入原数组是是以(e.hash & oldCap - 1)来存的。
							以下两种情况都可能存在同一个链表中e.hash1、e.hash3
					oldCap	0000 0000 0001 0000
				  oldCap-1	0000 0000 0000 1111
					newCap	0000 0000 0010 0000
				newCap -1	0000 0000 0001 1111
					e.hash1 1001 0010 0100 1001  (e.hash & oldCap)==0的情况
					e.hash2	1001 0010 0100 0000  (e.hash & oldCap)==0的情况，这是j=0的情况，它在j=0的时候就会被添加到newTab[0]中，所以不会与后面的情况冲突。
					e.hash3	0000 0000 0001 1001  (e.hash & oldCap)!=0的情况
		(e.hash1 & newCap)	0000 0000 0000 1001  =9	
		(e.hash3 & newCap)	0000 0000 0001 1001  =9+16				
							(e.hash & oldCap) == 0，所以这个条件下hash1保存在loHead，hash3保存在hiHead
							*/
                            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;
    }

二、get()

String value = map.get("one");

1.get()

调用getNode()找到与key对应的节点。

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

2.getNode()

first = tab[(n - 1) & hash]，数组长度与key的hashCode与运算得到链表存储的位置，通过位置直接在数组中获取到链表的头节点。如果头节点key与传入的key相等直接返回，不一样，则轮询链表找到与key相等的节点返回。

    /**
     * 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))))//如果key与头节点的key相等直接返回头节点
                return first;
            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))))//轮询链表，找到key与传入key相等的节点，返回。
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

三、remove()

1.remove()

调用removeNode()，删除成功返回value，失败null。

/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

2.removeNode()

就是通过key的hashCode确定数组下标，通过下标找到链表，轮询链表，找到相应的节点，再将该节点的前驱节点的next指向该节点后继节点的过程。

    /**
     * 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))))//如果头节点就是要删除的节点
                node = p;
            else if ((e = p.next) != null) {//头节点后面还有节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {//找到与key对应的节点
                            node = e;
                            break;//由于到这儿就跳出循环，所前次循环的p就是node的前驱节点
                        }
                        p = e;//前驱节点
                    } while ((e = e.next) != null);//轮询直到尾节点
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {//确定找到的节点
                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;//前驱节点的next指向对应节点的下一个节点
                ++modCount;
                --size;//map大小-1
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }