#yyds干货盘点#Map集合之底层解析-摩杜云开发者社区

HashMap(jdk8)

特点

数组+链表+红黑树
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，则会将该链形成红黑树结构。

EntitySet

关于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,但是实际上存放的还是 HashMapNode 对象存放到entitySet中后方便了我们的遍历和取值。

HashMap扩容源码

/**
 * 初始化或加倍表大小。如果为空，则分配
 * 符合初始容量目标保持在现场阈值。
 * 否则，因为我们使用的是二次幂扩展，所以
 * 来自每个 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时，才会真正的将集合的容量进行扩容。

HashTable

特点

安全
效率低
key和value都不允许为空
当key存在时，会进行value替换
数组+链表

解析

Hashtable默认初始容量是11个长度，且Hashtable初始化容量是在put前完成的。
Hashtable默认的加载因子是0.75，且临界值为 threshold=(int)Math.min(initialCapacity loadFactor, MAX_ARRAY_SIZE + 1),也就是说加载因子最大为MAX_ARRAY_SIZE + 1,但是默认的还是initialCapacity loadFactor，初始容量*加载因子。
如果进行put操作，添加元素之前会先去判断 count >= threshold（当前集合的大小是否大于或等于临界值）,如果大于临界值，则会按照int newCapacity = (oldCapacity << 1) + 1 （oldCapacity = table.length;），进行扩容，也就是说每次扩容都为`当前的容量 2 +1,临界值依然按照threshold = (int)Math.min(newCapacity loadFactor, MAX_ARRAY_SIZE + 1)的方式进行扩容;
Hashtable每次扩容完毕，都会进行重新hash的操作，在扩容前会先将当前集合所有的Node数组拿到，再将table表指向一个新的空的数组，数组大小为扩容后的容量，扩容后，将所有的Node数组中的对象Node进行key的重新hash。
进行put操作时如果当前容量 >=临界值则会按照当前容量2倍+1的方式进行扩容，扩容前会将当前table表备份一份，扩容完毕后，会进行一个重新hash的操作，执行完毕后会重新hash新元素的key的索引值，随后再将元素放入到新的table表中。

Hashtable构造器

Hashtable所有构造都基于下面这个构造器进行初始化。

public Hashtable(int initialCapacity, float loadFactor) {
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     if (loadFactor <= 0 || Float.isNaN(loadFactor))
         throw new IllegalArgumentException("Illegal Load: "+loadFactor);

     if (initialCapacity==0)
         initialCapacity = 1;
     this.loadFactor = loadFactor;
     table = new Entry<?,?>[initialCapacity];
     threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
 }

put方法源码

public synchronized V put(K key, V value) {
     // Make sure the value is not null
     if (value == null) {
         throw new NullPointerException();
     }

     // Makes sure the key is not already in the hashtable.
     Entry<?,?> tab[] = table;
     int hash = key.hashCode();
     int index = (hash & 0x7FFFFFFF) % tab.length;
     @SuppressWarnings("unchecked")
     Entry<K,V> entry = (Entry<K,V>)tab[index];
     for(; entry != null ; entry = entry.next) {
         if ((entry.hash == hash) && entry.key.equals(key)) {
             V old = entry.value;
             entry.value = value;
             return old;
         }
     }

     addEntry(hash, key, value, index);
     return null;
 }

addEntry方法

private void addEntry(int hash, K key, V value, int index) {
     modCount++;

     Entry<?,?> tab[] = table;
     if (count >= threshold) {
         // Rehash the table if the threshold is exceeded
         rehash();

         tab = table;
         hash = key.hashCode();
         index = (hash & 0x7FFFFFFF) % tab.length;
     }

     // Creates the new entry.
     @SuppressWarnings("unchecked")
     Entry<K,V> e = (Entry<K,V>) tab[index];
     tab[index] = new Entry<>(hash, key, value, e);
     count++;
 }

重新hash方法

protected void rehash() {
     int oldCapacity = table.length;
     Entry<?,?>[] oldMap = table;

     // overflow-conscious code
     int newCapacity = (oldCapacity << 1) + 1;
     if (newCapacity - MAX_ARRAY_SIZE > 0) {
         if (oldCapacity == MAX_ARRAY_SIZE)
             // Keep running with MAX_ARRAY_SIZE buckets
             return;
         newCapacity = MAX_ARRAY_SIZE;
     }
     Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

     modCount++;
     threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
     table = newMap;

     for (int i = oldCapacity ; i-- > 0 ;) {
         for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
             Entry<K,V> e = old;
             old = old.next;

             int index = (e.hash & 0x7FFFFFFF) % newCapacity;
             e.next = (Entry<K,V>)newMap[index];
             newMap[index] = e;
         }
     }
 }