java集合框架学习（Map篇）

什么是Map？

Map，其实Map相当于ArrayList或者更简单的数组的一种扩展、推广。在数组中我们可以利用下标即数字访问数组当中的不同元素，那么数字与对象之间形成了一种关联，那么如果将这个数字的概念扩展成为对象，那同样的我们可以将对象与对象之间关联起来。即Map，也称为映射表、关联数组、字典允许我们使用一个对象来查找某个对象。

Map的几种实现？

Map接口的具体实现有HashMap，TreeMap，LinkedHashMap，WeakHashMap、ConcurrentHashMap、IdentityHashMap等实现。

HashMap：Map基于散列表的实现（它取代了HashTable），插入和查询键值对的开销是固定的。可以通过构造器设置容量和负载因子，以调整容器的性能。
LinkedHashMap：类似于HashMap，但是迭代遍历时，取得“键值对”的顺序是其插入次序，或者是最近最少使用的次序，之比HashMap慢一点，而在迭代访问时更快，因为其内部是使用链表维护内部次序。（也叫链接映射表）
TreeMap：基于红黑树的实现，特点在于得到的结果，是经过排序的，TreeMap是唯一带有subMap()的Map,其可以返回一个子树。（也叫树映射表）
ConcurrentHashMap：一种线程安全的Map，其不涉及同步加锁。
WeakHashMap：协同垃圾回收器工作，删除无用的键和该键的引用。（也叫弱散列映射表）
IdentityHashMap：这个映射表中键的散列值不是通过hashCode计算的，而是通过System.identityHashCode方法计算的。这是Object.hashCode方法根据对象的内存地址来计算散列码时所使用的方式。而且在对两个对象进行比较时，identityHashMap类使用==，而不是equals。（也叫标识散列映射表）
EnumMap：它是一个键类型为枚举类型的映射表，它可以直接且高效的用一个值数组实现。在使用时，需要咋构造器中指定键的类型：
EnumMap<Weekday，Employee> personMap = new EnumMap<Weekday，Employee>(Weekday.class);(也叫做枚举映射表)

HashMap ？

Java中数据存储方式最底层的两种结构，一种是数组，另一种就是链表。

数组的特点：连续空间，寻址迅速，但是在删除或者添加元素的时候需要有较大幅度的移动，所以查询速度快，增删较慢。
链表的特点：由于空间不连续，寻址困难，增删元素只需修改指针，所以查询慢、增删快。
哈希表就是结合了数组和链表，具有较快的查询速度，和较快的增删速度。

HashMap的实现主要用到了哈希表的链地址法。即使用数组+链表的方式实现。

如图长度为16的数组中，每个元素存储的是一个链表的头结点。元素的key通过散列函数计算得到散列值，然后根据散列值对数组长度取模得到的。

比如上述哈希表中，12%16=12 , 28%16=12, 108%16=12, 140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

它的内部是用Entity数组来实现的，属性有key，value，next

Map中的方法？

A.PUT方法

1	map.put(key,value)

key通过散列后，得到散列值，在经过计算得出应该插入的”桶”的序号。

B.get()操作

1	value = map.get(key)

通过key在map中找到对应的value值，key-value也称之为键值对。

C.Map的遍历

Map的遍历大体分为三种：

遍历Map.entrySet() :它的每一个元素都是Map.Entry对象，这个对象中，放着的就是Map中的某一对key-value
遍历Map.keySet() :它是Map中key值得集合，可以通过遍历这个集合来读取Map中的元素
遍历Map.values() :它是Map中value的集合，可以通过这个集合直接遍历Map中的值，却不能读取key

package com.sort;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

/**
 * map集合和set集合一样是无序的
 * map集合遍历的几种常用方法
 * @author Owner
 *
 */
public class MapTest {

    public static void main(String[] args) {

        Map<String, String> map = new HashMap<String, String>();

        map.put("a", "zhangsan");
        map.put("b", "lisi");
        map.put("c", "wangwu");

        //System.out.println(map);

        /**
         * 方法一遍历map
         */
        Set<String> keySet = map.keySet();

        for(Iterator<String> iterator = keySet.iterator();iterator.hasNext();){
            String key = iterator.next();

            String value = map.get(key);

            System.out.println(key+"="+value);
        }

        System.out.println("**********************");

        /**
         * 方法二遍历map
         */
        for(String key : map.keySet()){
            System.out.println(key+"="+map.get(key));
        }

        System.out.println("**********************");

        /**
         * 方法三遍历map，推荐使用该方法遍历map集合，尤其是容量大时
         */
        for(Map.Entry<String, String> entry : map.entrySet()){
            System.out.println(entry.getKey()+"="+entry.getValue());
        }


        System.out.println("**********************");

        /**
         * 方法四遍历map
         */
        Set<Entry<String, String>> entrySet = map.entrySet();

        for(Iterator<Map.Entry<String, String>> iterator = entrySet.iterator();iterator.hasNext();){
            Map.Entry<String, String> entry = iterator.next();

            System.out.println(entry.getKey()+"="+entry.getValue());
        }


        System.out.println("**********************");
        /**
         * 方法五，这种方法遍历的是所有的值
         */
        for(String value : map.values()){
            System.out.println(value);
        }

    }
}

TreeMap？

TreeMap是基于红黑树的实现，也是记录了key-value的映射关系，该映射根据key的自然排序进行排序或者根据构造方法中传入的比较器进行排序，也就是说TreeMap是有序的key-value集合，TreeMap不允许key-value为空。

构造方法

public TreeMap() :空的构造方法，默认容量为0
public TreeMap(Comparator<? super K> comparator)：需要一个Comparator比较器作为参数，因为TreeMap是一个有序的key-value集合，所以可以自定义比较器进行设定元素的排序规则
public TreeMap(Map<? extends K, ? extends V> m)：将一个Map构建成一个TreeMap
public TreeMap(SortedMap<K, ? extends V> m)：将一个SortedMap构建成一个TreeMap