TUNANのBlogHomeArchivesTagsCategories
HashMap1.8源码分析
|Java
Word count: 2k|Reading time: 9 min

该篇博客不适合小白，只做针对性的api源码解析，以及适合我自身的案例研究

HashMap构造函数

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	
	// 初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

	// 最大容量2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;

	// 负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

	// 链表转树的阈值
    static final int TREEIFY_THRESHOLD = 8;

	// 树转链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;

	// 树最小的子节点数
    static final int MIN_TREEIFY_CAPACITY = 64;

	// 默认初始容量是16，负载因子是0.75
	public HashMap() {
		this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
	}

	// 只传入初始容量
	public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

	// 传入初始容量和负载因子
    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);
    }
	
	// 传入一个map集合
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
}

HashMap的数据结构

static class Node<K,V> 
    implements Map.Entry<K,V> {
    // hash值
    final int hash;
    // key值
    final K key;
    // value值
    V value;
    // 下一个Node的指针
    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;
    }

    // 得到key值
    public final K getKey()        { return key; }
    // 得到vaue值
    public final V getValue()      { return value; }
    // 重写toString
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        // hashCode值等于key和value的hash值取反
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    // 修改value
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    // 判断内容相等
    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;
    }
}

重温jdk1.7中如何触发死循环的

单线程情况下，rehash无问题。下图演示了单线程条件下的rehash过程

单线程rehash

多线程并发下的rehash

这里假设有两个线程同时执行了put操作并引发了rehash，执行了transfer方法，并假设线程一进入transfer方法并执行完next = e.next后，因为线程调度所分配时间片用完而“暂停”，此时线程二完成了transfer方法的执行。此时状态如下。

多线程rehash

接着线程1被唤醒，继续执行第一轮循环的剩余部分

e.next = newTable[1] = null
newTable[1] = e = key(5)
e = next = key(9)

结果如下图所示

多线程rehash

接着线程1被唤醒，继续执行第一轮循环的剩余部分

e.next = newTable[1] = null
newTable[1] = e = key(5)
e = next = key(9)

结果如下图所示

多线程rehash

接着执行下一轮循环，结果状态图如下所示

多线程rehash

此时循环链表形成，并且key(11)无法加入到线程1的新数组。在下一次访问该链表时会出现死循环。

resize()

初始化容量16，负载因子0.75，尾插法，扩容2倍，8个节点转树，6个节点转链表，不会产生死循环

final Node<K,V>[] resize() {
	// 理解为node/hashmap
    Node<K,V>[] oldTab = table;
	// 拿到旧的hashmapnode的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
	// 旧hashmap的扩容阈值
    int oldThr = threshold;
	// 新hashmap的容量和阈值初始化为0
    int newCap, newThr = 0;
	// 拿到新hashmap的容量
    if (oldCap > 0) {
        // 旧的hashmap容量大于最大值，则直接返回
		if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
		// 旧的hashmap扩容为原来的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
    }
	// 旧的hashmap长度等于0，但是阈值大于0，则把阈值赋值为hashmap的长度
    else if (oldThr > 0) 
        newCap = oldThr;
	// 如果旧的hashmap的长度和阈值都为0，则赋初始值
    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
	// 拿到新阈值的值 => 新容量*0.75
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
	// 赋值给threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
	// 创建一个新的容量的Node
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	// 赋值给table
    table = newTab;
	// 尾插法，将旧的table的数据查询出来再插入新的table
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    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;
                        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;
                    }
                }
            }
        }
    }
	// 返回新的Node
    return newTab;
}

hash()

使用时异或求hash值，比取余更快更均匀

static final int hash(Object key) {
    int h;
    // '^' 异或操作，相同则为0，不同则为1
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put()

如果插入的位置为空则直接插入，如果有值但是key的hash或者内容相等，则覆盖，如果能转树则转树。

public V put(K key, V value) {
    // 调用putVal方法
    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;
    // 如果当前数组table为null，进行resize()初始化，n = resize的长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果table[i]为空，那就把这个键值对放在table[i]
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 当另一个key的hash值已经存在时
    else {
        Node<K,V> e; K k;
        // 如果节点的key的hash值和容量都相同，则覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // Node转成树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 遍历table[i]所对应的链表，直到最后一个节点的next为null或者有重复的key值
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // key重复，替换value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 触发扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get()

首先通过hash函数找到索引，然后判断map为null，再判断table[i]是否等于key，然后在找与table相连的链表的key是否相等。

public V get(Object key) {
	Node<K,V> e;
	// 如果拿出来的不为null，就返回value
	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; 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;
		
	if ((e = first.next) != null) {
		//// 从树中拿
		if (first instanceof TreeNode)
			return ((TreeNode<K,V>)first).getTreeNode(hash, key);
		do {
			// 循环链表，key的hash值或者key的内容相同，则返回
			if (e.hash == hash &&
				((k = e.key) == key || (key != null && key.equals(k))))
				return e;
			} while ((e = e.next) != null);
		}
	}
	// 没找到 返回null
	return null;
}

面试题：如果new HashMap(19)，bucket数组多大？

  • HashMap的bucket 数组大小一定是2的幂，如果new的时候指定了容量且不是2的幂，实际容量会是最接近(大于)指定容量的2的幂，比如 new HashMap<>(19)，比19大且最接近的2的幂是32，实际容量就是32。

基础知识

位运算

Author: Tunan
Link: http://yerias.github.io/2019/01/04/java/5/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Java