类集五大核心接口Collection、List、Set、Map、Iterable，实现了基础的动态长度的数据结构，利用泛型保存相同类型数据避免向下转型，接口的使用需要子类实现
[toc]
类集接口 Java.util.Collection
所有类集的父接口，为单值集合：每次只能操作一个数据对象
public interface Collection<E> extends Iterable<E> boolean add (E e) 向集合保存单个数据 boolean addAll (Collection<? extends E> c) 向集合追加一组数据 void clear () 清空集合，根节点为空同时GC boolean contains (Object o) 查询数据是否存在，需要equals()方法 boolean remove (Object o) 数据删除，需要equals()方法 int size () 集合中数据数量，至多Integer.MAX_VALUE boolean isEmpty () 判空 Object[] toArray () 集合作对象数组返回 Iterator<E> iterator () 集合转为iterator接口，用作数据输出
List接口 Java.util.List
List接口允许保存重复元素，允许保存null，含有Collection接口所有方法并作出扩充，List子类包括ArrayList，Vector，LinkedList
public interface List<E> extends Collection<E> E get (int index) 获取指定索引数据 E set (int index, E element) 修改指定索引数据 ListIterator<E> listIterator () 返回ListIterator接口对象 static <E> List<E> of (E e1, E e2, E e3) 返回一个参数组成的List
List使用
// 子类实例化
List<String> list = new ArrayList<>();
// List<String> list = new LinkedList<>();
// List<String> list = new Vector<>();
// 添加数据，与list中存储顺序一致
list.add("string");
list.add("string");
// 获得索引数据
list.get(0);
// 判空
list.isEmpty();
// 长度
list.size();
// 按由前向后顺序删除第一个匹配
list.remove("string");
// 输出集合
System.out.print(list);
// Iterable接口forEach输出
list.forEach((str) -> {
System.out.print(str);
});
// forEach方法引用
list.forEach(System.out::println);
存储引用类型对象
List接口使用remove()、contains()方法时需要覆写equals()方法
String类型已经覆写equals()方法无需重写
class Custom{
int num;
String str;
public Custom(int num, String str){
this.num = num;
this.str = str;
}
@Override
public boolean equals(Object obj) {
if(obj == this) return true;
if(obj == null) return false;
if(!(obj instanceof Custom)) return false;
Custom c = (Custom)obj;
return this.num ==c.num && this.str.equals(c.str);
}
}
public static void main(String[] args){
List<Custom> list = new ArrayList<>();
list.add(new Custom(1,"Test1"));
list.add(new Custom(2,"Test2"));
list.remove(new Custom(1,"Test1"));
list.forEach((obj)->{
System.out.print(obj.num);
System.out.print(obj.str);
System.out.println();
});
}
2Test2
子类区别
| 子类 | ArrayList | Vector | LinkedList |
|---|---|---|---|
| 内部封装实现 | 对象数组 | 对象数组 | 链表 |
| 存储方式 | 顺序存储 | 顺序存储 | 链式存储 |
| 内存使用 | 仅存储数据域 | 仅存储数据域 | 需存储指针域 |
| 查找时间复杂度 | O(1) | O(1) | O(n) |
| 插入删除性能 | 移动大量元素性能差 | 移动大量元素性能差 | 表尾增改指针删性能好 |
| 线程安全性 | 不安全 | 安全 | 不安全 |
ArrayList子类
继承结构
源码分析[JDK1.8]
ArrayList是对象数组elementData的封装
为避免ArrayList扩充和拷贝导致性能下降，建议预估容量有参构造
无参构造 分配空的对象数组
有参构造 传入参数直接分配对应大小的对象数组
- 添加扩充流程
- 源码解析
private int size; transient Object[] elementData; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; protected transient int modCount = 0; private static final int DEFAULT_CAPACITY = 10; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 无参构造 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 有参构造 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } } // 添加扩充 public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } // minCapacity = size + 1 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } // 空数组返回10，否则返回size + 1 private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } // 容量不够计算尺寸扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 溢出后结果>0仍可进入grow方法 if (minCapacity - elementData.length > 0) grow(minCapacity); } // 扩充容量 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 扩充为原来的1.5倍，溢出从oldCapacity=1796357452开始 int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容容量不够（空数组newCapacity=0），扩容后溢出结果>0 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 扩容容量超过MAX_ARRAY_SIZE（包含溢出）调用hugeCapacity传入size+1 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } // size+1溢出抛异常，否则扩充更大值 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
LinkedList子类
继承结构
源码分析[JDK1.8]
LinkedList是链表的封装
无参构造无操作，扩充时只在尾部添加
// 尾节点 transient Node<E> last; // 构造方法 public LinkedList() { } // 表尾添加元素 public boolean add(E e) { linkLast(e); return true; } // 保存最后一个结点提升插入性能 void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
Vector子类
继承结构
与ArrayList完全相同
源码分析[JDK1.8]
Vector同ArrayList类似是对象数组的封装
Vector加入了线程安全机制但会有性能下降
Vector默认扩容策略同ArrayList，改为扩容2倍
// 无参构造默认初始化容量为10 public Vector() { this(10); } // 指定容量的有参构造方法 public Vector(int initialCapacity) { this(initialCapacity, 0); } // 初始化封装对象数组 public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } // 添加扩容 public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } // 容量增加则扩容 private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } // 指定增量按增量扩，否则扩容为旧对象数组长度的两倍 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } // 同ArrayList private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
Set接口 Java.util.Set
Set接口不允许保存重复元素，允许保存null，含有Collection接口所有方法并作出扩充，Set子类包括HashSet，TreeSet，LinkedHashSet
Set接口中无List接口get方法，无法实现指定索引数据获取
Set使用
static <E> Set<E> of (E e1, E e2) // JDK1.9
// 重复数据报异常
Set<String> set = Set.of("test","test","hello","world");
all.forEach(System.out::println);
Set集合通过of方法构造不允许含重复元素，否则报ClassCastException，一般通过子类实例化构造
Set<String> set = new HashSet<>();
set.add(null);
set.add("hello");
set.add("hello");
System.out.print(set); // 去重且无序
HashSet子类
数据去重无序保存
继承结构
源码分析[JDK1.8]
HashSet底层封装为HashMap，默认初始化容量为16，到达容量75%时扩容
TreeSet子类
数据去重有序保存
继承结构
自定义类排序
TreeSet保存自定义类对象需要实现Comparable接口，覆写compareTo方法
覆写compareTo方法需要比较类中所有属性，否则属性相同会导致错误去重
添加null元素需要在Comparable / Comparator接口中加入逻辑，否则报空指针
public TreeSet () 默认Comparable接口排序 public TreeSet (Comparator<? super E> comparator) 使用Comparator接口排序 public int compareTo( NumberSubClass referenceName ) 返回值<-1，=0，>1
class Test implements Comparable<Test> {
int num;
String label;
public Test(int num, String label){
this.num = num;
this.label = label;
}
@Override
public String toString() {
return "num = " + this.num
+" label = "+ this.label;
}
@Override
public int compareTo(Test o) {
if (this.num < o.num) {
return -1;
} else if (this.num == o.num) {
return 0;
} else {
return 1;
}
}
}
public static void main(String[] argv) {
Set<Test> set = new TreeSet<>();
set.add(new Test(2, "Two"));
set.add(new Test(3, "Three"));
set.add(new Test(1, "Four"));
set.add(new Test(1, "One"));
System.out.println(set);
}
[num = 1 label = One, num = 2 label = Two, num = 3 label = Three]
值相等时加入String类型比较，String类已覆写compareTo方法
@Override
public int compareTo(Test o) {
if (this.num < o.num) {
return -1;
} else if (this.num > o.num) {
return 1;
} else {
return this.label.compareTo(o.label);
}
}
[num = 1 label = Four, num = 1 label = One, num = 2 label = Two, num = 3 label = Three]
集合自定义类去重
TreeSet子类实现SortedSet，NavigabledSet和Comparable接口，通过compareTo方法return 0去重
其他集合子类无法通过Comparable接口去重，类中覆写Object类中的hashCode()和equals()方法去重
先计算和比较hashCode，若相同则使用equals比较内容，避免与集合中所有元素equals一一比较提高性能
public static int hash(Object... values) { return Arrays.hashCode(values); } // 通过hash算法计算出唯一地址 public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; }
class Test{
int num;
String label;
public Test(int num, String label){
this.num = num;
this.label = label;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Test test = (Test) o;
return num == test.num && Objects.equals(label, test.label);
}
@Override
public int hashCode() {
return Objects.hash(num, label);
}
@Override
public String toString() {
return "num = " + this.num +" label = "+ this.label;
}
}
public static void main(String[] argv) {
Set<Test> set = new HashSet<>();
set.add(new Main().new Test(2, "Two"));
set.add(new Main().new Test(3, "Three"));
set.add(new Main().new Test(1, "One"));
set.add(new Main().new Test(1, "One"));
System.out.println(set);
}
[num = 1 label = One, num = 2 label = Two, num = 3 label = Three]
集合输出
集合输出四种方式：Iterator、ListIterator、Enumeration、foreach