集合（Java总结一）

一、Queue

一个队列就是一个先入先出（FIFO）的数据结构

1、没有实现的阻塞接口的LinkedList：实现了java.util.Queue接口和java.util.AbstractQueue接口
　　内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue
　　PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。
　　PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。
　　ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，对公共集合的共享访问就可以工作得很好。

ConcurrentLinkedQueue

1）常用方法

　　*offer()：将指定的元素插入队列的尾部。
　　*poll() ：获取并移除队列的头，如果队列为空则返回null。
　　*peek()：获取表头元素但不移除队列的头，如果队列为空则返回null。
　　*remove(Object obj)：移除队列已存在的元素，返回true，如果元素不存在，返回false。
　　*add(E e)：将指定元素插入队列末尾，成功返回true，失败返回false（此方法非线程安全的方法，不推荐使用）。

2）特点

　　*调用size()方法的时候，需要遍历队列，通常使用isEmpty()。

　　*不允许插入null元素，会抛出空指针异常。

　　*是无界的，所以使用时，一定要注意内存溢出的问题。即对并发不是很大中等的情况下使用，不然占用内存过多或者溢出，对程序的性能影响很大，甚至是致命的。

2、实现阻塞接口的：
　　java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。
五个队列所提供的各有不同：
　　* ArrayBlockingQueue ：一个由数组支持的有界队列。
　　* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
　　* PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
　　* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
　　* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

二，Set
Set:注重独一无二的性质,该体系集合可以知道某物是否已近存在于集合中,不会存储重复的元素
用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。

对象的相等性

引用到堆上同一个对象的两个引用是相等的。如果对两个引用调用hashCode方法，会得到相同的结果，如果对象所属的类没有覆盖Object的hashCode方法的话，hashCode会返回每个对象特有的序号（java是依据对象的内存地址计算出的此序号），所以两个不同的对象的hashCode值是不可能相等的。

如果想要让两个不同的Person对象视为相等的，就必须覆盖Object继下来的hashCode方法和equals方法。

1、HashSet

哈希表结构，基于HashMap实现，新增元素相当于HashMap的key，value默认为一个固定的Object。

具有如下特点：

不允许出现重复因素；
允许插入Null值；
元素无序（添加顺序和遍历顺序不一致）；
线程不安全，若2个线程同时操作HashSet，必须通过代码实现同步；

2、TreeSet

底层结构为红黑树（特殊的二叉查找树，算法的规则: 左小右大）。

允许自定义排序，通过实现Comparator方法，重写equals方法

结果返回大于0时，方法前面的值大于方法中的值；

结果返回等于0时，方法前面的值等于方法中的值；

结果返回小于0时，方法前面的值小于方法中的值；

具有如下特点：

对插入的元素进行排序，是一个有序的集合（主要与HashSet的区别）;
底层使用红黑树结构，而不是哈希表结构；
允许插入Null值；
不允许插入重复元素；
线程不安全；

三、List

LinkedList和ArrayList的实现方式不同，可以在不同的场景下使用不同的List
ArrayList是由数组实现的，方便查找，返回数组下标对应的值即可，适用于多查找的场景
LinkedList由链表实现，插入和删除方便，适用于多次数据替换的场景

四、Map

1、HashMap

最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null(多条会覆盖)，非同步的。

2、TreeMap

能够把它保存的记录根据键(key)排序,默认是按升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。TreeMap不允许key的值为null。非同步的。

3、Hashtable

与 HashMap类似,不同的是:key和value的值均不允许为null;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢。

4、LinkedHashMap

保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.在遍历的时候会比HashMap慢。key和value均允许为空，非同步的。

5、遍历速度

10W平均值

增强for循环，keySet迭代 -> 31 ms

增强for循环，entrySet迭代 -> 20 ms

迭代器，keySet迭代 -> 17 ms

迭代器，entrySet迭代 -> 10.33 ms

按value排序(通用)

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

map.put("b", "b");

map.put("a", "c");

map.put("c", "a");

// 通过ArrayList构造函数把map.entrySet()转换成list

List<Map.Entry<String, String>> list = new ArrayList<Map.Entry<String, String>>(map.entrySet());

// 通过比较器实现比较排序

Collections.sort(list, new Comparator<Map.Entry<String, String>>() {

    @Override

    public int compare(Map.Entry<String, String> mapping1, Map.Entry<String, String> mapping2) {

        return mapping1.getValue().compareTo(mapping2.getValue());

    }

});

for (String key : map.keySet()) {

    System.out.println(key + " ：" + map.get(key));

}

四种常用Map插入与读取性能比较

　　　　　　插入10次平均(ms)

	1W	10W	100W
HashMap	56	261	3030
LinkedHashMap	25	229	3069
TreeMap	29	295	4117
Hashtable	24	234	3275

　　　　　　　　　　　　　　读取10次平均(ms)

	1W	10W	100W
HashMap	2	21	220
LinkedHashMap	2	20	216
TreeMap	5	103	1446
Hashtable	2	22	259

Map常用遍历性能比较

增强for循环使用方便，但性能较差，不适合处理超大量级的数据。
迭代器的遍历速度要比增强for循环快很多，是增强for循环的2倍左右。
使用entrySet遍历的速度要比keySet快很多，是keySet的1.5倍左右。

Map排序方式

其他类型

List<Map.Entry<String, String>> list = new ArrayList<Map.Entry<String, String>>(map.entrySet());

// 通过比较器实现比较排序

Collections.sort(list, new Comparator<Map.Entry<String, String>>() {

　　@Override public int compare(Map.Entry<String, String> mapping1, Map.Entry<String, String> mapping2) {

　　return mapping1.getKey().compareTo(mapping2.getKey());

　　}

});

Tree类型

Map<String, String> map = new TreeMap<String, String>(new Comparator<String>() {

　　@Override public int compare(String o1, String o2) {

　　// 降序排序 return o1.compareTo(o2);

　　}

});

 优化15条

巴特西