Map介绍

简介

Map

Map 是一组成对的“键值对”对象，允许使用键 (key) 来查找值 (value)。它提供了一个映射表，可以通过某个对象来查找另一个对象。它也被称作 关联数组，因为它将某些对象与另外一些对象关联在一起；或者称作 字典，通过键对象来查找值对象，就像在字典中使用单词来定义一样。

void clear() 
          从此映射中移除所有映射关系（可选操作）。 
 boolean containsKey(Object key) 
          如果此映射包含指定键的映射关系，则返回 true。 
 boolean containsValue(Object value) 
          如果此映射将一个或多个键映射到指定值，则返回 true。 
 Set<Map.Entry<K,V>> entrySet() 
          返回此映射中包含的映射关系的 Set 视图。 
 boolean equals(Object o) 
          比较指定的对象与此映射是否相等。 
 V get(Object key) 
          返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。 
 int hashCode() 
          返回此映射的哈希码值。 
 boolean isEmpty() 
          如果此映射未包含键-值映射关系，则返回 true。 
 Set<K> keySet() 
          返回此映射中包含的键的 Set 视图。 
 V put(K key, V value) 
          将指定的值与此映射中的指定键关联（可选操作）。 
 void putAll(Map<? extends K,? extends V> m) 
          从指定映射中将所有映射关系复制到此映射中（可选操作）。 
 V remove(Object key) 
          如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。 
 int size() 
          返回此映射中的键-值映射关系数。 
 Collection<V> values() 
          返回此映射中包含的值的 Collection 视图。

HashMap

HashMap是基于哈希表的Map实现的的，一个Key对应一个Value，允许使用null键和null值，不保证映射的顺序，特别是它不保证该顺序恒久不变，也不是同步的。HashMap存放元素是通过哈希算法将其中的元素散列的存放在各个“桶”之间。通常情况下HashMap在jdk1.7之前是数组 + 链表和jdk1.8是数组 + 链表 + 红黑树( 链表长度超过8就使用红黑树 )。

• 线程不安全
• 元素无序
• 允许key和value为null
• 数据结构主要是桶(数组，默认长度是16，resize扩容2n)，链表或红黑树

HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。HashMap的容量不足的时候，可以自动扩容resize()，但是最大容量为MAXIMUM_CAPACITY==2^30。

resize非常耗时的操作，因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。

时间复杂度：HashMap的时间复杂度取决于hash算法，优秀的hash算法可以让时间复杂度趋于常数O(1)，糟糕的hash算法可以让时间复杂度趋于O(N)。

LinkHashMap

• 线程不安全
• LinkedHashMap是有序的，默认为插入顺序
• LinkedHashMap是数组+双向链表+红黑树的数据结构

Hashtable

• 线程安全
• 元素无序
• 不可以存入null键和null值
• 默认的初始大小为11，之后每次扩容，容量变为原来的2n+1，数组加链表的方式存储数据

TreeMap

• 线程不安全
• 基于红黑树实现
• key不允许为null，value允许为null
• 元素是有序的迭代的时候TreeMap默认是按照Key值升序排序的；