Java 集合, 也叫作容器,主要是由两大接口派生而来:一个是 Collecton接口,主要用于存放单一元素;另一个是 Map 接口,主要用于存放键值对。对于Collection 接口,下面又有三个主要的子接口:List、Set 和 Queue。下图中列举了主要的继承派生关系:
【List】
Arraylist: Object[] 数组
Vector:Object[] 数组
LinkedList: 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环)
【Set】
HashSet(无序,唯一): 基于 HashMap 实现的,底层采用 HashMap 来保存元素
LinkedHashSet: LinkedHashSet 是 HashSet 的子类,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的
TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树)
【Queue】
PriorityQueue: Object[] 数组来实现二叉堆
ArrayQueue: Object[] 数组 + 双指针
【HashMap】
JDK1.8 之前 HashMap 由数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间
【LinkedHashMap】
LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。详细可以查看:《LinkedHashMap 源码详细分析(JDK1.8)》
【Hashtable】
数组+链表组成的,数组是 Hashtable 的主体,链表则是主要为了解决哈希冲突而存在的
【TreeMap】
红黑树(自平衡的排序二叉树)
主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合,需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。
当我们只需要存放元素值时,就选择实现Collection 接口的集合,需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet,不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList,然后再根据实现这些接口的集合的特点来选用。
ArrayList 是 List 的主要实现类,底层使用 Object[ ]存储,适用于频繁的查找工作,线程不安全 ;
Vector 是 List 的古老实现类,底层使用Object[ ] 存储,线程安全的。
一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo()方法或compare()方法,当我们需要对某一个集合实现两种排序方式,比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的 Collections.sort().
ArrayList<Integer> arrayList = new ArrayList<Integer>(); arrayList.add(-1); arrayList.add(3); arrayList.add(3); arrayList.add(-5); arrayList.add(7); arrayList.add(4); arrayList.add(-9); arrayList.add(-7); System.out.println("原始数组:"); System.out.println(arrayList); // void reverse(List list):反转 Collections.reverse(arrayList); System.out.println("Collections.reverse(arrayList):"); System.out.println(arrayList); // void sort(List list),按自然排序的升序排序 Collections.sort(arrayList); System.out.println("Collections.sort(arrayList):"); System.out.println(arrayList); // 定制排序的用法 Collections.sort(arrayList, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); System.out.println("定制排序后:"); System.out.println(arrayList);
output:
原始数组: [-1, 3, 3, -5, 7, 4, -9, -7] Collections.reverse(arrayList): [-7, -9, 4, 7, -5, 3, 3, -1] Collections.sort(arrayList): [-9, -7, -5, -1, 3, 3, 4, 7] 定制排序后: [7, 4, 3, 3, -1, -5, -7, -9]
// person对象没有实现Comparable接口,所以必须实现,这样才不会出错,才可以使treemap中的数据按顺序排列 // 前面一个例子的String类已经默认实现了Comparable接口,详细可以查看String类的API文档,另外其他 // 像Integer类等都已经实现了Comparable接口,所以不需要另外实现了 public class Person implements Comparable<Person> { private String name; private int age; public Person(String name, int age) { super(); this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } /** * T重写compareTo方法实现按年龄来排序 */ @Override public int compareTo(Person o) { if (this.age > o.getAge()) { return 1; } if (this.age < o.getAge()) { return -1; } return 0; } }
public static void main(String[] args) { TreeMap<Person, String> pdata = new TreeMap<Person, String>(); pdata.put(new Person("张三", 30), "zhangsan"); pdata.put(new Person("李四", 20), "lisi"); pdata.put(new Person("王五", 10), "wangwu"); pdata.put(new Person("小红", 5), "xiaohong"); // 得到key的值的同时得到key所对应的值 Set<Person> keys = pdata.keySet(); for (Person key : keys) { System.out.println(key.getAge() + "-" + key.getName()); } }
output:
5-小红 10-王五 20-李四 30-张三
HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类,都能保证元素唯一,并且都不是线程安全的。
HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表(基于 HashMap 实现)。LinkedHashSet 的底层数据结构是链表和哈希表,元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树,元素是有序的,排序的方式有自然排序和定制排序。
底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景,LinkHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景,TreeSet 用于支持对元素自定义排序规则的场景。
【Queue】
Queue 是单端队列,只能从一端插入元素,另一端删除元素,实现上一般遵循 先进先出(FIFO) 规则。
Queue 扩展了 Collection 的接口,根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常,另一种则会返回特殊值。
【Deque】
Deque 是双端队列,在队列的两端均可以插入或删除元素。
Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法,同样根据失败后处理方式的不同分为两类:
事实上,Deque 还提供有 push() 和 pop() 等其他方法,可用于模拟栈。
ArrayDeque 和 LinkedList 都实现了 Deque 接口,两者都具有队列的功能,但两者有什么区别呢?
ArrayDeque 是基于可变长的数组和双指针来实现,而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据,但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的,而LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容,但是每次插入数据时均需要申请新的堆空间,均摊性能相比更慢。
从性能的角度上,选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外,ArrayDeque 也可以用于实现栈。
PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的,即总是优先级最高的元素先出队。
这里列举其相关的一些要点:
PriorityQueue 利用了二叉堆的数据结构来实现的,底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉,实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的,且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆,但可以接收一个 Comparator 作为构造参数,从而来自定义元素优先级的先后。
说一说 PriorityQueue
PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的,即总是优先级最高的元素先出队。
这里列举其相关的一些要点:
PriorityQueue 利用了二叉堆的数据结构来实现的,底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉,实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的,且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆,但可以接收一个 Comparator 作为构造参数,从而来自定义元素优先级的先后。
PriorityQueue 在面试中可能更多的会出现在手撕算法的时候,典型例题包括堆排序、求第K大的数、带权图的遍历等,所以需要会熟练使用才行。