HashMap解析

发表于 | 更新于

重要的参数

  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ，默认的初始容量
  2. static final int MAXIMUM_CAPACITY = 1 << 30 ，最大容量
  3. static final float DEFAULT_LOAD_FACTOR = 0.75f 默认的装载因子
  4. static final int TREEIFY_THRESHOLD = 8 在链长度达到这个长度时转换为树结构
  5. static final int UNTREEIFY_THRESHOLD = 6 当长度达到这个长度，会从树转换成链
  6. static final int MIN_TREEIFY_CAPACITY = 64; 想要转换成树的话，table的最小容量

field

  1. Node<K,V>[] table;
  2. Set<Map.Entry<K,V>> entrySet;
  3. int size;
  4. int modCount; 记录table的修改次数，保证iterators可以快速失败，see ConcurrentModificationException
  5. int threshold 下次扩容的size
  6. float loadFactor; 装载因子

内部类

  1. Node 基础的node元素

    1
    2
    3
    4
    5
    6
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    }

  2. KeySet

    1
    final class KeySet extends AbstractSet<K> {}

  3. Values

    1
    final class Values extends AbstractCollection<V> {}

  4. EntrySet

    1
    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {}

  5. HashIterator

    1
    2
    3
    4
    5
    6
    abstract class HashIterator{
            Node<K,V> next;        // next entry to return
            Node<K,V> current;     // current entry
            int expectedModCount;  // for fast-fail
            int index;             // current slot
    }

  6. KeyIterator

    1
    2
    final class KeyIterator extends HashIterator
            implements Iterator<K>

  7. ValueIterator

    1
    2
    final class ValueIterator extends HashIterator
            implements Iterator<V>

  8. EntryIterator

    1
    2
    final class EntryIterator extends HashIterator
            implements Iterator<Map.Entry<K,V>>

  9. KeySpliterator

  10. ValueSpliterator

  11. EntrySpliterator

  12. TreeNode

主要行为

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {

        //n为length, p为 要放入的位置的指针
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; //如果长度为0 则初始化
        if ((p = tab[i = (n - 1) & hash]) == null) //取位置的方式时(len-1) & hash 因为len是2的幂次，所以与运算结果一定小于len
            tab[i] = newNode(hash, key, value, null);
        else { //else 发现位置上已经有Node  
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; //如果完全一致
            else if (p instanceof TreeNode) //如果p 是TreeNode 
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { //如果p就是正常的Node ,则进行链式的放置
                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)))) //遍历中如果找到equals的Node
                        break;
                    p = e;
                }
            }
            //此时 e 指向的对象已经是有正确值的Node
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)  //判断能否直接替代
                    e.value = value;
                afterNodeAccess(e); //后续操作
                return oldValue; 
            }
        }
        ++modCount;  //这段不是很理解，按理来说在链上增加Node也属于改变Mapping数量，但这段代码看起来只会在直接在table上放值时才会走到
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

未完。。。