Java中的Map集合

一，map集合的特点 （1）map是一个双列集合，一个元素中包含两个值（key—Value）。 （2）map集合中的键与值存在映射关系，key（键）唯一，value（值）允许重复 （3）无序，无索引 二，map集合的常用方法 (1)put方法

  V put(K key, V value) （可以相同的key值，但是添加的value值会覆盖前面的，返回值是前一个，如果没有就返回null）

        Map map = new HashMap();
        map.put("blue",1);
        map.put("white",3);
        map.put("yellow",3);

(2)remove方法

     删除关联对象，指定key对象

        Map map = new HashMap();
        map.put("blue",1);
        map.put("white",2);
        map.put("yellow",3);
        //指定键值对进行删除
        map.remove("blue", 1);

(3)clear方法

   清空集合对象

        Map map = new HashMap();
        map.put("blue",1);
        map.put("white",2);
        map.put("yellow",3);

       //清除map中所有元素
        map.clear();

(4)获取

value get(key); 可以用于判断键是否存在的情况。当指定的键不存在的时候，返回的是null。

Map map = new HashMap();
        map.put("blue",1);
        map.put("white",2);
        map.put("yellow",3);
        //根据键，获取键映射的值
        map.get("blue");
        System.out.println(map.get("blue"));

(5)长度

 获取map集合中键值对的个数：

Map map = new HashMap();
        map.put("blue",1);
        map.put("white",2);
        map.put("yellow",3);
        
        int s =map.size();
        System.out.println(s);

(6)判断

boolean isEmpty() 长度为0返回true否则false

boolean containsKey(Object key) 判断集合中是否包含指定的key

boolean containsValue(Object value) 判断集合中是否包含指定的value

三，map集合的遍历方式

（1）使用keyset（）方法，通过Set的迭代器取出Set集合中的每一个元素（Iterator）就是Map集合中的所有的键，再通过get方法获取键对应的值。

        Map map = new HashMap();
        map.put("blue",1);
        map.put("white",2);
        map.put("yellow",3);
        for(String key : map.keySet()) {
            Integer value = map.get(key);
            System.out.println(key+"="+value);
        }

（2）使用Entry对象遍历

        Map.Entry,在Map接口中有一个内部接口Entry（内部类）

        作用：当集合一创建，就会在Map集合中创建一个Entry对象，用来记录键与值（键值对对                         象，键值的映射关系）、

        Map map = new HashMap();
        map.put("blue",1);
        map.put("white",2);
        map.put("yellow",3);

        for(Entry entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key+"="+value);
        }

四，map集合的常用实现类

1.HashMap （1）HashMap的特点  hashmap存取是无序的键和值位置都可以是null，但是键位置只能是一个null键位置是唯一的，底层的数据结构是控制键的hashmao按照key的hash值计算数组中储存下标的位置，计算方式：（n-1）*hashjdk1.8前数据结构是：链表+数组           jdk1.8之后是：数组+链表+红黑树阈值（边界值）>8并且数组长度大于64，才将链表转换成红黑树，变成红黑树的目的是提高搜索速度，高效查询HashMap线程不安全，多线程下扩容容易死循环，多线程下put可能会数据覆盖，put与get并发时，可能导致get为null （2）扩容方式  【初始容量】：当添加第一个元素时，hashmap默认的初始数组大小为16，通过位移运算1<<4得出，数组长度为2^n。 【加载因子】：用来描述hashmap集合中元素的填满程度，默认为0.75f。 【扩容方法】：resize（） 【扩容条件】：HashMap中的元素超过扩容阈值（当前数组容量x加载因子）时，数组扩容为原数组的两倍。或者加入新元素时，如果链表长度大于8，会将当前链表转为红黑树，再转为红黑树之前，会判断数组长度，如果数组长度小于64，会发生扩容，如果数组长度大于64，则正常转为红黑树。 （3）put过程

          当新添加一个KV键值对元素时，通过该元素的key的hash值，计算该元素在数组中应该保存的下标位置。如果该下标位置已经在其他的Node对象（产生哈希冲突），则采用链地址法处理，即将新元素封装成一个新的Node对象，插入到该下标位置的链表尾部（尾插法）。当链表的长度超过8并且数组长度大于64时，为了避免查找性能下降，该链表会转化成黑红树。

 

解决哈希冲突的常见方法：

1.链地址法：哈希表中的每个Node节点都有一个Next指针，构成一个单向链表，被分配到同一个下标位置上的多个Node节点（发生哈希冲突），可以通过存入同一个单向链表来解决。

2.开放地址法：一旦发生哈希冲突，就去寻找下一个空的散列地址，只要散列足够大，空的散列集合总能找到，并且记录存入。

3.建立公共溢出区，将哈希表分为基本表和溢出表，凡是和基础表发生哈希冲突的元素，都存入溢出表。

4.再哈希法：也叫双哈希法，有多个不同的哈希函数，当发生哈希冲突时，使用第二个，第三个........，等哈希函数计算地址，等哈希函数计算地址，直到无冲突，缺点就是增加了计算时间。

（4）HashMap中的Hash函数

         HashMAori通过新添加元素key的hashCode（）方法，计算一个hash值，然后通过这个hash值计算位置下表。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

2.LinkedHashMap        HashMap的子类，实现Mao接口，保存了元素的插入顺序，既使用了HashMap的数据结构，又借用了LinkedList的双向列表。LinkedHashMap就是把HashMap中的Node维护成了一个双向链表。

public class LinkedHashMap
    extends HashMap
    implements Map{
        transient LinkedHashMap.Entry head;

        transient LinkedHashMap.Entry tail;
        
        final boolean accessOrder;
    }

（1）LinkedHashMap的特点： key值唯一，不允许重复value值允许重复有序LinkedHashMap是HashMap的子类 （2）储存结构：数组+链表+红黑树（维护了一个Entry的双向链表，保证了插入顺序）

为了实现双向链表，LinkedHashMap中提供了entry：

    /**
     * LinkedHashMap中的node直接继承自HashMap中的Node。并且增加了双向的指针
     */
    static class Entry extends HashMap.Node {
        Entry before, after;
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }

 （3）LinkedHashMap有序

          在hashmap的基础上通过双向链表维护元素节点间的顺序。LinkedHashMap中entry类继承自hashmap中的Node类。entry就是LinkedHashMap中的基本节点组成，其实就是双向链表的节点。

public V get(Object key) {
        Node e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
 

   它的get方法实际上就是HashMap的get方法，再最后判断是多了一个afterNodeAccess方法，

这个accesOrder其实就是控制节点在linkedHashmap

如果是true， 基于访问顺序。如果是false，就按插入顺序排列。

如此，就实现了LinkedeHashMap的有序。

3.TreeMap

              TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航 *** 作的方法.TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序；

（1）TreeMap的特点： key值唯一，不允许重复Value值允许重复按照key自动排序AbsttactMap的子类 （2）储存结构：红黑树（树中的每个节点都是一个Entry内部类的对象） （3）TreeMap的构造函数

//默认构造函数，按照key的自然顺序排列
public TreeMap() {comparator = null;}

//传递Comparator具体实现，按照该实现规则进行排序
public TreeMap(Comparator comparator) {this.comparator = comparator;}

//传递一个map实体构建TreeMap,按照默认规则排序
public TreeMap(Map m) {
    comparator = null;
    putAll(m);
}

//传递一个map实体构建TreeMap,按照传递的map的排序规则进行排序
public TreeMap(SortedMap m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

（4）TreeMap的put方法

 

 put的源码：

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     *
     * @return the previous value associated with {@code key}, or
     *         {@code null} if there was no mapping for {@code key}.
     *         (A {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key}.)
     * @throws ClassCastException if the specified key cannot be compared
     *         with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *         and this map uses natural ordering, or its comparator
     *         does not permit null keys
     */
    public V put(K key, V value) {
        Entry t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry parent;
        // split comparator and comparable paths
        Comparator cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable k = (Comparable) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

4.HashTable

        散列表（也叫哈希表），是根据Key-Value的直接访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录（类似索引），以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

（1）HashTable的特点： key值唯一，不允许重复Value值允许重复Value不允许为空，如果为空，则抛出NUllPointException线程安全，使用了synchronized加锁，但是性能较差 （2）储存结构：数组+链表 （3）哈希表的查找原理：

            哈希表就是数组加链表的产物，它继承了数组的查找容易，也继承了链表的插入删除快捷的特点。使用哈希函数将被查找的键转化为数组的索引。在理想的状态下，不同的键会被转化成不同的索引值。但是那是理想状态，我们实践当中是不可能一直是理想状态的。当不同的键生成了相同的索引的时候，也就是我们所说的冲突，我们这个时候就要处理冲突。

（4）put过程：

 /**
     * Maps the specified key to the specified
     * value in this hashtable. Neither the key nor the
     * value can be null. 

     *
     * The value can be retrieved by calling the get method
     * with a key that is equal to the original key.
     *
     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or null if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               null
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
    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 = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry entry = (Entry)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

（5）HashMap和Hashtable的区别 线程安全：HashMap是线程非安全的，而HashTable是线程安全的（内部的方法基本都使用了synchronized修饰）。执行效率：HashMap比HashTable效率高一点。对Null key 和 Null value的支持：HashMap可以储存null的key和value，但null作为键只能有一个，作为值可以有多个，HashTable不允许有null键和null值，否则抛出NullPointException。数据结构：JDK1.8之后的的HashMap在解决哈希冲突时，当链表长度的=大于阈值（默认为8）并且数组长度大于64，链表转化为红黑树，以减少搜索时间。所以，HashMap底层采用数组+链表+红黑树，而HashTable没有这样的机制，仅采用数组+链表。扩容方式：如果不指定初始容量，Hashtable的默认初始大小为11，之后每次扩容，容量变为原来的2n+1.HashMap的默认初始容量为16，之后每次扩容，都变为原数组的2倍。指定容量：创建时如果给定了初始容量，Hashtable会按照指定容量创建，而HashMap会将其扩容为2倍。

5.ConcurrentHashMap

    ConcurrentHashMap是一个支持高并发更新与查询的哈希表(类似HashMap)。在保证安全的前提下，查询不需要锁定。与HashTable不同，该类不依赖于ConcurrentHashMap去保证线程 *** 作的安

全。

         在JDK1.8之后，采用数组+链表+红黑树 ，使用synchronized和CAS进行并发控制。Java 8 在链表长度超过阈值（8）并且数组长度大于64时，将链表转换为红黑树；synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍；