[JDK 소스 코드 학습] HashMap 소스 코드 분석

HashMap 은 일상적인 개발 에서 사용 빈도 가 상당히 잦 아 면접 에서 도 자주 물 어 본다.이 자바 에서 자주 사용 하 는 집합 류 중 하나 로 소스 코드 를 배 울 필요 가 있 습 니 다.
본 고 는 HashMap 의 데이터 구조, 구조 함 수 를 분석 하고 자주 사용 하 는 방법 put, get, 확장, 링크 와 빨 간 검 은 나무 가 서로 전환 할 것 이다.
정적 속성

/**
* 默认初始容量 - 必须是2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
* 最大容量。如果构造函数中指定的容量大于这个值，那么会使用该默认值作为最大容量
*/
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;

구조 함수

// 指定初始容量和负载因子的构造方法
public HashMap(int initialCapacity, float loadFactor) {
    // 如果指定的初始容量小于0，直接抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
            initialCapacity);
    // 如果指定的初始大于最大容量，则使用最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 如果指定的负载因子小于0，或者是非法数字，则直接抛出异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
            loadFactor);
    this.loadFactor = loadFactor;
    // 计算table大小，即扩容后的数组大小
    this.threshold = tableSizeFor(initialCapacity);
}

// 指定初始容量，负载因子采用默认
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 初始容量和负载因子全部采用默认
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 使用一个map去构造HashMap
public HashMap(Map extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

get 방법

// 其实调用的是getNode方法，如果指定节点为null，则直接返回null，否则返回该节点的value
public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    // first是要找的节点所在的数组位置上的第一个元素（数组每个位置放的是一个链表和红黑树）
    // (n - 1) & hash 就是计算这个key位于数组的哪个位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果指定位置上的第一个节点刚好是要找的key，则直接返回第一个节点
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 第一个节点不是要找的key，如果有next节点的话，则继续找
        if ((e = first.next) != null) {
            // jdk8中引入的红黑树，如果第一个节点的树节点
            if (first instanceof HashMap.TreeNode)
                // 采用树的查找算法，查找对应的key
                return ((TreeNode)first).getTreeNode(hash, key);
            // 否则的话，则是链表节点，采用的是循环遍历整个链表，直到找出指定的key
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

4. put 방법

// 存入元素，其实调用的是putVal方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


/**
 *
 * @param hash key的hash
 * @param key key
 * @param value 要存入的value
 * @param onlyIfAbsent 如果为true的话，则不改变已存在的值
 * @param evict 如果为false，则table处于创建模式。
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    boolean evict) {
    Node[] tab; Node p; int n, i;
    // 如果table为null，或者长度为0，则进行一次扩容（具体扩容步骤，后面再讲）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // i为这个key应该放在table的具体位置，如果位置上没有元素，则构造一个节点Node，并且放在这个位置上
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { // 否则，即是table这个位置已经有元素了
        Node e; K k;
        // p就是这个位置上的第一个节点
        // 如果要put进来的key，与第一个节点的key一样，那么将e指向第一个节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果第一个节点是树节点，则采用树的插入算法插入一个节点
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else { // 否则，为链表节点
            for (int binCount = 0; ; ++binCount) {
                // 如果该位置只有一个节点，即没有next
                // 注意，这里在for循环里面，且e=p.next,也就是说，e始终会指向最后一个节点
                // 下面会有一个p = e, 新构建的Node会在p.next位置
                // 也就是说，新节点会最终放在链表的最后
                if ((e = p.next) == null) {
                    // 构建一个新节点Node，并将p的next指向这个新节点
                    p.next = newNode(hash, key, value, null);
                    // 如果链表节点数超过的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;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 需要替换，或者旧值为null，则用新的value替换旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 后处理，HahsMap中是一个空方法
            afterNodeAccess(e);
            // 返回put的value
            return oldValue;
        }
    }

    // put的元素最终落在链表或者树上的，会走上面的return oldValue,就没有下面的处理的
    // put的元素最终落在table指定位置的第一个节点时，才有下面的处理

    // table的修改次数加1    
    ++modCount;
    // table（数组）的大小大于指定数值后，进行一次扩容
    // 前面说了，threshold就是通过容量和负载因子算出来的，下次扩容的大小
    if (++size > threshold)
        resize();
    // HashMap中是一个空方法
    afterNodeInsertion(evict);
    return null;
}

5. 확장 resize 방법

final Node[] resize() {
    // 用oldTab保存原来的数组table
    // 从这里就能看得出，HashMap底层就是一个数组，数组里的元素就是一个个Node，这个Node可能是TreeNode，也就可能是链表Node
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 原数组长度
    int oldThr = threshold; // 原扩容阈值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 数组长度已经超过最大长度了，直接将下次扩容阈值改成Integer.MAX_VALUE的，然后返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新数组长度扩大一倍，如果比最大长度小，并且旧数组长度大于默认数组初始长度，则将扩容阈值扩大一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 旧数组长度小于等于0且就扩容阈值大于0，则将新数组长度设为旧的扩容阈值
    // 其实初始化一个HashMap时，走的就是这个分支
    else if (oldThr > 0)
        newCap = oldThr;
    // 否则，新数组长度和扩容阈值都设置默认
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 新的扩容阈值=0，那么就根据数组容量和负载因子，再计算一次新扩容阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
            (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    
    // 上面计算好了扩容之后的table容量
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    // 下面的计算就是一大推复制操作，宗旨就是把旧table上的元素，全部copy到这个newTab上
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node 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)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node 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;
                    }
                }
            }
        }
    }
    // 最终返回扩容后的新table
    return newTab;
}

지금까지 HahsMap 의 소스 코드 를 모두 분석 하 였 습 니 다.
주제 외 에 안의 확장 작업 을 자세히 연구 하면 용량 과 부하 인자 가 새로운 배열 table 의 크기 를 계산 한 다음 에 배열 의 요 소 를 모두 새 배열 에 복사 하 는 것 이다.이 복사 과정 에서 하나의 스 레 드 가 이 HashMap 에 하나의 요 소 를 넣 었 다 면 이 요 소 는 어디 에 존재 하고 잃 어 버 릴 까요?사실 이것 이 바로 면접 에서 자주 묻 는 것 입 니 다. HashMap 은 스 레 드 가 안전 합 니까?