关于map:Map集合之底层解析

9次阅读

共计 4438 个字符，预计需要花费 12 分钟才能阅读完成。

数组 + 链表 + 红黑树
key 非反复
双列元素
key 和 value 能够为空
key 只能有一个 null
非平安

无参结构器

应用无参结构，第一次 put 时，会先去校验 table 表中的长度是否 >0，如果小于 0，则回去查看初始容量 threshold 是否大于 0，如果没有指定 threshold 初始容量，则会应用默认的初始容量 16 作为 table 表的长度，默认的加载因子为 0.75，只有当汇合 put 时，才会真正的将 table 表的长度进行扩容，且下次扩容是达到初始容量 * 加载因子 = 临界值时会再次触发扩容。

/**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

指定初始化容量和加载因子的结构器

应用初始化容量和加载因子的结构器初始容量不得小于 0
如果初始化容量的大小大于 1 << 30(1 的 30 次方)，会间接应用 1 的 30 次方作为初始容量的大小。
加载因子不可小于等于 0 或者不是一个 float 类型。

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity:" +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor:" +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

应用单参初始容量结构器

初始容量不可大于 1 的 30 次方，且不可小于 0
默认的加载因子为 0.75

public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

应用传入 map 汇合的结构器

public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        // 计算出容量与加载因子
        // 如果容量超过加载因子，则进行扩容。// 随后遍历 Map 顺次进行 put 操作
        putMapEntries(m, false);
    }

hashMap 默认初始化是 16 个长度，其中默认的加载因子是 0.75，当汇合中增加的元素长度达到一个 临界值 – 汇合内元素总数 * 0.75= 临界值，即 12，当增加完一个元素此时汇合内的长度 >12 时会进行一个扩容，扩容依照以后容量的两倍进行扩容，并且依据以后的加载因子计算出 临界值, 当下一次再次触发，则会进行雷同的操作。
当咱们在 table（即 hashmap 中的数组）表中，存储元素时，会先去依据 key，获取对应的 hash 值（非 hashcode 值），是依据按位算法 –(h = key.hashCode()) ^ (h >>> 16)–，拿到这个值后，会和表中的 长度 -1进行按位运算，失去一个索引值，如果表中对应的索引值的元素为为空，则间接将元素增加至数组中的索引，如果存在，则会比拟新元素 key 的 hash 值与曾经存在的元素 key 的 hash 值是否相等，并且两个元素的 key 是否相等，如果相等阐明元素反复，则会进行替换操作，如果不相等，则会先去判断，这个索引处的对象类型是不是一颗红黑树，如果是红黑树，则会依照红黑树的形式存储，如果是一条链表，则会顺次比拟链中元素是否相等，如果相等，间接退出，如果不相等，则会在链的最初面减少一个元素，如果创立完后该链的长度 >=8，则会判断表 table 长度是否是 64，如果不是 64，则会优先扩容 table，再往链尾增加新元素的 Node 节点，如果是 64，则会将该链造成红黑树结构。

对于 HashMap 汇合的外部类 EntitySet 解析

已知，Map 汇合是键值对存储，且经源码剖析，其实，每个 k - v 元素实质就是一个 Node 节点对象（HashMap 外部类 Node<K,V>）, 且这个 Node 对象实现了 Map 接口的 Entity 接口，其实当咱们初始化一个 Node 节点时，newNode(hash, key, value, null)，实际上 Map 接口的外部类 Entity<K,V> 保留了 Node 对象的援用，因为多态的关系，Node 对象即是 Node 类型，又能够向上转型 Entity<K,V>, 即 Entity<K,V> 又能够向下转型。

为了不便对 HashMap 汇合的遍历，即会把保留在 HashMap 中的 Node 节点的援用保留在 EntitySet 一份，该汇合寄存的元素类型是 Entity，而一个 Entity 对象就有 K -V,EntitySet<Entity<K,V>>，即：Set<Map.Entity<K,V>>,EntitySet 中，定义的类型是 Map.Entity, 然而实际上寄存的还是 HashMap$Node，这是因为 Node<K,V> implements Map.Entity<K,V>, 当把 HashMap$Node 对象寄存到 entitySet 中后不便了咱们的遍历和取值。

/**
 * 初始化或加倍表大小。如果为空，则调配
 * 合乎初始容量指标放弃在现场阈值。* 否则，因为咱们应用的是二次幂扩大，所以
 * 来自每个 bin 的元素必须放弃雷同的索引，或者挪动
 * 在新表中具备 2 次方偏移。*
 * @return 表格
 */
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)
             newThr = oldThr << 1; // double threshold
     }
     else if (oldThr > 0) // initial capacity was placed in threshold
         newCap = oldThr;
     else {               // zero initial threshold signifies using defaults
         newCap = DEFAULT_INITIAL_CAPACITY;
         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
     }
     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;
 }

1.HashMap 的 key 不能够反复，如果再次 put 一个已有的 key，会将汇合中的 key 对应的 value 替换成新 put 的 value
2.HashMap 不平安，因为类中没有同步机制。
3.HashMap 效率高，因为 HashMap 的底层是数组 + 单向链表 + 红黑树。
4.HashMap 的 key 和 value 都能够为空，然而 key 只能有一个空。
5.HashMap 的扩容的触发能够是汇合内元素的大于临界值，会进行 2 倍的扩容，单条链表的长度 >= 8 时且 table 不是 64 时会进行 2 倍的扩容
6.HashMap 进行 put 时会依据key 计算出来的 hash 值与以后 table 表的 长度 -1进行 按位与 计算出 table 中的索引
7. 如果 hash 值计算的索引处在 table 表中已存在，则会进行比照，如果 key 的 hash 值不一样或者 key 的 equals 不满足则会进行 红黑树 构造的转换或单向链表的追加。
8.HashMap 是无序的，因为底层是 hash 表的形式进行存储的，因而存储的程序和取出来的程序是不同的。
9.HashMap 应用无参或者指定容量和指定容量、加载因子的结构器，只会在 HashMap 类中记录 threshold 初始容量长度和 loadFactor 加载因子，只有等到 put 时，才会真正的将汇合的容量进行扩容。