JAVA集合框架之MAP

Map简介：

Map接口实现的是一组Key-Value的键值对的组合。 Map中的每个成员方法由一个关键字（key）和一个值（value）构成。它包装的是一组成对的“键-值”对象的集合，而且在Map接口的集合中也不能有重复的key出现，因为每个键只能与一个成员元素相对应。Map有两种比较常用的实现：HashMap和TreeMap等。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

HashMap介绍：
HashMap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。

如上图所示，HashMap就是一个散列表，由数组跟链表构成。

插入一个数据，先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则通过比较是否存在相同的key，若存在则覆盖原来key的value，否则将该元素保存在链头（最先保存的元素放在链尾）。若table在该处没有元素，则直接保存。取值就显得比较简单了。通过key的hash值找到在table数组中的索引处的Entry，然后返回该key对应的value即可。

JDK 1.8对HashMap进行了比较大的优化，底层实现由之前的“数组+链表”改为“数组+链表+红黑树”，使用一个Node数组来存储数据，但这个Node可能是链表结构，也可能是红黑树结构如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用treeifyBin函数，将链表转换为红黑树。那么即使hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O(log n)的开销也就是说put/get的操作的时间复杂度最差只有O(log n)

HashMap的四种遍历方式：

package collection;
import java.util.Collection;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
 
public class MapTest {
    public static void main(String[] args) {
        Map m = new HashMap<>();
        m.put("hello", 11);
        m.put("world", 11);
        m.put("nihao", 21);
        m.put("shijie", 22);
         
        //输出map中的所有value
        Collection values = m.values(); 
        for(int value: values) {
            System.out.println(value);
        }
          
        //map遍历1，通过keySet获得map中所有可以的集合，在通过key得到value
                //这种方式会遍历两次，一次是对key值得iterator，再一次是通过key获得值
        System.out.println("--------map遍历1------------");
        Set keySet = m.keySet();
        Iterator it = keySet.iterator();
        while(it.hasNext()) {
            String key = it.next();
            System.out.print("[key=" + key + ",value=" + m.get(key) + "]  ");
        }
         
        //map遍历2，foreach方法来遍历keyset，和第一种没有什么区别
        System.out.println("--------map遍历2------------");
        for(Object key: keySet) {
            System.out.print("[key=" + key + ",value=" + m.get(key) + "]  ");
        }
         
        //map遍历3，Map内部的Entry封装所有map的key-value对放入集合中，集       //合中的一个元素就包括了key和value，这样就之遍历一次就能得到集合，并可以访问所
//有key-value。
        System.out.println("--------map遍历3------------");
        Set entrySet = m.entrySet();
        Iterator it1 = entrySet.iterator();
        while(it1.hasNext()) {
            @SuppressWarnings("unchecked")
            Map.Entry e = (Map.Entry)it1.next();
            System.out.print("[key=" + e.getKey() + ",value=" + e.getValue() + "]  ");
        }
         
        System.out.println();
        System.out.println("--------map遍历4------------");
        //map遍历4，java8中新增方法。
        m.forEach((key,value) -> {
            System.out.print("[key=" + key + ",value=" + value + "]  ");
        });
         
        //关于hashMap的遍历，推荐使用3，4两种方法。    
    }
}

第一种和第二种性能上来说差别不大，都是取到所有元素，然后再遍历的，主要的差别是foreach中不能使用remove方法，而Iterator中可以使用，之后会详细说一下。

第三种方法性能会高一些，第一种跟第二种方法先取keySet，其实已经先遍历一次取到所有的key跟value，后面取value还多了一步get方法。

第四种方法使用了java8的新特性写法，简洁明了，forEach方法是JAVA8中在集合父接口Map中新增的一个default实现方法:

1)forEach方法接受一个在JAVA8中新增的java.util.function.Consumer的消费行为 或者称之为动作 (Consumer action )类型；

2)然后将集合中的每个元素作为消费行为的accept方法的参数执行；

3)直到每个元素都处理完毕或者抛出异常即终止行为；

4)除非指定了消费行为action 的实现，否则默认情况下是按迭代里面的元素顺序依次处理。

 * @param action The action to be performed for each entry
     * @throws NullPointerException if the specified action is null
     * @throws ConcurrentModificationException if an entry is found to be
     * removed during iteration
     * @since 1.8
     */
    default void forEach(BiConsumer action) {
        Objects.requireNonNull(action);
        for (Map.Entry entry : entrySet()) {
            K k;
            V v;
            try {
                k = entry.getKey();
                v = entry.getValue();
            } catch(IllegalStateException ise) {
                // this usually means the entry is no longer in the map.
                throw new ConcurrentModificationException(ise);
            }
            action.accept(k, v);
        }
    }

HashMap遍历删除元素：

以上几种遍历方法中，只有Iterator遍历方法支持remove，其他方法使用remove删除时可能会抛异常。

HashMap<String, String> map = new HashMap<>();
map.put("1","1");
map.put("2","2");
map.put("3","3");
map.put("3","3");
for (Map.Entry<String, String> item : map.entrySet()) {
    map.remove(item.getKey());
}

查看抛出异常的代码位置

final Node nextNode() {
    Node[] t;
    Node e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    if ((next = (current = e).next) == null && (t = table) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
}

modCount用于记录HashMap的修改次数,在HashMap的put(),get(),remove(),Iterator()等方法中,都使用了该属性,由于HashMap不是线程安全的,所以在迭代的时候,会将modCount赋值到迭代器的expectedModCount属性中,然后进行迭代,如果在迭代的过程中HashMap被其他线程修改了,modCount的数值就会发生变化,这个时候expectedModCount和ModCount不相等,
迭代器就会抛出ConcurrentModificationException()异常,这样可以避免共享资源而引发的潜在问题。

所以除了使用Iterator的remove方法删除外，还可以使用ConcurrentHashMap替换HashMap，ConcurrentHashMap会自己检查修改操作，对其加锁，避免因多线程操作引发的问题。

几种常用的map比较：

HashMap的存入顺序和输出顺序无关。而LinkedHashMap 则保留了键值对的存入顺序。TreeMap则是对Map中的元素进行排序。在实际的使用中我们也经常这样做：使用HashMap或者LinkedHashMap 来存放元素，当所有的元素都存放完成后，如果使用则是需要一个经过排序的Map的话，我们再使用TreeMap来重构原来的Map对象。这样做的好处是：因为HashMap和LinkedHashMap 存储数据的速度比直接使用TreeMap 要快，存取效率要高。当完成了所有的元素的存放后，我们再对整个的Map中的元素进行排序。这样可以提高整个程序的运行的效率，缩短执行时间。

这里需要注意的是，TreeMap中是根据键（Key）进行排序的。而如果我们要使用TreeMap来进行正常的排序的话，Key 中存放的对象必须实现Comparable 接口。

HashMap和Hashtable之间有两个主要区别。第一，HashMap是非同步的（为了快速访问），第二，HashMap允许使用null关键字和null值，而Hashtable是不允许的。

TreeMap实现了Map接口，并把元素存储在树中。TreeMap在操作上需要比HashMap更多一些的开销，但是由于树的结构使然，它返回排序的关键字。如果没有按照关键字顺序提取Map的元素的需求，那么HashMap是更实用的结构。LinkedHashMap也是一个HashMap,但是内部维持了一个双向链表,可以保持顺序。