Java集合框架深度解析：数据结构与高效编程实践

首页  知识社区  Java集合框架深度解析：数据结构与高效编程实践

集合概述 Collection接口 List接口 Set接口 Queue接口 Map接口集合的内部实现

引言

在Java编程语言中，集合框架扮演着至关重要的角色。它不仅提供了丰富的数据结构，还为数据的存储和管理提供了强大的支持。本文将深入探讨Java集合框架的各个方面，包括其基本概念、主要类及其特点，并通过实际示例展示其应用。通过阅读本文，你将能够全面理解Java集合框架，并掌握如何在实际编程中高效地使用它。

集合概述

在Java中，集合类是用来存放对象的容器。集合相当于一个容器，里面包容着一组对象。这些对象作为集合的一个元素出现。Java API提供的集合类位于java.util包内。集合与数组有许多相似之处，但它们之间也存在一些显著的区别。

数组与集合的比较

长度区别：数组的长度是固定的，一旦创建，其大小不能改变。集合的长度是可变的，可以根据需要动态地增加或减少元素。
内容区别：数组可以存储基本数据类型（如int、double等）或对象的引用。集合只能存储对象的引用。
元素内容：数组只能存储同一种类型的元素。集合可以存储不同类型的元素，但通常也会存储同一种类型的元素。

java集合与数组区别

Collection接口

Collection是最基本的集合接口，它定义了集合的基本操作。所有集合类都实现了这个接口，或者实现了它的子接口。

Collection接口的方法

boolean add(E e)：添加一个对象到集合中。
void clear()：移除集合中的所有对象。
boolean remove(Object o)：移除集合中的一个指定对象。
Iterator<E> iterator()：返回一个迭代器，用于遍历集合中的元素。

List接口

List是Collection的一个子接口，它进一步定义了有序集合的操作。List可以包含重复的元素，并且可以精确控制元素的插入位置。

ArrayList

特点：排列有序，可重复。
底层实现：使用数组。
性能：访问速度快，增删慢，getter和setter快。
线程安全性：线程不安全。
扩容机制：容量不够时，ArrayList是当前容量乘以1.5再加1。

Vector

特点：排列有序，可重复。
底层实现：使用数组。
性能：访问速度快，增删慢。
线程安全性：线程安全，但效率低。
扩容机制：容量不够时，默认扩大一倍。

LinkedList

特点：排列有序，可重复。
底层实现：使用双向循环链表。
性能：查询慢，增删快。
线程安全性：线程不安全。

Java List接口详细描述

Set接口

Set是Collection的一个子接口，它定义了不允许重复的集合操作。Set注重独一无二的性质，存储的元素不能重复。

HashSet

特点：排列无序，不可重复。
底层实现：使用哈希表。
性能：存取速度快。
内部结构：内部是HashMap。

TreeSet

特点：排列无序，不可重复。
元素内容：排序存储。
内部结构：内部是TreeMap的SortedSet。

LinkedHashSet

特点：采用哈希表存储，并用双向链表记录插入顺序。
内部结构：内部是LinkedHashMap。

Java Set接口及其子类详细描述

Queue接口

Queue是Collection的一个子接口，它定义了队列的操作。队列是一种特殊类型的集合，用于按照特定的顺序（通常是FIFO，即先进先出）处理元素。

Map接口

Map是Java集合框架中的另一个重要接口，它定义了键值对的映射关系。Map集合可以存储键值对，其中键是唯一的。

HashMap

特点：键不可重复，值可重复。
底层实现：使用哈希表。
线程安全性：线程不安全。
null值：允许键和值为null。

HashTable

特点：键不可重复，值可重复。
底层实现：使用哈希表。
线程安全性：线程安全。
null值：key和value都不能为null。

TreeMap

特点：键不重复，值可重复。
底层实现：使用二叉树。

集合的内部实现

HashMap的实现

JDK1.7实现：HashMap内部是一个数组，数组中的每个元素是一个单向链表。容量始终保持2的幂次方，可以扩容，扩容后数组大小为当前的2倍。负载因子默认为0.75，扩容的阈值等于容量乘以负载因子。
JDK1.8实现：Java8对HashMap进行了修改，利用了红黑树，其由数组+链表+红黑树组成。查找时，根据hash值快速定位到数组的具体下标，但需要顺着链表一个个比较才能找到需要的元素。为了降低这部分的开销，当链表中的元素超过8个以后，会将链表转换为红黑树，降低查找时间复杂度为O(logN)。

ConcurrentHashMap的实现

JDK1.7实现：由Segment数组和HashEntry组成，和HashMap一样，是数组加链表。核心数据如value及链表都是volatile修饰的，保证了获取时的可见性。采用分段锁技术，其中Segment继承于ReentrantLock。
JDK1.8实现：抛弃了原有的Segment分段锁，采用了CAS+synchronized来保证并发安全性。val和next都用了volatile修饰，保证了可见性。

HashTable

特点：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的。任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

TreeMap

特点：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器。当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。