Java 集合框架

Posted on In

Map 属不属于集合？在讨论这个问题之前，要先分清什么才是集合。如果说实现了 Collection 接口的叫集合，那么显然 Map 并不属于集合；如果说集合指的是集合框架（或容器），那么 Map 也属于集合。

《Java 编程思想》的 11 章中，明确表示了集合包含 List、Set、Queue 和 Map ；《Java 核心技术 卷一》中也表示集合有两个基本的接口，Collection 和 Map。集合框架属于 Java 的基础知识，也是日常开发中常用的工具，面试也经常考察，因此作为一个 Java 程序员应该熟练掌握它。

collection_framework

ArrayList

底层维护着一个 Object 数组。使用默认的构造函数会初始化一个容量为 0 的数组，在放第一个元素时会扩容成容量为 10 的数组。可指定初始化容量。扩容时会重新开辟一个计算好容量的数组，并使用 System.arraycopy() 复制元素，每次扩容后容量为上次容量的 1.5 倍，容量上限为 Integer.MAX_VALUE - 8（2^31-1-8）。

1
add(E e);

在容量足够时速度很快，在容量不足时，数组会扩容，因此在可以预见的元素个数超过默认的 10 个时，最好在初始化时指定一个合适的容量。

1
2
3
add(int index,E e);
remove(int index);
remove(E e);

这些方法都需要使用 System.arraycopy() 来移动元素，效率低，并且越是靠前的元素，需要移动的元素越多。

1
2
get(int index);
set(int index,E e);

使用索引，速度快。

总结：使用 ArrayList 最好能够指定容量，获取和修改元素较快，删除效率较低。

LinkedList

底层维护着一个类似双向链表的结构，元素类型是 LinkedList 的静态内部类 Node ，每个 Node 包含它的前一个 Node、后一个 Node 和它本身的数据。LinkedList 将它的头结点和尾节点作为成员变量，每次添加元素都会开辟一个新的 Node 节点，无容量上限。

1
2
get(int index);
set(int index,E e);

查找和修改需要遍历，当要查找的索引位置超过链表大小的一半时，反向遍历。

1
2
3
4
5
add(E e); // 向尾部插入
addFirst(E e);
addLast(E e);
removeFirst();
removeLast();

在 LinkedList 中，添加方法就是向尾部添加元素。上述方法只对链表的头尾两侧操作，不需要移动指针，效率高。

1
2
3
add(int index,E e);
remove(E e);
remove(int index);

上述方法需要遍历查找索引，之后再改变元素前后指针指向，效率相对也较高（与数组不同，不需要改变结构）。

总结：使用 LinkedList 向前后插入元素效率高，其余需要知道索引位置的方法效率相对要低，但是不需要修改结构，是以空间换时间的思路。

HashSet

HashSet 的源码很少，也非常简单。它的内部维护着一个 HashMap，使用 key 存储数据，value 都是同一个 Object 对象。

LinkedHashSet

LinkedHashSet 继承自 HashSet，它的源码更少，也更简单，与 HashSet 唯一区别就是它的内部使用的是 LinkedHashMap 存储数据，可以保证元素的插入顺序与遍历顺序一致。

TreeMap

TreeMap 内部使用的是红黑树结构，插入的数据可以按照 key 的自然顺序排序，也可以自定义比较器实现自定义排序。其增删改查的平均时间复杂度为 O(logN)。

TreeSet

TreeSet 内部使用的是 TreeMap，因此可以保证插入元素的唯一性，并且插入的元素会进行排序。