1、Map 概述

1. Map与Collection并列存在。用于保存具有映射关系的数据：key-value
2. Map 中的key 和value 都可以是任何引用类型的数据
3. Map 中的key 用Set来存放，不允许重复，即同一个Map 对象所对应的类，须重写hashCode()和equals()方法
4. 常用String类作为Map的“键”
5. key 和value 之间存在单向一对一关系，即通过指定的key 总能找到唯一的、确定的value
6. Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和Properties。
7. HashMap 是Map 接口使用频率最高的实现类

2、Map 常用方法

• 添加、删除、修改操作：

• Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
• void putAll(Map m):将m中的所有key-value对存放到当前map中
• Object remove(Object key)：移除指定key的key-value对，并返回value
• void clear()：清空当前map中的所有数据

• 元素查询的操作：

• Object get(Object key)：获取指定key对应的value
• boolean containsKey(Object key)：是否包含指定的key
• boolean containsValue(Object value)：是否包含指定的value
• int size()：返回map中key-value对的个数
• boolean isEmpty()：判断当前map是否为空
• boolean equals(Object obj)：判断当前map和参数对象obj是否相等

• 元视图操作的方法：

• Set keySet()：返回所有key构成的Set集合
• Collection values()：返回所有value构成的Collection集合
• Set entrySet()：返回所有key-value对构成的Set集合

3、Map的实现类之一：HashMap

3.1 HashMap的存储结构

JDK 7及以前版本：HashMap是 数组+链表 结构(即为链地址法)

JDK 8版本发布以后：HashMap是 数组+链表+红黑 树 实现。

JDK7：

JDK8：

3.2 HashMap概述

Map中的key： 无序的、不可重复的 ，使用Set存储所有的key。key所在的类要重写equals()和hashCode() （以HashMap为例）

Map中的value： 无序的、可重复的 ，使用Collection存储所有的value。value所在的类要重写equals()

一个键值对：key-value构成了一个Entry对象。

Map中的entry： 无序的、不可重复的 ，使用Set存储所有的entry

3.3 HashMap源码分析

JDK7

public class HashMap<K,V>
   extends AbstractMap<K,V>
   implements Map<K,V>, Cloneable, Serializable
{

   /**
    * The default initial capacity - MUST be a power of two.
    */
   static final int DEFAULT_INITIAL_CAPACITY = 16;

   /**
    * The maximum capacity, used if a higher value is implicitly specified
    * by either of the constructors with arguments.
    * MUST be a power of two <= 1<<30.
    */
   static final int MAXIMUM_CAPACITY = 1 << 30;

   /**
    * The load factor used when none specified in constructor.
    */
   static final float DEFAULT_LOAD_FACTOR = 0.75f;

   /**
    * The table, resized as necessary. Length MUST Always be a power of two.
    */
   transient Entry<K,V>[] table;


   /**
   * The number of key-value mappings contained in this map.
   */
   transient int size;

   /**
   * The next size value at which to resize (capacity * load factor).
   * @serial
   */
   int threshold;

   /**
   * The load factor for the hash table.
   *
   * @serial
   */
   final float loadFactor;


   /**
    * Constructs an empty <tt>HashMap</tt> with the specified initial
    * capacity and the default load factor (0.75).
    *
    * @param initialCapacity the initial capacity.
    * @throws IllegalArgumentException if the initial capacity is negative.
    */
   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

   /**
    * Constructs an empty <tt>HashMap</tt> with the default initial capacity
    * (16) and the default load factor (0.75).
    */
   public HashMap() {
       this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }

   /**
    * Constructs an empty <tt>HashMap</tt> with the specified initial
    * capacity and load factor.
    *
    * @param initialCapacity the initial capacity
    * @param loadFactor     the load factor
    * @throws IllegalArgumentException if the initial capacity is negative
    *         or the load factor is nonpositive
    */
   public HashMap(int initialCapacity, float loadFactor) {
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                                              initialCapacity);
       // initialCapacity：默认 16
       // MAXIMUM_CAPACITY: 1<<30
       // 一般此处都跳过                                      
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                                              loadFactor);

       // Find a power of 2 >= initialCapacity
       int capacity = 1;
       // 找一个 2的平方 > 初始化容量，就跳出
       // capacity : 16
       while (capacity < initialCapacity)
           capacity <<= 1;

       this.loadFactor = loadFactor;
       // 临界值：16 * 0.75=12
       threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
       // 创建数组
       table = new Entry[capacity];
       useAltHashing = sun.misc.VM.isBooted() &&
              (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
       init();
  }
}

JDK8

public class HashMap<K,V> extends AbstractMap<K,V>
   implements Map<K,V>, Cloneable, Serializable {

   /**
    * The default initial capacity - MUST be a power of two.
    */
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

   /**
    * The maximum capacity, used if a higher value is implicitly specified
    * by either of the constructors with arguments.
    * MUST be a power of two <= 1<<30.
    */
   static final int MAXIMUM_CAPACITY = 1 << 30;

   /**
    * The load factor used when none specified in constructor.
    */
   static final float DEFAULT_LOAD_FACTOR = 0.75f;

   /**
    * The bin count threshold for using a tree rather than list for a
    * bin. Bins are converted to trees when adding an element to a
    * bin with at least this many nodes. The value must be greater
    * than 2 and should be at least 8 to mesh with assumptions in
    * tree removal about conversion back to plain bins upon
    * shrinkage.
    */
   static final int TREEIFY_THRESHOLD = 8;

   /**
    * The bin count threshold for untreeifying a (split) bin during a
    * resize operation. Should be less than TREEIFY_THRESHOLD, and at
    * most 6 to mesh with shrinkage detection under removal.
    */
   static final int UNTREEIFY_THRESHOLD = 6;

   /**
    * The smallest table capacity for which bins may be treeified.
    * (Otherwise the table is resized if too many nodes in a bin.)
    * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
    * between resizing and treeification thresholds.
    */
   static final int MIN_TREEIFY_CAPACITY = 64;  


   /**
    * Basic hash bin node, used for most entries. (See below for
    * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
    */
   static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;
       final K key;
       V value;
       Node<K,V> next;

       Node(int hash, K key, V value, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
      }

       public final K getKey()       { return key; }
       public final V getValue()     { return value; }
       public final String toString() { return key + "=" + value; }

       public final int hashCode() {
           return Objects.hashCode(key) ^ Objects.hashCode(value);
      }

       public final V setValue(V newValue) {
           V oldValue = value;
           value = newValue;
           return oldValue;
      }

       public final boolean equals(Object o) {
           if (o == this)
               return true;
           if (o instanceof Map.Entry) {
               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
               if (Objects.equals(key, e.getKey()) &&
                   Objects.equals(value, e.getValue()))
                   return true;
          }
           return false;
      }
  }


   /**
    * Constructs an empty <tt>HashMap</tt> with the specified initial
    * capacity and load factor.
    *
    * @param initialCapacity the initial capacity
    * @param loadFactor     the load factor
    * @throws IllegalArgumentException if the initial capacity is negative
    *         or the load factor is nonpositive
    */
   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);
  }

   /**
    * Constructs an empty <tt>HashMap</tt> with the specified initial
    * capacity and the default load factor (0.75).
    *
    * @param initialCapacity the initial capacity.
    * @throws IllegalArgumentException if the initial capacity is negative.
    */
   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

   /**
    * 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
  }  



}    
public V put(K key, V value) {
   return putVal(hash(key), key, value, false, true);
}

/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)
       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;
       // hashcode相等，key也相等，就覆盖原来数据
       if (p.hash == hash &&
          ((k = p.key) == key || (key != null && key.equals(k))))
           e = p;
       else if (p instanceof TreeNode)
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       else {
           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
                       // 红黑树
                       treeifyBin(tab, hash);
                   break;
              }
               if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k))))
                   break;
               p = e;
          }
      }
       // 1. key是null
       // 2. hash值不等
       // 3. hash值相等，key不等
       if (e != null) { // existing mapping for key
           V oldValue = e.value;
           if (!onlyIfAbsent || oldValue == null)
               e.value = value;
           afterNodeAccess(e);
           return oldValue;
      }
  }
   ++modCount;
   if (++size > threshold)
       resize();
   afterNodeInsertion(evict);
   return null;
}

3.4 HashMap的底层实现原理

• jdk7说明：

1. HashMap map = new HashMap()
2. 在实例化以后，底层创建了长度是16的一维数组Entry[] table。
3. 首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。

1. 如果key1的哈希值与已经存在的数据的 哈希值都不相同 ，此时key1-value1添加成功。 情况2
2. 如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：
3. 如果 equals()返回false： 此时key1-value1添加成功。 情况3
4. 如果equals()返回true：使用value1替换value2。
5. 如果 此位置上的数据为空 ，此时的key1-value1添加成功。 情况1
6. 如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值：
7. 补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。

1. 在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

• jdk8 相较于jdk7在底层实现方面的不同：

1. new HashMap():底层没有创建一个长度为16的数组
2. jdk 8底层的数组是：Node[],而非Entry[]
3. 首次调用put()方法时，底层创建长度为16的数组
4. jdk7底层结构只有： 数组+链表 。jdk8中底层结构： 数组+链表+红黑树 。

1. 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
2. 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。

3.5 HashMap常用常量

1. DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，默认值：16
2. MAXIMUM_CAPACITY ：HashMap的最大支持容量，默认值：2^30
3. DEFAULT_LOAD_FACTOR ：HashMap的默认加载因子，默认值：0.75
4. TREEIFY_THRESHOLD ：Bucket中链表长度大于该默认值，转化为红黑树，默认值：8
5. UNTREEIFY_THRESHOLD ：Bucket中红黑树存储的Node小于该默认值，转化为链表，默认值：6
6. MIN_TREEIFY_CAPACITY ：桶中的Node被树化时最小的hash表容量。（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。），默认值：64
7. table ：存储元素的数组，总是2的n次幂
8. entrySet ：存储具体元素的集
9. size ：HashMap中存储的键值对的数量
10. modCount ：HashMap扩容和结构改变的次数。
11. threshold ：扩容的临界值=容量*填充因子
12. loadFactor ：填充因子

3.6 HashMap什么时候进行扩容和树形化呢？

当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时，就 会 进 行 数 组 扩 容 ，loadFactor的 默 认 值(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。

默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过160.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。 当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。

4、Map的实现类之二：HashMap的子类LinkedHashMap

1. LinkedHashMap是HashMap的子类
2. 在HashMap存储结构的基础上，使用了一对 双向链表 来记录 添加元素的顺序
3. 与LinkedHashSet类似，LinkedHashMap可以维护Map 的迭代顺序：迭代顺序与Key-Value 对的插入顺序一致

5、Map的实现类之三：TreeMap

1. TreeMap存储Key-Value 对时，需要根据key-value 对进行排序。
2. TreeMap可以保证所有的Key-Value 对处于 有序状态 。
3. TreeSet底层使用 红黑树结构 存储数据
4. TreeMap的Key 的排序：

1. 自然排序 ：TreeMap的所有的Key 必须实现Comparable 接口，而且所有的Key 应该是同一个类的对象，否则将会抛出ClasssCastException
2. 定制排序 ：创建TreeMap时，传入一个Comparator 对象，该对象负责对TreeMap中的所有key 进行排序。此时不需要Map 的Key 实现Comparable 接口

1. TreeMap判断两个key相等的标准： 两个key通过compareTo()方法或者compare()方法返回0 。

6、Map的实现类之四：Hashtable

1. Hashtable是个古老的Map 实现类，JDK1.0就提供了。
2. 不同于HashMap，Hashtable是 线程安全 的。
3. Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
4. 与HashMap不同，Hashtable 不允许 使用null 作为key 和value
5. 与HashMap一样，Hashtable也不能保证其中Key-Value 对的顺序
6. Hashtable判断两个key相等、两个value相等的标准，与HashMap一致

7、Map的实现类之五：Hashtable的子类Properties

1. Properties 类是Hashtable的子类，该对象用于处理属性文件
2. 由于属性文件里的key、value 都是字符串类型，所以Properties 里的key 和value 都是字符串类型
3. 存取数据时，建议使用setProperty(String key,Stringvalue)方法和getProperty(String key)方法