【Java基础】集合总结（三）——Queue集合、Map集合

一、Queue集合

Queue用于模拟队列这种数据结构，队列的特点是“先进先出”（FIFO）。队列的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。

（一）PriorityQueue实现类

PriorityQueue保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行排序。因此当调用peek()方法或者poll()方法取出队列时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。

//定义一个PriorityQueue类型的队列，并依次加入6,-3,20
PriorityQueue pq = new PriorityQueue();
pq.offer(6);
pq.offer(-3);
pq.offer(20);

//访问队列中的第一个元素，输出最小的元素-3
System.out.println(a.poll());
           

PriorityQueue不允许插入null元素，它还需要对队列元素进行排序，有两种排序方式

• 自然排序：采用自然排序的PriorityQueue集合中的元素必须实现了Comparable接口，而且应该是同一个类的多个实例，否则可能导致ClassCastException异常。
• 定制排序：创建PriorityQueue队列时，传入一个Comparator对象，该对象负责队列中的所有元素进行排序。采用定制排序时不要求队列元素实现Comparable接口。

（二）Deque接口与ArrayDeque实现类

Deque代表一个双端队列，特点是允许从两端来操作队列的元素。Deque不仅可以当成双端队列使用，而且可以被当成栈来使用，因为该类里还包含了pop(出栈)、push(入栈)两个方法。

Deque接口提供了一个典型的实现类，ArrayDeque。它是一个基于数组实现的双端队列，其可以作为栈来使用，也可以作为队列来使用。

//作为栈使用，先进后出
public class ArrayDequeStack{
   public static void main(String[] args)
   {
      ArrayDeque stack=new ArrayDeque();
      //将三个元素push入“栈”
      stack.push("绿色");
      stack.push("红色");
      stack.push("黄色");
      System.out.println(stack);
      //访问第一个元素，但并不将其“pop”出栈。输出：黄色
      System.out.println(stack.peek());
      //pop出第一个元素，输出：黄色
      System.out.println(stack.pop());
   }
}


//作为队列使用，先进先出

public class ArrayDequeQueue{
   public static void main(String[] args)
   {
      ArrayDeque queue=new ArrayDeque();
      //将三个元素加入队列
      queue.offer("绿色");
      queue.offer("红色");
      queue.offer("黄色");
      System.out.println(queue);
      //访问队列头部的元素，但并不将其poll出队列。输出：绿色
      System.out.println(queue.peek());
      //poll出第一个元素，输出：绿色
      System.out.println(stack.poll());
   }
}
           

（三）LinkedList实现类

LinkedList不光实现了List接口，还实现了Queue接口。这意味着它既是一个List集合，可以根据索引来随机访问集合中的元素。也是一个Queue集合，可以被当成双端队列来使用。因此既可以当成栈来使用，也可以当成队列来使用。

public class LinkedListTest{
    public static void main(String[] args)
    {
        LinkedList books = new LinkedList();
        //将字符串元素加入队列的尾部
        books.offer("A书");
        //将一个字符串元素加入栈的顶部
        books.push("B书");
        //将字符串元素添加到队列的头部（相当于栈的顶部）
        books.offerFirst("C书");
        //访问并不删除栈顶的元素
        System.out.println(books.peekFirst());
        //访问并不删除队列的最后一个元素
        System.out.println(books.peekLast());
        //将栈顶的元素弹出“栈”
        System.out.println(books.pop());
        //访问并删除队列的最后一个元素
        System.out.println(books.poolLast());
    }
}
           

（四）各种线性表的性能分析

LinkedList与ArrayList、ArrayDeque的实现机制完全不同，ArrayList、ArrayDeque内部以数组的形式来保存集合中的元素，因此随机访问集合元素时有较好的性能；而LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色（只需改变指针所指的地址即可）。总体来说，ArrayList的性能比LinkedList的性能要好，因此大部分的时候都应该考虑使用ArrayList。需要指出的是，虽然Vector也是以数组的形式来存储集合元素的，但因为它实现了线程同步功能（而且实现机制也不好），所以各方面性能都比较差。

关于使用List集合有如下建议：

• 如果需要遍历List集合元素，对于ArrayList、Vector集合，应该使用随机访问方法（get）来遍历集合元素，这样性能更好；对于LinkedList集合，则应该采用迭代器（Iterator）来遍历集合元素。
• 如果需要经常执行插入、删除操作来改变包含大量数据的List集合的大小，可考虑使用LinkedList集合。使用ArrayList、Vector集合可能需要经常重新分配内部数组的大小，效果可能较差。
• 如果有多个线程需要同时访问List集合中的元素，开发者可考虑使用Collections将集合包装成线程安全的集合。

二、Map集合

Map用于保存具有映射关系的数据，是key-value类型的。key和value都可以是任何引用类型的数据。key和value之间存在单向一对一关系，即通过指定的key总能找到唯一的、确定的value。Map的key不允许重复。

（一）Map接口常用方法

Map map=new HashMap();
//放入3组数据
map.put("语文",35);
map.put("数学",97);
map.put("英语",43);
//多次放入的key-value对中value可以重复
map.put("语文"，95);
//放入重复的key时，新的value会覆盖原有的value
//如果新的value覆盖了原有的value，该方法返回被覆盖的value
system.out.println(map.put("英语"，86))； //输出43
//判断是否包含指定的key
map.containsKey("语文");
//判断是否包含指定的value
map.containsValue(97);
//对map集合进行遍历
for(Object key:map.keySet())
{
    System.out.println(key+"-->"+map.get(key));
}
//根据key来删除key-value对，返回被删除key所关联的value，如果该key不存在，则返回null
map.remove("语文");
           

（二）HashMap实现类

1、HashMap是Map 接口使用频率最高的实现类，是线程不安全的。

2、允许使用null键和null值，与HashSet一样，不保证映射的顺序。

3、所有的key构成的集合是Set：无序的、不可重复的。所以，key所在的类要重写：equals()和hashCode()。

     所有的value构成的集合是Collection：无序的、可以重复的。所以，value所在的类要重写： equals()。

4、一个key-value构成一个entry，所有的entry构成的集合是Set：无序的、不可重复的。

5、HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。

     HashMap 判断两个 value 相等的标准是：两个 value 通过 equals() 方法返回 true。

6、HashMap的存储结构：

• JDK7及以前版本：HashMap是数组+链表结构。
• JDK8版本发布以后：HashMap是数组+链表+红黑树实现。

（三）LinkedHashMap实现类

1、在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。

2、与LinkedHashSet类似， LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 key-Value 对的插入顺序一致。

3、LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能；但因为它以链表来维护内部顺序，所以在迭代访问Map里的全部元素时将有较好的性能。

4、LinkedHashMap的底层实现原理：

     LinkedHashMap底层使用的结构与HashMap相同，因为LinkedHashMap继承于HashMap。

     区别就在于：LinkedHashMap内部提供了Entry，替换HashMap中的Node。

（四）Hashtable实现类

1、Hashtable是个古老的 Map 实现类， JDK1.0就提供了。不同于HashMap，Hashtable是线程安全的。

2、Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。

3、与HashMap不同， Hashtable 不允许使用 null 作为 key 和 value。

4、与HashMap一样， Hashtable 也不能保证其中 Key-Value 对的顺序。

5、Hashtable判断两个key相等、两个value相等的标准， 与HashMap一致。

6、尽量少用Hashtable实现类，即使需要创建线程安全的Map实现类，也无需使用Hashtable实现类，可以通过Collections工具类把HashMap变成线程安全的。

（五）Properties读写属性文件

1、Properties 类是 Hashtable 的子类，该对象用于处理属性文件。

2、由于属性文件里的 key、 value 都是字符串类型，所以 Properties 里的 key和 value 都是字符串类型。

3、存取数据时，建议使用setProperty(String key,String value)方法设置属性值和getProperty(String key)方法获取指定属性名对应的属性值。

Properties pros = new Properties();
pros.setProperty("username","Lucy");
String user = pros.getProperty("username");
           

（六）TreeMap实现类

1、TreeMap底层使用红黑树结构存储数据，每个key-value对即作为一个红黑树的一个节点。

2、TreeMap存储 Key-Value 对（节点）时， 需要根据 key对节点进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。

3、TreeMap 的 Key 的排序：

• 自然排序： TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException异常。
• 定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不要求 Map 的 Key 实现Comparable 接口。

4、TreeMap判断两个key相等的标准是：两个key通过compareTo()方法或者compare()方法返回0。

（七） WeakHashMap实现类

WeakHashMap和HashMap的用法基本相似，不同之处在于，HashMap的key保留了对实际对象的强引用，这意味着，只要该HashMap对象不被销毁，该HashMap的所有key所引用的对象就不会被垃圾回收，HashMap也不会自动删除对应的key-value对。但WeakHashMap的key只保留了对实际对象的弱引用，这意味着如果WeakHashMap对象的key所引用的对象没有被其它强引用变量所引用，则这些key所引用的对象可能被垃圾回收，WeakHashMap也可能自动删除这些key所对应的key-value对。

（八）IdetityHashMap实现类

其实现机制和HashMap基本相似，但它在处理两个key相等时比较独特：在IdetityHashMap中，当且仅当两个key严格相等（key1==key2）时，IdentityHashMap才会认为两个key相等；对于普通的HashMap而言，只要key1和key2通过equals()方法比较返回true，且它们的hashCode值相等即可。

（九）EnumMap实现类

EnumMap是和枚举类一起使用的Map实现，EnumMap中的所有key都必须是单个枚举类的枚举值。创建EnumMap时必须显式或隐式指定它对应的枚举类。EnumMap内部以数组的形式保存，根据key的自然顺序（即枚举值在枚举类中的定义顺序）来维护key-value对的顺序，不允许使用null作为key值，但可以作为value值。

（十）各Map实现类的性能分析

由于Hashtable是一个古老的、线程安全的集合，因此HashMap通常比Hashtable要快。

TreeMap通常比HashMap、Hashtable要慢（尤其在插入、删除key-value对时更慢），因为TreeMap底层采用红黑树来管理key-value对。TreeMap中的key-value对总是处于有序状态，无须专门进行排序操作。

对于一般的使用场景，程序应该多考虑使用HashMap，因为HashMap正是为快速查询设计的。但如果程序需要一个总是排好序的Map时，则可以考虑使用TreeMap。

LinkedHashMap比HashMap慢一点，因为它需要维护链表来保持Map中key-value时的添加顺序。IdentityHashMap性能没有特别出色之处，因为它采用与HashMap基本相似的实现，只是塔使用==而不是equals()方法来判断元素相等。EnumMap的性能最好，但它只能使用同一个枚举类的枚举值作为key。