Java集合框架（四）Map
Map
先看下map的类图:
我们主要学习HashMap,LinkedHashMap,Hashtable,WeakedHashMap和TreeMap。
1.map介绍
map在java中用来保存具有映射关系的数据，以键值对的形式保存，一个key对应一个value，key不可以重复。可以把map中的key部分看成一个set集合，无序不重复，把value部分看成是一个list集合，都可以通过索引来进行访问，只不过这里的索引不是数字下标而是map中的key。
2.map主要实现和基本用法
map和set的实现结构基本相同，从两者的类图中也可以看出来。事实上java中就是先有得map集合，再有得set集合，set集合是被当成一个value全都是null的map集合。
HashMap：(使用最多的实现类)
测试代码：
package com.ljw.ColleactionAndMap;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
/**
* Created by liujiawei on 2018/6/30.
*/
public class TestMap {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put(null,1);
hashMap.put(null,2);
hashMap.put("jack","jack");
hashMap.put("tom","tom");
hashMap.put("jak","jack");
hashMap.put(2,"2");
hashMap.put(1,"1");
System.out.println(hashMap);
System.out.println(hashMap.keySet()); //以集合形式获取map的所有key
System.out.println(hashMap.get(1));
System.out.println("是否保存'33'的key===" + hashMap.containsKey("33"));
System.out.println("是否保存'33'的value===" + hashMap.containsValue("33"));
System.out.println(hashMap.entrySet()); //以集合形式获取map中的entry
//迭代hashmap的4中常见方式
//1.通过迭代器迭代entryset
System.out.println("通过迭代器迭代entryset");
Iterator it = hashMap.entrySet().iterator();
while(it.hasNext()){
Map.Entry entry = (Map.Entry) it.next();
System.out.println(entry.getKey() + "====" + entry.getValue());
}
//2。for循环entryset 推荐
System.out.println("推荐使用for循环entryset");
for (Object o:hashMap.entrySet()) {
Map.Entry<Object,Object> entry = (Map.Entry<Object, Object>) o;
System.out.println(entry.getKey() + "====" + entry.getValue());
}
//3.遍历key获取values
System.out.println("遍历key获取values");
for (Object o:hashMap.keySet()) {
System.out.println(o + "===" + hashMap.get(o));
}
//4。遍历value
System.out.println("遍历value");
for (Object o:hashMap.values()) {
System.out.println(o);
}
}
}运行结果：
通过上面的结果可以看到，hashmap中支持插入null作为key，key是唯一的，插入重复的key时，后插入的value会代替之前的value。我们还注意到插入的顺序和我们输出的顺序不一致，这是因为HashMap在插入key时，会通过计算hashcode来自己确定存储位置，所以是无序的。HashMap还可以以集合的形式返回所有的key，通过HashMap的keySet()可以对map的对象进行迭代。通过get（Object key）方法，可以获取到对应的value。
LinkedHashMap：
测试代码：
package com.ljw.ColleactionAndMap;
import java.util.LinkedHashMap;
/**
* Created by liujiawei on 2018/7/2.
*/
public class TestLinkedHashMap {
public static void main(String[] args) {
LinkedHashMap linkedHashMap = new LinkedHashMap();
linkedHashMap.put(null,1);
linkedHashMap.put(null,2);
linkedHashMap.put("jack","jack");
linkedHashMap.put("tom","tom");
linkedHashMap.put("jak","jack");
linkedHashMap.put(2,"2");
linkedHashMap.put(1,"1");
System.out.println(linkedHashMap);
}
}
运行结果：
LinkedHashMap在HashMap的基础上，通过链表来维护插入的key的顺序，保证放入和取出的顺序是一致的。
因为需要维护插入的顺序，所以性能上没有HashMap好。
Hashtable：
Hashtable和HashMap的用法基本相同，区别在于Hashtable是线程安全的，不支持null作为key。
WeakedHashMap：
WeakedHashMap和HashMap的用法相同，区别的是WeakedHashMap中放的是弱引用（java引用相关参考）我们用代码看下是什么意思：
测试代码：
package com.ljw.ColleactionAndMap;
import java.util.WeakHashMap;
/**
* Created by liujiawei on 2018/7/2.
*/
public class TestWeakedHashMap {
public static void main(String[] args) {
WeakHashMap weakHashMap = new WeakHashMap();
weakHashMap.put(new String("jack"),"jack");
weakHashMap.put(new String("tom"),"tom");
weakHashMap.put(new String("pony"),"pony");
System.out.println(weakHashMap);
System.gc();
System.out.println(weakHashMap);
String tony = "tony";
weakHashMap.put(tony,tony);
System.gc();
System.out.println(weakHashMap);
}
}运行结果：
可以看到第一次放入的三个数据，在调用了System.gc()以后，全都被回收了，最后增加的数据保留了下面，这就是因为上面三个全都属于弱引用，最后那个则是强饮用。
*使用WeakedHashMap时，里面要注意全都是弱引用，否则就失去了使用它的意义。
TreeMap：
对照TreeSet, TreeSet内部通过红黑树来存储数据，要求插入的对象都实现compator接口，依次来保证内部元素处于有序状态。TreeMap也是通过红黑树实现了内部对象的排序。我们用代码看下：
package com.ljw.ColleactionAndMap;
import java.util.Comparator;
import java.util.TreeMap;
/**
* Created by liujiawei on 2018/7/2.
*/
public class TestTreeMap {
public static void main(String[] args) {
TreeMap treeMap = new TreeMap();
treeMap.put(1,1);
treeMap.put(2,1);
treeMap.put(3,1);
treeMap.put(4,1);
System.out.println(treeMap);
TreeMap treeMap1 = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
int a = (int) o1;
int b = (int) o2;
if(a < b)
return 1;
if(a == b)
return 0;
if(a > b)
return -1;
return 0;
}
});
treeMap1.put(1,1);
treeMap1.put(2,1);
treeMap1.put(3,1);
treeMap1.put(4,1);
System.out.println(treeMap1);
}
}运行结果：
和TreeSet一样，TreeMap中的对象需要实现Compator接口，否则无法进行排序，抛出异常。
在实例化时，通过内部类直接重写compare（）方法，可以实现定制排序的效果。
*除非需要map中的对象总是处于有序状态，此时选择TreeMap，其他时候就应该尽量使用其他集合，因为排序会额外消耗时间。
3.HashMap和Hashtable底层分析（jdk1.7）
HashMap：
我们从HashMap的源码中来分析下HashMap初始化/新增／扩容这三个过程。初始化：
先记住这三个参数，后面会介绍这三个用途。默认容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认加载因子：0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
扩容因子：
int threshold;HashMap的三个构造方法，其实调用的都是最后一个：
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
} this(initialCapacity, DEFAULT_LOAD_FACTOR);
}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;
threshold = initialCapacity;
init();
}
这里的init（）方法是留给HashMap的子类实现的，这里没有任何实际意义。
新增：
HashMap中的新增对象都是通过put（key,value）方法来实现，它是以什么形式存储数据的，null是怎么处理的，重复的key是怎么判断的，都在这个put（）方法中实现，我们一起看下这部分的源码：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
看下inflateTable（）这个方法，inflate是膨胀的意思，可以看出，这就是给table初始化的方法：
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
继续看下，put（）方法，可以看到HashMap之所以支持null作为key，就是它对null做了特殊处理，看下putForNullKey（）方法：
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
可以看到，当key是null，会去table第一个位置找对应的数据，如果有的话，新的value会替代原有的value放在第一个位置，同时返回老得value。可以for循环有个判断条件是e = e.next，我们继续往下看：
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
可以看到非null类型的key处理步骤其实和null差不多，都是计算key的hash值，找到对应的存储位置来进行操作，这里的e.next是用来查询链表中的下一个数据，这涉及到HashMap内部的存储，用一个图说明下HashMap的存储：
HashMap内部使用数组来存储数据，这个数组是一个链表数组，里面存放Entry对象，Entry有三个属性，hash，key，value，key和value就是我们放进map的数据，hash则是通过hash（object）方法计算出的hashcode，所以HashMap的存储过程是这样理解的：
我们put一个key，value进map，首先拿到这个key，通过hashcode找到对应位置的数据，这是一个链表，先比较链表中的第一个对象的value，看是否相同，是的话，替换value，返回老的value，不是则和链表的下一个数据进行比较。
扩容：
我们已经知道，put（key，value），最后其实执行的操作就是addEntry(hash,key,value)，我们对table进行的扩容也是在这个方法中进行的：void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
Hashtable：
Hashtable和Vector一样，也是从最初的jdk就存在的一个集合，命名甚至都没有遵守驼峰命名的规则，现在基本不再使用这个集合，但是从研究的角度还是有必要了解下的：
初始化：
看下Hashtable的有关构造函数：
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
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);
initHashSeedAsNeeded(initialCapacity);
}
新增：
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);
initHashSeedAsNeeded(initialCapacity);
}
可以看到，Hashtable在实例化的过程中就对table对象完成了初始化过程，默认容量为11，加载因子也是0.75f。
新增：
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 = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
后面的插入以及扩容操作基本大同小异。
4.map集合比较
HashMap,LinkedHashMap,TreeMap和Hashtable这四个的使用，可以参考以下：
（1） HashMap是为了快速查询而设计的，当需要使用map集合时，如果没有特殊需求，首选HashMap；（2）LinkedHashMap作为HashMap的子类，额外通过链表来对插入的数据做了管理，使得插入和取出的顺序相同，在迭代查询上有优势，插入删除操作还是HashMap更好；
（3）TreeMap使用红黑树，使得内部数据总是处于排序状态，但是这耗费了额外的性能，如果没有这个排序的需要，尽量不要使用TreeMap；
（4）需要线程安全，可以使用Hashtable.