草料场

浏览: 169330 次
性别:
来自: 杭州

最近访客更多访客>>

ufostop

努力吧飞翔

longfei136

ufopw

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

【Java源码解读】HashMap

博客分类：

Java

源码来源：OpenJDK 10

简述

HashMap实现了Map接口

与Hashtable不同处在于：

HashMap允许null为key，允许null为value，而Hashtable则不支持

Hashtable线程安全，HashMap未同步化，所以线程不安全

关于性能

当所使用的Hash函数能使得所有元素均匀地分布到各哈希桶时，get和put这类基础操作的耗时可接近常量（O(1)）。
遍历HashMap的耗时与内部哈希桶的数量和键值对的数量有关。这些内部对象越多，遍历耗时越久。所以对遍历性能要求较高时，不应把HashMap的初始容量设置得过高，负载因子也不宜过低
HashMap的性能主要受初始容量（intial capacity）和负载因子（load factor）影响。

容量指的是内部哈希桶的数量，初始容量就是HashMap刚创建时哈希桶的数量。
负载因子是指内部键值对的数量和容量的最大比例。当键值对数量要超过这个最大比例时会触发容量增长操作，HashMap将被重新hash，重新调整内部数据结构，哈希桶的数量将翻倍（大约）

默认（推荐）的负载因子是0.75。这是一个平衡耗时与内存占用较好的点。负载因子越高，内存占用越少，但是（平均）查找耗时越长。如果初始容量（initial capacity）比键值对的最大数量与负载因子商大，那么该HashMap永远不会重新hash。因此，选择合适的容量和负载因子可减少重新hash的次数，从而提高HashMap的性能。

默认初始容量是16，默认负载因子是0.75；
添加前12个键值对不会扩容（16 * 0.75 = 12）；
添加第13个键值对时会执行扩容操作，容量翻倍变为32，下次扩容的阀值也翻倍变为24

另外，如果有较多key的哈希值（hashCode()）相同，HashMap的性能也会下降（哈希冲突）。为了改善哈希冲突的情况，当key实现了Comparable接口时，HashMap会利用此方法对key进行排序以改善哈希冲突情况下的性能。
通常，HashMap会用哈希桶存放键值对；每个键值对是一个节点；当键值对多到哈希桶过大时，会用TreeNode（红黑树）替代原哈希桶。TreeNode结构可以在键值对数量较大时提供更好的查找性能。但如果大部分哈希桶中键值对数量不多，即大部分哈希桶都不是TreeNode，那么部分方法的性能可能会因检查哈希桶是否为TreeNode而下降。
Tree类型哈希桶中的元素主要按哈希值排序。如果存哈希碰撞，也会尝试用Comparable接口提供的compareTo方法对这些键值对进行排序（在key实现了Comparable接口的前提下）。
因为TreeNode所占用的内存大约是常规节点的两倍，所以只有在哈希桶中的键值对数量超过特定的限值时才会转换为TreeNode。且当键值对数量回到足够小时，又会将TreeNode转为常规节点。合适的哈希算法可以减低使用TreeNode概率。

关于线程安全

与ArrayList类似，HashMap也是线程不安全的。如果有多个线程访问HashMap实例，且至少有一个线程会改变map的内部结构，那么必须在外部对这些操作进行同步处理。

添加或删除键值对会改变map内部结构；仅改变已有键值对中的值不会改变内部结构。

一般可以对拥有map实例的某个外部对象进行同步化访问改造，或用Collections.synchronizedMap方法将该map包装为一个同步化的线程安全的map
HashMap的视图操作也是fail-fast机制的。对于它抛出的ConcurrentModificationException异常也是仅用于辅助排障，而不能作为正常业务逻辑的依赖。

关键字段

DEFAULT_INITIAL_CAPACITY

默认的初始容量。值为16。该值必须是2的幂

MAXIMUM_CAPACITY

最大容量。值为1<<30，即1073741824。该值必须是2的幂

DEFAULT_LOAD_FACTOR

默认负载因子。值为0.75

TREEIFY_THRESHOLD

哈希桶中节点数量必须达到这个值才会将哈希桶树化（与 MIN_TREEIFY_CAPACITY 结合使用）。值为8

树化：将节点转换为TreeNode，以树结构存储键值对，替代原链式结构。

为什么要树化？哈希桶内元素的树化可以提高存取性能。如果桶内元素非常多，且是以链表的形式存储的，那么很容易被攻击至服务器CPU资源不足。

客户端可以利用哈希冲突的数据与服务端交互，导致服务端对链式数据集存取时消耗大量的CPU资源，进而进入拒绝服务的状态。

UNTREEIFY_THRESHOLD

哈希桶中节点数量少于该值时才会将哈希桶非树化，即，将TreeNode转换为常规节点。值为6

MIN_TREEIFY_CAPACITY

HashMap的容量必须达到该值才会将哈希桶树化（与 TREEIFY_THRESHOLD 结合使用）；否则如果哈希桶中节点过多，会触发内部数组扩容操作。值为64。

该值必须大于等于 4* TREEIFY_THRESHOLD，以避免扩容与树化的冲突

构造方法

HashMap(int initialCapacity, float loadFactor)

创建一个空map，并指定初始容量和负载因子

初始容量（initialCapacity）会被用于计算真正的初始容量值(tableSizeFor(int cap)。这个值只是暂存于内部字段threshold，直到首次添加键值对时才会创建用到该值，并创建内部数组

HashMap(int initialCapacity)

创建一个空map，并指定初始容量

该方法会使用默认负载因子。

内部实现就是调用HashMap(initialCapacity, DEFAULT_LOAD_FACTOR)

HashMap()

创建一个空map

负载因子初始化为默认值（0.75）；其它字段不动，都是默认值

HashMap(Map<? extends K, ? extends V> m)

创建一个map，并将指定map中的键值对都添加到该新map中

负载因子取默认值（0.75）

添加指定map中的节点时会调用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)；其中onlyIfAbsent为false，evict为false

关键方法

hash(Object key)

计算key的哈希值

为了减少哈希冲突，将key的自带hashCode实现值与其右移16位后的值进行异或运算。

注：计算节点在内部数组中的索引时，key哈希值的高位部分很少会用到，所以与右移16位后的值进行异或

index = (n - 1) & hash

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

tableSizeFor(int cap)

计算满足目标容量的容量值（map的容量必须是2的幂）

该方法就是为了找到大于等于cap的最小的2的幂

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

先将n赋值为目标容量（cap）减1，可防止cap本就是2的幂时，后续操作无法得到期望值。中间的一系列无符号右移和“或”操作可以得到（二进制）右侧各位连续为1的数（00...011...1）。这个数再加1就能得到满足条件的最小的2的幂。

另，如果cap是负数，最终得到的n也是负数，所以（需）返回1；

如果n大于等于最大容量限制（1<<30），则返回最大容量限制值

resize()

调整内部数组的大小

将原数组中的节点转移到新数组时，

如果节点next为空，则直接将其放入新数组

该节点在新数组中的索引为节点hash和新数组和最大索引的“与”操作结果

newTab[e.hash & (newCap - 1)] = e

否则，如果该节点是TreeNode，则尝试将其分割（split）

((TreeNode<K,V>)e).split(this, newTab, j, oldCap)

TreeNode<K,V>.split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)

否则，通过节点的next引用遍历找到目标节点的loHead、loTail、hiHead与hiTail

如果loTail不为空，则将其next引用置为空；hiTail也如此

将loHead放到新数组中，索引为该入口节点在原数组中的索引

将hiHead放到新数组中，索引为该入口节点在原数组中的索引和原数组容量的和

以此达到目标效果：扩容后，每个节点要么存放在相同索引的哈希桶中，要么新哈希桶索引与原哈希桶索引的偏移量为2的幂

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) {
        // 原容量已达到最大容量值，不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 翻倍后的容量小于最大容量限值，且原容量大于等于默认初始容量（16）
            // 下一次扩容临界点也翻倍
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        // 原容量为0，说明需要初始化，新容量就是原threshold保存的值
        newCap = oldThr;
    else { // zero initial threshold signifies using defaults
        // 原容量为0，需要初始化，但threshold保存的值小于等于0，所以使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 可能因为前面的步骤中相关条件不满足，导致newThr未被赋值。所以需要处理newThr
    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"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    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;
                    }
                }
            }
        }
    }

    return newTab;
}

putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

添加一个键值对。如果已存在key相等的键值对，最后会返回原value；否则会返回null

hash就是键的哈希值

onlyIfAbsent表示是否只有当map未包含目标key时才添加该键值对；也就是说，当该值为true时，不会用新值去替换原值

evict为false时说明内部数组出于创建过程中

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)
        // 如果内部数组为空，先调用resize()方法进行初始化
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果目标索引处没有节点，则创建（常规）节点将键值对存放到该位置
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            // 如果目标索引处原节点与新节点的哈希值相同且key相等，则认为键值对已存在
        else if (p instanceof TreeNode)
            // 如果原节点时TreeNode，则将新节点加入到该树形哈希桶中
            // 与该方法类似，如果目标树形哈希桶中已存在等价的key，putTreeVal会返回相应的节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 目标索引处已有节点，且其key与新节点key不相等，且该节点是常规节点，
            // 则将新节点添加到该链表末尾
            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
                        // 如果链表中节点数量达到了树化的临界值，则将这些哈希值（hash）相同的节点树化
                        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相等的节点已存在，且原值为null或onlyIfAbsent为false，则用新值替换原值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        // 如果添加新节点后，节点数量超过了扩容线，则进行扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

treeifyBin(Node<K,V>[] tab, int hash)

将key的哈希值为指定值的节点进行树化

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果内部数组还未初始化或其容量小于树化的临界值，则扩容内部数组
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 将原节点都转换为TreeNode，并前后连在一起
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 整理这些新的TreeNode成为符合要求的树
            hd.treeify(tab);
    }
}

getNode(int hash, Object key)

获取指定key对应的节点

hash是key所对应哈希值。将hash作为参数之一往下传递，可减少重复计算hash的消耗

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) {
        // 如果对应索引处存在节点（根节点），则在此哈希桶中查找目标节点
        // 先检查首节点。如果key相等，则直接返回首节点
        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)
                // 如果首节点是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);
        }
    }

    // 内部数组为空，或目标索引处无节点，则直接返回null
    return null;
}

removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

删除键值对（节点）

hash就是key对应的哈希值

value与matchValue结合使用；当matchValue为true时，只有当value与现有键值对中的value相等才会删除键值对

movable为true且目标节点是TreeNode时会调用TreeNode<K,V>.moveRootToFront方法确保其树的根节点是其哈希桶中的第一个元素

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    // 先找到对应的节点（与getNode相同），再将其移除
    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)))) {
                        node = e;
                        break;
                    }
                    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，则按照树节点的方式删除
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 如果是常规节点，且前一个节点p就是目标节点，说明首节点就是目标节点，则直接将下一个节点放到首节点的位置
                tab[index] = node.next;
            else
                // 否则将前一个节点与后一个节点直连，从而移除目标节点
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }

    // 如果内部数组为空，或不存在对应的哈希桶，则直接返回null
    return null;
}

TreeNode<K,V>.putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)

添加一个TreeNode键值对

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    // 从根节点开始遍历，找到插入新节点的位置
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            // 新节点哈希值比当前节点小（应添加到其左边）
            dir = -1;
        else if (ph < h)
            // 新节点哈希值比当前节点大（应添加到其右边）
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // 两节点key相等，直接返回当前节点（由其调用方决定是否替换原值）
            return p;
        else if ((kc == null &&
            (kc = comparableClassFor(k)) == null) ||
                (dir = compareComparables(kc, k, pk)) == 0) {
            // 两节点key不相等，但哈希值相同且无法比较或比较值为0
            if (!searched) {
                // 还未搜索当前节点的左右支树，需要继续搜索
                TreeNode<K,V> q, ch;
                searched = true;
                // 如果在左右支树中找到了等价的节点（key及其哈希值都相等），则返回找到的节点（由其调用方决定是否替换原值）
                if (((ch = p.left) != null &&
                    (q = ch.find(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                            (q = ch.find(h, k, kc)) != null))
                    return q;
            }

            // 如果已搜索过左右支树且未找到等价节点，则由方法tieBreakOrder的返回值决定新节点需添加到当前节点左支树还是右支树
            dir = tieBreakOrder(k, pk);
        }
        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 如果当前节点某一支为null，且这支方向就是新节点的插入位置，则直接将新节点插入该位置
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 重新平衡该树形哈希桶，并将其根节点作为该哈希桶的第一个元素
            moveRootToFront(tab, balanceInsertion(root, x));
            // 完成新节点添加，无“已存在的key”，返回null
            return null;
        }
    }
}

TreeNode<K,V>.split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)

将树形哈希桶中的节点分为底层和高层树形哈希桶；如果节点数量太少，则将树形哈希桶转换为常规节点哈希桶

先通过节点的next引用遍历找到目标节点的loHead、loTail、hiHead与hiTail

如果loHead不为null，且low节点个数小于等于非树化临界值（UNTREEIFY_THRESHOLD）,

则将loHead非树化，即从TreeNode转换为常规节点，并将所得节点放到新数组中，

索引为入口节点在原数组中的索引

TreeNode. untreeify(HashMap<K,V> map)

否则，直接将loHead放入新数组，索引为入口节点在原数组中的索引。

如果hiHead不为null，说明loHead还未树化，则将loHead树化

TreeNode. treeify(Node<K,V>[] tab)

如果hiHead不为空，且high节点个数小于等于非树化临界值（UNTREEIFY_THRESHOLD），

则将hiHead非树化，即从TreeNode转换为常规节点，并将所得节点放到新数组中，

索引为入口节点在原数组中的索引与原数组容量的和

否则，直接将hiHead放入新数组，索引为入口节点在原数组中的索引与原数组容量的和

如果loHead不为null，说明hiHead还未树化，则将hiHead树化

TreeNode<K,V>.treeify(Node<K,V>[] tab)

将与当前TreeNode相连的节点进行树化处理

参数tab是节点的目标存放数组，在确保根节点是该树形哈希桶的第一个节点时会用到

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            // 根节点为null，将x作为（临时）根节点
            // x的parent引用置为null，x被标记为黑色（非红）
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            // 已经有（临时）根节点，将x插入到树中
            // 根据节点的哈希值来决定新节点的插入位置
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            // 从根节点开始遍历，找到插入新节点的位置
            for (TreeNode<K,V> p = root;;) {
                // 先确定新节点应添加到当前节点左还是右
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    // 新节点的哈希值比当前节点的小（应添加到其左边）
                    dir = -1;
                else if (ph < h)
                // 新节点的哈希值比当前节点大（应添加到其右边）
                    dir = 1;
                else if ((kc == null &&
                    (kc = comparableClassFor(k)) == null) ||
                        (dir = compareComparables(kc, k, pk)) == 0)
                    // 两节点的哈希值相等，且节点的key未实现Comparable接口或两节点的key比对结果相等
                    dir = tieBreakOrder(k, pk);

                // 如果两个key不相等，即比对结果不为0，则新节点插入位置（dir）就是该比对结果
                // 尝试插入新节点
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 如果当前节点某一支为null，且这支方向就是新节点的插入位置，则直接将新节点插入该位置
                    // 将当前节点定为新节点的parent
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;

                    // 新节点的插入后，需要对树进行再平衡
                    root = balanceInsertion(root, x);

                    break;
                }
            }
        }
    }
    // 确保该树形哈希桶的根节点是该哈希桶的第一个节点
    moveRootToFront(tab, root);
}

TreeNode<K.V>.tieBreakOrder(Object a, Object b)

当两个节点key的哈希值相同且key的比对结果相等或无法比对（未实现Comparable接口），用此方法决定节点先后顺序

此方法只是为了在上述情况下有一个统一的节点插入规则

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
            -1 : 1);

    return d;
}

TreeNode<K,V>.moveRootToFront (Node<K,V>[] tab, TreeNode<K,V> root)

确保根节点是其所在树形哈希桶的第一个元素

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        // index就是根节点应存放的位置
        int index = (n - 1) & root.hash;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        if (root != first) {
            // 目标索引处的节点不是根节点
            // 先将根节点放入目标索引位置
            Node<K,V> rn;
            tab[index] = root;

            // 再将根节点的前后节点直接相连
            TreeNode<K,V> rp = root.prev;
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;

            // 然后将目标索引处的原节点作为根节点的后继节点
            if (first != null)
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        assert checkInvariants(root);
    }
}

TreeNode<K,V>.untreeify(HashMap<K,V> map)

将当前TreeNode及其它与之相邻的节点进行非树化处理

参数map是节点所属的map，在将树形节点转换为普通节点时会用到

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 将目标节点转换为常规节点
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }

    return hd;
}

removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable)

移除当前树节点，也就是该实例方法对应的实例

如果movable为true，则移除目标节点后会调用TreeNode<K,V>.moveRootToFront方法确保其树的根节点是其哈希桶中的第一个元素

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
    int n;
    if (tab == null || (n = tab.length) == 0)
        // 内部数组为空时直接返回
        return;

    int index = (n - 1) & hash;
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;

    // 将前一个节点与后一个节点直接连接
    if (pred == null)
        // 前一个节点为null，说明当前节点是该哈希桶的首节点，则直接用后一个节点替代首节点
        tab[index] = first = succ;
    else
        // 否则将前一个节点和后一个节点直接相连
        pred.next = succ;

    if (succ != null)
        succ.prev = pred;

    // 如果后一个节点是null（此时first的值是next，且哈希桶中只剩一个节点），可以直接返回
    if (first == null)
        return;

    if (root.parent != null)
        root = root.root();
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        // 树节点较少，将其非树化
        tab[index] = first.untreeify(map);  // too small
        return;
    }

    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        // 找到比当前节点大的最小节点
        while ((sl = s.left) != null) // find successor
            s = sl;

        // 交换该最小节点与当前节点的颜色（非红即黑）
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors

        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }

            if ((s.right = pr) != null)
                pr.parent = s;
        }

        p.left = null;
        if ((p.right = sr) != null)
            sr.parent = p;

        if ((s.left = pl) != null)
            pl.parent = s;

        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;

        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    else if (pl != null)
        replacement = pl;
    else if (pr != null)
        replacement = pr;
    else
        replacement = p;

    if (replacement != p) {
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;

        p.left = p.right = p.parent = null;

    }

    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); 

    if (replacement == p) {  // detach
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }

    if (movable)
        moveRootToFront(tab, r);
}

其它方法

size()

获取键值对数量

isEmpty()

判断map是否为空

内部就是判断size是否等于0

get(Object key)

获取指定key对应键值对的值

如果没有对应键值对，将返回null。因为HashMap允许value为null，所以该方法返回值为null并不意味着不存在相应键值对

内部实现就是调用了getNode(int hash, Object key)获取对应的节点，再返回其value

containsKey(Object key)

判断是否存在指定key对应的键值对

内部实现就是调用getNode(int hash, Object key)，判断返回值是否为null

put(K key, V value)

添加一个键值对。如果已经存在key相等的键值对，原value将被替换为新value，并返回原value；否则返回null

putVal(hash(key), key, value, false, true)

putAll(Map<? extends K, ? extends V> m)

添加指定map中所有键值对

如果已存在key相等的键值对，原value将被替换为新value

类似构造方法HashMap(Map<? extends K, ? extends V> m)中的添加方式

remove(Object key)

移除指定key对应的键值对，并返回value。如果不存在对应的键值对，将返回null

内部会调用removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

matchValue: false; value: null; movable: true

clear()

移除所有键值对

具体实现就是把size置为0，内部数组的各索引处引用置为null

containsValue(Object value)

判断是否存在value与指定value相等的键值对

具体实现就是遍历内部数组中的每个哈希桶，逐个检查value是否相等

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (Node<K,V> e : tab) {
            for (; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
                }
            }
        }
        
    return false;
}

keySet()

获取key的Set视图

对该视图的修改会影响到map。如，KeySet.remove(Object key)方法内部会调用map的removeNode方法

values()

获取value的Collection视图

对该视图的修改会影响到map。如，Values.clear()方法内部会调用map的clear方法

entrySet()

获取键值对的Set视图

对该视图的修改会影响到map。如，EntrySet.clear()方法内部会调用map的clear方法

getOrDefault(Object key, V defaultValue)

获取指定key对应的value；如果不存在对应的键值对，则返回指定的默认值

内部实现就是调用getNode(int hash, Object key)获取键值对节点，再返回其value

putIfAbsent(K key, V value)

如果不存在指定key的键值对，则添加指定的键值对

内部实现就是调用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)，其中onlyIfAbsent为true

remove(Object key, Object value)

删除与指定key和value都相等的键值对

内部实现就是调用removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)，其中matchValue为true

replace(K key, V oldValue, V newValue)

将与指定key和value都相等的键值对的value替换为指定的新value

内部实现就是先调用getNode方法找到key相等的键值对，再判断其value与oldValue相等的情况下，将原value替换为newValue

forEach(BiConsumer<? super K, ? super V> action)

遍历每个键值对，执行action.accept(key, value)

replaceAll(BiFunction<? super K, ? super V, ? extends V> function)

遍历每个键值对，将原value替换为function.apply(key, value)的返回值

较为复杂的方法

computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

如果存在指定key的键值对，且value不为null，

则返回原value

否则执行mappingFunction.apply(key)得到新value；

如果存在原键值对，则用新value替换原value，并返回新value

否则添加新键值对，并返回新value

computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)

如果存在指定key的键值对，且value不为null，

则执行remappingFunction.apply(key, oldValue)得到新value，用其替换原value，并返回新value

否则，直接返回null

compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)

执行remappingFunction.apply(key, oldValue)获得新value

如果不存在指定key对应的键值对，则oldValue为null

如果新value不为null，则添加新键值对

否则

如果新value不为null，则用新value替换原value

否则移除键值对节点

最终返回新value

merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)

如果已存在key对应的键值对，

如果原value不为null，则执行remappingFunction.apply(oldValue, value)获得新value

否则指定的value即为新value

如果新value不为null，则将原value替换为新value

否则删除该键值对

最后返回新value

否则，如果指定的value不为null，则添加新键值对

最后返回指定的value

分享到：

【Java源码解读】Hashtable | 【Java源码解读】Collections.synchronized ...

2018-08-20 14:49
浏览 527
评论(0)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客 更多访客>>