Java基础之集合（二）

目录

1.2 Map

1.2.1HashMap

1.2.2ConcurrentHashMap

 1.2.3 HashTable

1.2.4TreeMap

1.2.5LinkedHashMap

1.2 Map

Map提供了一个更通用的元素存储方法，用于存储元素对（Key-Value），每个键映射一个值。

1.2.1HashMap

HashMap基于键的HashCode值唯一标识一条数据，同时基于键的HashCode值进行数据的存取，因此可以快速地更新和查询数据，但每次遍历的顺序无法保证相同。HashMap的Key和Value允许为空。

底层由数组+链表+红黑树组成

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;
        this.threshold = tableSizeFor(initialCapacity);
    }
           

•  initialCapacity:当前数组的容量，默认为16，可以扩容，扩容后数组的大小为当前的2倍，值始终为

  

  。
• loadFactor：负载因子，默认为0.75.

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
           

 数组中每个Entry实例都是一个链表或红黑树，默认数组中的Entry实例为链表，当链表中元素个数超过8个，HashMap会将链表结构转换成红黑树结构以提高查询效率。

HashMap在查找数据时，首先根据哈希值快速定位到数组的具体下标，在定位到数组下标后，如果Entry实例为链表，对链表进行顺序遍历，时间复杂度为O（n），若Entry实例为红黑树，查找的复杂度为O（logN），效率得到了大大的提升。

HashMap非线程安全，若需要满足线程安全，可以使用sychronizedMap（）使HashMap具有线程安全的能力，或者使用ConcurrentHashMap代替HashMap。

1.2.2ConcurrentHashMap

在Java7中ConcurrentHashMap采用分段锁的实现并发操作，因此他是线程安全的。ConcurrentHashMap由多个Segment组成，每次加锁锁住的都是一个Segment，当保证了每个Segment都是线程安全的就保证了全局都是线程安全的。ConcurrentHashMap默认由16个Segment组成，在这种情况下，最多支持16个线程执行写操作。

 在Java8中，CurrentHashMap弃用了Segment分段锁，改用了Synchronized+CAS实现对多线程的安全操作，数据结构同HashMap一致

 1.2.3 HashTable

HashTable很多功能与HashMap类似，不同的是，它是线程安全的，与ConcurrentHashMap不同的是，他同一时刻只能拥有一个线程写HashTable，并发性远远不如ConcurrentHashMap。他的一些方法都被Synchronized修饰。

1.2.4TreeMap

TreeMap是基于二叉树数据结构存储数据

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
}
           

public TreeMap() {
        comparator = null;
    }

    /**
     * Constructs a new, empty tree map, ordered according to the given
     * comparator.  All keys inserted into the map must be <em>mutually
     * comparable</em> by the given comparator: {@code comparator.compare(k1,
     * k2)} must not throw a {@code ClassCastException} for any keys
     * {@code k1} and {@code k2} in the map.  If the user attempts to put
     * a key into the map that violates this constraint, the {@code put(Object
     * key, Object value)} call will throw a
     * {@code ClassCastException}.
     *
     * @param comparator the comparator that will be used to order this map.
     *        If {@code null}, the {@linkplain Comparable natural
     *        ordering} of the keys will be used.
     */
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    /**
     * Constructs a new tree map containing the same mappings as the given
     * map, ordered according to the <em>natural ordering</em> of its keys.
     * All keys inserted into the new map must implement the {@link
     * Comparable} interface.  Furthermore, all such keys must be
     * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
     * a {@code ClassCastException} for any keys {@code k1} and
     * {@code k2} in the map.  This method runs in n*log(n) time.
     *
     * @param  m the map whose mappings are to be placed in this map
     * @throws ClassCastException if the keys in m are not {@link Comparable},
     *         or are not mutually comparable
     * @throws NullPointerException if the specified map is null
     */
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

    /**
     * Constructs a new tree map containing the same mappings and
     * using the same ordering as the specified sorted map.  This
     * method runs in linear time.
     *
     * @param  m the sorted map whose mappings are to be placed in this map,
     *         and whose comparator is to be used to sort this map
     * @throws NullPointerException if the specified map is null
     */
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
           

同时TreeMap实现了SortedMap接口，保障了元素的顺序存储。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}

public interface NavigableMap<K,V> extends SortedMap<K,V>{}
           

所以TreeMap常用于实现排序的映射列表，当我们使用TreeMap是，Key必须实现Comparable接口或采用自定义的比较器，否则将会抛出ClassCastException。

1.2.5LinkedHashMap

LinkedHashMap为HashMap的子类，其内部采用链表保存元素的插入顺序，当通过Iterator遍历时，采用元素的插入顺序访问元素。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>{}