对于任何一个 Java 程序员来说集合框架Java Containers / Collections都是天天朝夕相处的“老伙计”了。无论是日常拉取数据库的 List 列表还是在内存里做高频缓存的 Map容器几乎承载了整个应用的所有血液。许多初学者刚开始学Java集合的时候看到一堆的ArrayListSet.....难免感到头大但是不难发现Java 的容器世界虽然看似庞大、有几十个实现类但归根结底它们其实只属于两大核心家族。那就是Collection和Map;接下来的篇章便带大家梳理一下其中比较重要的几个实现类当然也是面试中常问到的话不多说我们直接开学!一.Map1.1 Map简介如果说Collection是让元素孤零零地排排坐那么Map接口就是纯粹的“连线大师”。它的核心职责是保存Key-Value的映射关系。在 Map 的世界里有一个不可动摇的底层铁律键Key是绝对唯一的不能重复而每个键最多只能映射到一个值Value。这就像每个人的身份证号Key在系统里只能绑定一个特定的名字Value如果你强行用相同的 Key 再存一次新数据旧的数据就会啪的一下被新内容无情覆盖。面对这种成对出现的数据我们该怎么去访问它呢Map 接口非常贴心地提供了三种 Collection 视图允许我们从不同的视角解剖这个映射表。keySet:如果你只关心所有的钥匙可以通过“键集keySet”把所有的 Key 单独揪出来values:如果你只关心背后的奖品可以通过“值集values”拿到所有的 Value 集合entrySet:而如果你想一网打尽则可以通过“键-值映射关系集entrySet”光说不练假把式。既然聊到了这三大视图咱们来看看在真实的 Java 代码里它们是怎么被剥离出来的。先准备一盘基础数据MapString, String staffMap new HashMap(); staffMap.put(9527, 周星驰); staffMap.put(007, 凌凌漆); staffMap.put(1024, 极客牛马);当你只想知道系统里注册了哪些唯一的工号根本不在乎背后是谁时就用keySet()。// 获取所有的 Key键 SetString employeeIds staffMap.keySet(); System.out.println(--- 所有的工号Keys ---); for (String id : employeeIds) { System.out.println(工号: id); }注意看它的返回值类型是SetK为什么不是List或者是普通的Collection回想一下前面说的铁律 ——Map 里的 Key 具有绝对唯一性不能重复。这刚好和Set接口“去重、唯一”的特性天然吻合。所以 Java 源码规定拿出来的键集用Set来装。换一个场景如果老板说“把今天上班的所有员工名字打印出来我不管他工号是几号。” 这时候你就需要用values()把所有的 Value 抽出来。// 获取所有的 Value值 CollectionString employeeNames staffMap.values(); System.out.println(--- 所有的员工名字Values ---); for (String name : employeeNames) { System.out.println(名字: name); }仔细看返回值这次变成CollectionV了。为什么不用Set了因为Value是可以重复的公司里叫“张三”的可能有两个工号不同就行。既然允许重复Java 底层就用了一个最宽泛的Collection接口来接住这些名字。接下来就是第三种entrySet,这是日常开发中出镜率最高的遍历方式。它会把 Map 里的每一对 Key-Value 整体打包成一个叫Map.Entry的小对象然后放进一个Set里丢给你。// 获取所有的键值对集合Entries SetMap.EntryString, String entrySet staffMap.entrySet(); System.out.println(--- 工号与名字齐活Entries ---); for (Map.EntryString, String entry : entrySet) { // 每一对“红线组合”都可以通过 getKey() 和 getValue() 分别拿到头尾 String id entry.getKey(); String name entry.getValue(); System.out.println(工号【 id 】绑定的员工是: name); }知道了怎么访问Map之后我们来看一下Map的整体结构长什么样便于我们后序对重点的实现类进行讲解:接口:Map是Map容器家族的祖先Map是一个用于Map保存键值对(key-value)的接口。Map中不能包含重复的键;每个键最多只能映射到一个值。SortedMap继承了Map的接口其内容是排序的键值对NavigableMap接口继承了SortedMap,相比于SortedMap,NavigableMap有一系列的“导航”方法;如获取大于/等于某对象的键值对、获取小于/等于某对象的键值对”等等。实现类:HashMap实现了Map主要作用HashMap是储存无序的键值对Hashtable也实现接口Map。因此Hashtable的主要作用是储存无序的键值对。Hashtable和HashMap相比Hashtable在它的主要方法中使用synchronized关键字修饰来保证线程安全。但是由于它的锁粒度太大非常影响读写速度所以现代Java程序几乎不会使Hashtable如果需要保证线程安全一般会用ConcurrentHashMap来替代。TreeMap实现了NavigableMap接口。TreeMap是基于红黑树实现的一种提供顺序访问的Map其主要作用是储存有序的键值对所以键Key需要定义比较大小的逻辑具体顺序可以由指定的Comparator 来决定或者根据键的自然顺序来判断。LinkedHashMap解决了HashMap本身并不保证键值对的顺序的问题如果我们需要按照插入顺序或访问顺序来遍历键值对就需要使用LinkedHashMap了它在内部维护了一个双向链表WeakHashMap继承了Map。WeakHashMap的键是弱引用,它的主要作用是当GC内存不足时会自动将中的key回收这避免了WeakHashMap的内存空间无限膨胀。很明显WeakHashMap适用于作为缓存。1.2 HashMap相信大家对HashMap的常用方法都比较熟悉了所以接下来就通过一个例子带大家简单过一下详细的就不过多阐述:public class HashMapDemo { public static void main(String[] args) { // 1. 创建 HashMap HashMapString, Integer map new HashMap(); // 2. put() 添加元素 map.put(Tom, 90); map.put(Jack, 85); map.put(Alice, 95); System.out.println(初始Map map); // 3. get() 获取元素 System.out.println(Tom的成绩 map.get(Tom)); // 4. getOrDefault() System.out.println(Bob成绩 map.getOrDefault(Bob, 0)); // 5. containsKey() System.out.println(是否包含Jack map.containsKey(Jack)); // 6. containsValue() System.out.println(是否有人得95 map.containsValue(95)); // 7. put() 更新元素 map.put(Tom, 100); System.out.println(Tom更新后 map); // 8. remove() map.remove(Jack); System.out.println(删除Jack map); // 9. size() System.out.println(元素个数 map.size()); // 10. isEmpty() System.out.println(是否为空 map.isEmpty()); // 11. keySet() 遍历所有key System.out.println(\n遍历key); for (String key : map.keySet()) { System.out.println(key); } // 12. values() 遍历所有value System.out.println(\n遍历value); for (Integer value : map.values()) { System.out.println(value); } // 13. entrySet() 遍历键值对最常用 System.out.println(\n遍历Entry); for (Map.EntryString, Integer entry : map.entrySet()) { System.out.println(entry.getKey() - entry.getValue()); } } }要点:基于哈希表访问速度快。进行put或者get操作可以达到常数时间的性能O(1)。(极端情况:当hash冲突比较严重时查找元素只能去链表遍历复杂度为0(n);如果是Java8转化成了红黑树那平均复杂度就是O(logn))元素之间没有顺序性:HashMap使用一个哈希函数将键映射到特定的桶中。这个映射过程是基于键的哈希值并不是线性顺序HashMap最多只允许一条记录的键Key为null;但允许多条记录的Value为null;key为null的键值对会放在第0个桶且只允许一个(当keynull时hash值为0;Java7:数据结构采用(数组链表)实现Java8:数据结构采用(数组链表红黑树)实现。HashMap是非线程安全的需要保证线程安推荐使用并发包中的ConcurrentHashMapHashtable与HashMap的简单对比:HashTable基于Dictionary类而HashMap是基于AbstractMap。Dictionary是任何可以键映射到相应值的类的抽象类而AbstractMap是基于Map接口的实现它以减少实现此接口所需的工作。HashMap 的key和 value都允许为null,而Hashtable 的key和value都不允许为null。HashMap遇到key为null的时候会进行处理而对value没有处理;HashTable是同步的而HashMap则不是。HashTable中的几乎所有公共的方法都是synchronized的。1.2.1 Java7与8的核心进化咱们把 HashMap 的皮扒开大方向上它里面就是一个数组然后数组中的每个元素是一个单向链表。Java 7纯正的“数组 链表”在 Java 7 的世界里数据结构纯粹采用数组 链表实现。这时候如果你去翻源码会发现数组里存的每一个节点都是嵌套类Entry的实例。这个Entry就是承载我们数据的核心“大腰子”它里面雷打不动地包含四个属性key你存进去的键。value你存进去的值。hash算出来的哈希值提前存好免得重复计算。next用于单向链表的指针指向下一个Entry。看完其数据结构了那么我们可以看到下述的构造方法public HashMap(); //默认负载因子0.75 public HashMap(int initialCapacity);其中涉及到了几个专业词汇:initialCapacity初始化容量,即刚创建这个 Map 时它底层的数组大小。capacity当前的数组容量。有一个铁律它始终保持2 的次幂。它可以自动扩容扩容后数组大小直接变为当前的2倍。loadFactor负载因子。它是自动扩容之前被允许的最大饱和量。官方默认给的值是0.75。capacity × loadFactor当size超过这个值时就会触发扩容。扩容就是用一个新的大数组替换原来的小数组并将原来数组总的值迁移到新的数组中默认负载因子为什么是0.75这个值呢?设太大和太小有什么问题?1.加载因子过大: 扩容频率相对较低、哈希冲突更频繁、链表的长度更长、链表转化成红黑树的发生越频繁导致性能有一定下降;2.加载因子过小: 扩容频率相对更频繁、空间利用率低、容易造成性能抖动:总结完我们来看一下经常使用的put方法:public V put(K key, V value) { // 当插入第一个元素的时候需要先初始化数组大小 if (table EMPTY_TABLE) { inflateTable(threshold); } // 如果 key 为 null感兴趣的可以往里看最终会将这个 entry 放到 table[0] 中 if (key null) return putForNullKey(value); // 1. 求 key 的 hash 值 int hash hash(key); // 2. 找到对应的数组下标 //hash (length-1) int i indexFor(hash, table.length); // 3. 遍历一下对应下标处的链表看是否有重复的 key 已经存在 // 如果有直接覆盖put 方法返回旧值就结束了 for (EntryK,V e table[i]; e ! null; e e.next) { Object k; if (e.hash hash ((k e.key) key || key.equals(k))) { V oldValue e.value; e.value value; e.recordAccess(this); return oldValue; } } modCount; // 4. 不存在重复的 key将此 entry 添加到链表中细节后面说 addEntry(hash, key, value, i); return null; }在上述的put方法中我们可以看到第一步是先判断table容器是否为空如果为空的话会调用inflateTable来进行数组初始化我们来看一下这个方法的源码:private void inflateTable(int toSize) { // 保证数组大小一定是 2 的 n 次方。 // 比如这样初始化: new HashMap(20), 那么处理成初始数组大小是 32 int capacity roundUpToPowerOf2(toSize); // 计算扩容阈值: capacity * loadFactor threshold (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1); // 算是初始化数组吧 table new Entry[capacity]; initHashSeedAsNeeded(capacity); //ignore }可以看到它主要的功能是确定初始的数组大小并计算数组扩容的阈值值得注意的一点在于这里有一个将数组大小保持为2的n次方的做法Java7 和 Java8 的HashMap 和 ConcurrentHashMap 都有相应的要求。为啥必须为2的n次方?因为我们在计算数组下标的时候一般采取的是取模的方法例如hash%length;但是取模运算%相对于位与运算 an是更慢的所以能用位与运算替代取模运算的话就会带来一定的性能优化。但是要用“位与运算”替代“取模运算%”需要满足一定的条件那就是:只有当length为2的n次方的时候hash% lengthhash (length-1)才成立举例:hash 35 100011length 32 100000hash % length 35%32 3hash (length-1) 35 311000110111110000113看完put方法我们常用的get方法会更简单一些它的实现过程可以总结如下:根据来计算hash值找到对应的数组下标hash(length-1)遍历该数组位置处的链表(此链表是hash冲突时产生的链表)直到找到相等(或者equals)的key在进入Java8的原理之前我们先来总结一下Java7的:Java 8: 数组 链表 红黑树由上图数据结构示意图可知到了 Java 8底层数据结构变成了数组 链表 红黑树。虽然底层的嵌套类改名叫Node本质还是那四个属性但最大的改变在于当某一个数组位置上的链表长度大于 8并且数组总容量大于等于 64时这个单向链表就会当场黄袍加身转化成一棵红黑树节点变成TreeNode。这就把上面提到的极端 O(n)情况完美优化成了 O(log n)。Java8中put方法大致的思路和Java7类似不同之处在于如果哈希碰撞导致链表过长(大于等于TREEIFY THRESHOLD数值为8)并且满足容量大于等于64就把链表转换成红黑树;如果容量不满足大于等于64的条件那就触发扩容扩容会将原来为8的链表节点分散开缩短链表长度。而当红黑树节点数量减少变为6时树会退化为链表这个地方会出现面试题Java8中链表转红黑树和红黑树转链表为什么是8和6?答: 红黑树中的TreeNode是链表中的Node所占空间的2倍虽然红黑树的查找效率为o(logN)要优于链表的o(N)但是当链表长度比较小的时候即使全部遍历时间复杂度也不会太高。故要寻找一种时间和空间的平衡即在链表长度达到一个阈值之后再转换为红黑树。之所以是8: 是因为Java的源码贡献者在进行大量实验发现hash碰撞发生8次的概率几乎为不可能事件如果真的碰撞发生了8次那么说明此时的链表性能已经很差了操作的hash碰撞的可能性非常大了后续可能还会继续发生hash碰撞。所以在这种极端的情况下才会把链表转换为红黑树链表转换为红黑树也是需要消耗性能的为了挽回性能权衡之下才使用红黑树提高性能的大部分情况下hashMap还是使用链表红黑树转链表的阈值为6:主要是因为如果也将该阈值设置8那么当hash碰撞个数在8左右时会反生链表和红黑树的不停相互激荡转换白白浪费资源。中间有个差值7可以防止链表和树之间的频繁转换面试题:为什么是红黑树而不是平衡树AVL?答:AVL树更加严格平衡因此可以提供更快的查找效果。但是带来的代价就是添加/删除速度更慢因为会进行更多次数的旋转平衡操作。红黑树在添加/删除/查找方面取了折中表现都相对较好。总结一下put的关键要点就是:Java8采用的采用尾插法Java7采用头插法。(头插改尾插能解决并发状态下hashmap出现死循环的问题。关于hashmap并发问题的讲解这里不展开,后续会展开。)和Java7稍微有点不一样的地方就是Java7是先扩容后插入新值的Java8先插值再扩容。回顾一下之前Java7在计算hash方法实现的时候采取的公式是:(n-1) hash但是在java8中这里是把key的hashcode取出来然后把它右移16位然后取异或为什么这么做呢?之前的方法设计者认为很容易发生碰撞。为什么这么说呢?不妨思考一下在n-1为15(0x1111)时其实散列真正生效的只是低4bit的有效位当然容易碰撞了。因此设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)就是把高16bit和低16bit异或了下让hash值的高位数据也能参与到最终的下标计算中这样结果更随机从而减少不同hash值计算出的下标发生碰撞的可能。1.2.2 HashMap不是线程安全的在1.2.1我们讲了HashMap不是线程安全的HashTable才是线程安全那么在下面这一节我们将会着重介绍为什么HashMap不是线程安全的?在并发安全的情况下会产生什么问题呢?而且面试有时候也会问你HashMap多线程情况下会产生什么影响?那么在详细介绍前先开门见山其会出现两个问题:1. 数据覆盖问题2. 扩容时导致的死循环问题数据覆盖问题假设其中一个场景A、B两个线程同时执行put()操作且两个key都指向同一个bucket那么此时两个结点都会做头插法。其中涉及到createEntry()方法他主要工作是获取到了bucket上的头结点然后再将新结点作为bucket的头部并指向旧的头结点完成一次头插法的操作。好那么我们现在继续刚刚的场景当线程A和线程B都获取到了bucket的头结点后若此时线程A的时间片用完线程B将其新数据完成了头插法操作此时轮到线程A操作但这时线程A所据有的旧头结点已经过时了(并未包含线程B刚插入的新结点)线程A再做头插法操作就会抹掉B刚刚新增的结点导致数据丢失。而JDK8是将头插法改为了尾插法所以这个覆盖的问题还是存在并没有解决。当然不光是put()操作删除操作、修改操作同样都会有覆盖问题。讲完第一个问题我们接下来将第二个问题也是最常遇到的情况:扩容时导致死循环但是这个问题不同于数据覆盖问题它只有JDK7及以前的版本会存在死循环现象在JDK8中resize()方式已经做了调整都是使用的尾插法即使多线程下也不会造成死循环。而JDK7能造成死循环就是因为resize()时使用了头插法将原本的顺序做了反转才留下了死循环的机会。实在不想整理了这部分原因可以看下述的这篇文章链接如下: 为什么 HashMap 会死循环扩展:Comparable和Comparator既然前面咱们聊到TreeMap必须得按顺序排列 Key那这里面就必然牵扯到 Java 蓝星上最容易让人搞混的一对“双子星”接口Comparable和Comparator。这两个词长得像亲兄弟一样好多人面试时一两句话根本说不清。咱们今天就把这两个接口揉碎了聊看看它们在底层到底是怎么指挥对象去排队的。先来说Comparable。这个接口的名字叫“可比较的”它的特点是从内部改变一个类。你想啊如果一个类比如User实现了Comparable接口那就意味着这个类在出生的时候它的基因里就自带了“怎么跟同类比大小”的属性。它里面只有一个方法需要你实现compareTo(T o)你可以把它理解为“自力更生”。对象自己跟别人比。// 实现了 Comparable意味着 User 具备了天生的排序能力 public class User implements ComparableUser { private String name; private int age; Override public int compareTo(User other) { // 拿自己的年龄跟别人的年龄比 // 返回正数说明我大负数说明我小0说明咱俩一样大 return this.age - other.age; } }什么时候用它呢当你觉得这个类有一个绝对占主导地位的、默认的排序规则时。比如商品默认按 ID 排序学生默认按学号排序。这就是它的“自然排序”。那既然有了Comparable为什么 Java 大佬还要再搞一个Comparator呢这时候你得换个场景想。第一种情况假设你现在在用别人写好的String类或者大厂封装好的老代码你根本没有权限去修改人家的源码、往人家的基因里塞Comparable接口。第二种情况你的User类虽然默认按年龄排序了但今天运营产品经理突然抽风说要在某一个活动页面按用户的姓名首字母排序明天又说要按注册时间排序。你的类只能实现一次Comparable总不能天天改源码里的基因吧这时候Comparator比较器就闪亮登场了。它不需要类自己去实现而是像一个外聘的第三方裁判。它里面最核心的方法是compare(T o1, T o2)裁判站在上帝视角把两个对象拿过来帮它们排座位。// 这是一个独立的裁判类专门管按名字排序 public class NameComparator implements ComparatorUser { Override public int compare(User u1, User u2) { // 裁判手握两个对象直接比对它们的名字 return u1.getName().compareTo(u2.getName()); } }回过头来咱们把它们代入到TreeMap或者Collections.sort()的案发现场。如果你用的是Comparable// 因为 User 类基因里实现了 ComparableTreeMap 会自动调用 compareTo 帮它们排好序 TreeMapUser, String map new TreeMap(); map.put(new User(张三, 18), VIP);如果你用的是Comparator// User 类里有没有排序基因无所谓因为我们在创建 TreeMap 的时候硬塞给它一个外聘裁判 TreeMapUser, String map new TreeMap(new NameComparator()); // 或者直接塞 Lambda TreeMapUser, String map new TreeMap((u1, u2) - u1.getAge() - u2.getAge());维度ComparableComparator角色定位对象的天生基因自然排序外聘的特约裁判定制排序源码位置java.lang包下java.util包下核心方法compareTo(T o)自己跟别人比compare(T o1, T o2)裁判比两个人对源码的影响必须修改目标类的源码去实现它不需要修改目标类完全解耦灵活性一个类只能实现一次规则写死了可以写出无数个不同的裁判随用随换二.List2.1 List简介介绍完Map之后我们再来看一下日常开发以及面试中也是经常使用到的list;而List的成员有以下几种实现:ArrayList,LinkedList,Stack,Vector;其中ArrayList,LinkedList是线程不安全的而Stack与Vector是线程安全的但是在实际开发中这两者基本上都放弃使用了所以这次的重点是ArrayList以及LinkedList,在正式介绍他俩之前我们先来对其进行整体概述:底层数据结构: ArrayList基于动态数组实现,而LinkedList基于双向链表实现。扩容: ArrayList基于动态数组实现存在容量限制当元素数超过最大容量时会自动扩容; LinkedList基于双向链表实现不存在容量限制。CPU 缓存局部性:ArrayList在内存中存储连续适合下标访问(随机访问)可以很好地利用CPU缓存局部性原理; LinkedList的元素存储不连续访问时可能跳转到不同地址无法利用CPU缓存局部性原理。非线程安全:ArrayList和LinkedList 都不是线程用户安全的。浅拷贝: LinkedList以及ArrayList都实现了Cloneable接口默认为浅拷贝。知识补充:CPU cache的局部性原理:利用时间局部性和空间局部性提高内存访问效率。时间局部性指近期访问过的数据会被再次访问空间局部性指被访问的数据附近的数据也会被访问。通过这种原理CPUcache能够预先缓存可能频繁访问的数据块减少对慢速主存的访问从而提高程序执行速度优化整体性能。2.2 ArrayListArrayList是一个数组队列相当于动态数组。ArrayList默认创建时容量为0第一次添加元素时才会使用默认初始容量10继续添加元素时如果发现容量已满会自动扩容为原始大小的1.5倍。因此应该尽量在初始化ArrayList 时为其指定合适的初始化容量大小减少扩容操作产生的性能开销。ArrayList中有一个Array,那么他俩之间的区别是什么呢?我们可以从以下几点阐述:ArrayList会根据实际存储的元素动态地扩容而Array被创建之后就不能改变它的长度了。ArrayList配合泛型能将许多类型错误提前到编译阶段暴露出来使程序更安全、更易调试;而传统的数组在这方面存在不足某些类型错误只有到运行时才会触发异常。这就是使用泛型确保类型安全”这句话的典型体现。ArrayList中只能存储对象。对于基本类型数据需要使用其对应的包装类(如Integer、Double等)。Array可以直接存储基本类型数据也可以存储对象。ArrayList支持插入、删除、遍历等常见操作并且提供了丰富的API操作方法比如add()、remove()等。Array只是一个固定长度的数组只能按照下标访问其中的元素不具备动态添加、删除元素的能力。ArrayList创建时不需要指定大小而Array创建时必须指定大小。三. Set和前面类似但是我们需要注意Set集合的一个个比较重要的特点:Set集合中的元素是唯一的所以不会出现重复的元素。总结一下:HashSet中存储的元素是无序的。HashSet允许null值的元素。HashSet不是线程安全的。说白了HashSet浑身上下没有一块骨头是自己的它全都在“空手套白狼”地依赖HashMap。你想啊Set 的核心诉求是什么不就是去重、保证元素唯一吗这时候设计 Java 容器的那帮大佬一琢磨既然 Map 里的Key本来就是唯一的、不能重复的那我还费个什么劲去重新写一套去重的算法和数据结构直接把 Map 拿过来套个马甲不就完了所以当你点开HashSet的源码你会发现它的构造函数里第一行就写着private transient HashMapE,Object map;那你肯定会好奇Map 存的是“键值对Key-Value”Set 存的可是“单个元素”啊这怎么对应上去这就不得不佩服大佬们的骚操作了。他们直接在HashSet内部定义了一个毫无实质卵用的虚无对象叫PRESENTprivate static final Object PRESENT new Object(); // 一个占位的 dummy 对象当你调用hashSet.add(张三)的时候它在底层其实是这么调用的public boolean add(E e) { return map.put(e, PRESENT) null; // 你的值被拿去当 KeyValue 全都塞这个 PRESENT }看懂了吧你放进HashSet里的所有元素其实在底层全被当成了HashMap的 Key。 至于 Value因为不能空着大家就共享同一个没有任何意义的PRESENT占位对象。既然底子是HashMap那HashMap的臭脾气HashSet自然是一成不变地全盘继承了。最直接的表现就是HashSet里的元素是完全无序的、散列的。所以下次如果有人问你HashSet怎么实现去重的你直接告诉他别问我问HashMap去它只是个披着羊皮的 HashMap 罢了。其它的LinkedHashSet和TreeSet也类似就不在此过多介绍。四.QueueJava中的Queue(队列)是一种具有先进先出(FIFO)特性的集合框架可以用于存储一组元素并支持在队列的一端插入元素在另一端移除元素。其中:ArrayDeque是Deque的动态数组实现。LinkedList是 Deque的双向链表实现。PriorityQueue是Deque的堆实现。它基于二叉堆实现并且其中的元素根据自然排序或Comparator提供的顺序排序不接受null值元素