HashMap源码

get操作

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

final HashMap.Node<K, V> getNode(int hash, Object key) {
    HashMap.Node[] tab;
    HashMap.Node first;
    int n;
    // 这里，先把tab指向了整个类的table，也就是先获取目前存储的所有元素
    // 同时判断是否为空，长度是否大于0，并初始化first的值，n - 1 & hash是为了保证hash值有效
    if ((tab = this.table) != null && (n = tab.length) > 0 && (first = tab[n - 1 & hash]) != null) {
        Object k;
        // 这里是为了判断是否存在hash冲突，如果hash值相等，并且key也相当，则直接返回
        if (first.hash == hash && ((k = first.key) == key || key != null && key.equals(k))) {
            return first;
        }

        HashMap.Node e;
        // 这里是判断冲突后，是否还存在下一个元素
        if ((e = first.next) != null) {
            // 判断此时的结构是否为红黑树，如果是，则遍历红黑树找节点
            if (first instanceof HashMap.TreeNode) {
                return ((HashMap.TreeNode)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;
}

getTreeNode

final HashMap.TreeNode<K, V> getTreeNode(int h, Object k) {
    return (this.parent != null ? this.root() : this).find(h, k, (Class)null);
}

final HashMap.TreeNode<K, V> find(int h, Object k, Class<?> kc) {
    // 首先获取到该节点的整个红黑树
    HashMap.TreeNode p = this;
	
    do {
        HashMap.TreeNode<K, V> pl = p.left;
        HashMap.TreeNode<K, V> pr = p.right;
        int ph;
        // 首先，是因为发生hash冲突后，才会用这个红黑树来解决hash冲突，那么该树中节点的hash值不是应该全部相等吗？
        // 应该是没有看生成代码的原因，转变为红黑树后，应该要做一次reHash，那么他们就会有新的hash值来用于构建红黑树
        // 这里，就是获取到左子树和右子树的hash值，然后与传入的值进行比较，一直找到相等的
        if ((ph = p.hash) > h) {
            p = pl;
        } else if (ph < h) {
            p = pr;
        } else {
            // 这里是找到了Hash值相等的
            Object pk;
            // 先判断key值是否相等，如果相等则返回
            if ((pk = p.key) == k || k != null && k.equals(pk)) {
                return p;
            }

            // 这里是仍然有冲突，那么就看该节点的左右子树
            if (pl == null) {
                p = pr;
            } else if (pr == null) {
                p = pl;
            } else {
                // 这里是左右子树都不为空
                int dir;
                // 这里由于没有传入比较器，所以不会走if，只会走else
                if ((kc != null || (kc = HashMap.comparableClassFor(k)) != null) && (dir = HashMap.compareComparables(kc, k, pk)) != 0) {
                    p = dir < 0 ? pl : pr;
                } else {
                    // 这里是左右子树都不为空，则递归的进行搜索即可
                    HashMap.TreeNode q;
                    if ((q = pr.find(h, k, kc)) != null) {
                        return q;
                    }

                    p = pl;
                }
            }
        }
    } while(p != null);

    return null;
}