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    }
指定初始化容量和加载因子的结构器
  1. 应用初始化容量和加载因子的结构器初始容量不得小于0
  2. 如果初始化容量的大小大于 1 << 30(1的30次方)，会间接应用1的30次方作为初始容量的大小。
  3. 加载因子不可小于等于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. 初始容量不可大于1的30次方，且不可小于0
  2. 默认的加载因子为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);    }

扩容机制

  1. hashMap默认初始化是16个长度，其中默认的加载因子是0.75，当汇合中增加的元素长度达到一个临界值--汇合内元素总数 * 0.75=临界值，即12，当增加完一个元素此时汇合内的长度>12时会进行一个扩容，扩容依照以后容量的两倍进行扩容，并且依据以后的加载因子计算出临界值,当下一次再次触发，则会进行雷同的操作。
  2. 当咱们在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解析
  1. 已知，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>又能够向下转型。

  2. 为了不便对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中后 不便了咱们的遍历和取值。

    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