JDK之HashMap源码剖析

基于java version "1.8.0_321"

类继承关系

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {}

HashMap继承自抽象类AbstractMap，并实现了Map、Cloneable、Serializable。

AbstractMap

public abstract class AbstractMap<K,V> implements Map<K,V> {}

抽象类AbstractMap实现了Map

抽象方法

public abstract Set<Entry<K,V>> entrySet();

整个抽象类唯一的一个抽象方法，获取Map集合。又由子类实现逻辑。

属性

DEFAULT_INITIAL_CAPACITY

默认初始化容量，必须是2的幂。final修饰，不可被子类修改。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

MAXIMUM_CAPACITY

static final int MAXIMUM_CAPACITY = 1 << 30;

最大容量，必须是2的幂，<= (1<<30)介于两者之间。

DEFAULT_LOAD_FACTOR

负载系数，初始化未指定时为0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

TREEIFY_THRESHOLD

从列表转化为树实现的阈值：当至少有这么多个节点有元素时，容器将转化为树。

至少为8，

static final int TREEIFY_THRESHOLD = 8;

UNTREEIFY_THRESHOLD

static final int UNTREEIFY_THRESHOLD = 6;

MIN_TREEIFY_CAPACITY

static final int MIN_TREEIFY_CAPACITY = 64;

函数

hash()

获取key的hash

• 当key为空时，返回0.
• key不为null，返回key.hashCode() ^（key.hashCode() >>>16)的异或值

>>>：逻辑右移

>>：算数右移

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

put()

put()只是调用putVal()来实现。主要的逻辑和处理在putVal()。

代码和注释

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);  //调用putVal()
}

putVal()

1. 根据key计hash值：(h=key.hashCode()) ^ (h >>> 16)

2. 判断是否调整容量，当table为空时调用resize()

3. 计算下标i（i = (n - 1) & hash），判断小标i处是否存在Node节点

   • 不存在：当前hash映射的下标的容器为空，则直接new一个对象放在当前容器
   • 存在：
     • 若当前节点的key和要put的key相等，把当前e=节点
     • 若当前容器转化成红黑树：调用putTreeVal()，若key存在则返回对应的对象，key不存在则新增节点返回null
     • 当前容器是链表：否则遍历当前桶链表，如果存在key，退出；不存在key，新增node<key,value>到链表末尾

4. 经过第2步操作后，判断e的值若不为空，更新e的value为value参数值，返回oldeValue。否则执行第五步

5. 修改标志++modCount，size加一。若size超过要需调整容量大小时，触发resize()函数，调整容量。

6. putVal()结束，返回null

代码和注释

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;    //容器列表
    Node<K,V> p;    //key映射的下标下的节点
    int n, i;   //调整后的容量n， i：映射的下标
    //判断是否调整容量
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //判断(n - 1) & hash下是否已有节点，存在冲突
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);   //不存在冲突的话直接存这个位置上
    else {
        Node<K,V> e;    //i下标处的头节点
        K k;   //头节点的key
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))   //判断已有元素和当前key是否相同
            e = p;  //是同一个的话，就相当于更新值
        else if (p instanceof TreeNode) //当前桶转化成红黑树树的话，就调用putTreeVal()
            //instanceof：Java中的二元运算符，左边是对象，右边是类；当对象是右边类或子类所创建对象时，返回true；否则，返回false。
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //遍历当前桶链表，添加当前key,value到末尾
            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
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))   //桶中存在元素
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) e.value = value;
            afterNodeAccess(e); //保留函数，方便子类继承实现
            return oldValue;
        }
    }
    ++modCount; //修改标记
    if (++size > threshold) //是否需要调整容量
        resize();
    afterNodeInsertion(evict);  //保留函数，方便子类继承实现
    return null;
}

putTreeVal()

当桶转换成红黑树时，会执行tree版本的putVal()即putTreeVal()。

get(Object key)

根据key获取V，如果根据getNode(key)获取Node，如果为null返回null。存在的话返回Node.value。

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

getNode(int hash, Object key)

根据hash和key获取Node。

1. 如果哈希表和桶不为空，则遍历桶。为空则返回null
2. 遍历桶：如果桶转换成红黑树，return getTreeNode(hash, key)的返回值；如果桶中是链表则遍历链表。找得到就返回，找不到返回null

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 {   //遍历链接
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}