List、Set、数据结构、Collections
一、与集合相关的数据结构
1. 栈
- 先进后出
2. 队列
- 先进先出
3. 数组
- 查询快：数组的地址是连续的，通过数组的首地址就可以找到数组，通过数组的索引就可以快速查找某一个元素。
- 增删慢：数组的长度是固定的，想要增加、删除一个元素，必须创建一个新数组，把原数组的数据复制到新数组。（在堆内存中，频繁的创建数组，复制数组中的元素，销毁数组，故效率低下。）
4. 链表
-
查询慢：链表中的地址不是连续的，所以每次查询元素时，都必须从头开始查询。
-
增删快：增加、删除一个元素，对于链表的整体结构没有影响，所以增删快。
-
单向链表：链表中只有一条链，不能保证元素的顺序 (存储元素和取出元素的顺序可能不一致)。
- 双向链表：链表中有两条链，其中有一条链专门用来记录元素的顺序，是一个有序集合。
5. 红黑树
- 二叉树：分支不能超过两个。
- 排序树/查找树：在二叉树的基础上，元素是有大小顺序的。左子树小，右子树大。
- 平衡树：平衡因子的绝对值不超过一。
- 红黑树：趋近于平衡树，查询的速度非常快，查询叶子节点最大次数和最小次数不能超过二倍。
- 节点可以是红色的或者黑色的。
- 根节点是黑色的。
- 叶子节点是黑色的。
- 每个红色节点的子节点都是黑色的。
- 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同。
二、List接口
1. List接口的介绍与常用方法
java.util.list接口 extends Collection接口- 特点：
- 有序的集合，存储元素和取出元素的顺序是一致的。
- 有索引，包含了一些带索引的方法。
- 允许存储重复的元素。
List接口中带索引的方法：public void add(int index, E element)将指定的元素，添加到该集合中的指定位置上。public E get(int index)返回集合中指定位置的元素。public E remove(int index)移除列表中指定位置的元素，返回的是被移除的元素。public E set(int index, E element)用指定元素替换集合中指定位置的元素，返回值是被替换的元素。
- 注意：
- 操作索引的时候，一定要防止索引越界异常。
IndexOutOfBoundsException索引越界异常。ArrayIndexOutOfBoundsException数组索引越界异常。StringIndexOutOfBoundsException字符串索引越界异常。
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
System.out.println(list); // [1, 2, 3]
list.add(1,10);
list.add(3,20);
list.add(5,30);
System.out.println(list); // [1, 10, 2, 20, 3, 30]
System.out.println(list.get(1)); // 10
System.out.println(list.get(3)); // 20
System.out.println(list.get(5)); // 30
System.out.println(list.remove(0)); // 1
System.out.println(list.remove(1)); // 2
System.out.println(list.remove(2)); // 3
System.out.println(list); // [10, 20, 30]
list.set(0,1);
list.set(1,2);
list.set(2,3);
System.out.println(list); // [1, 2, 3]
}
}
2. ArrayList集合
java.util.ArrayList集合数据存储的结构是数组结构。元素增删慢，查找快。
3. LinkedList集合
java.util.LinkedList集合 implements List接口- 特点：
- 底层是一个链表的结构：查询慢，增删快。
- 里边包含了大量操作首尾元素的方法。
- 注意：使用
LinkedList集合特有的方法，不能使用多态。 - 方法：
public void addFirst(E e)将指定的元素插入此列表的开头public void addLast(E e)将指定的元素插入此列表的末尾public void push(E e)将元素推入此列表所表示的堆栈（addFirst）public E getFirst()返回此列表的第一个元素public E getLast()返回此列表的最后一个元素public E removeFirst()删除并返回此列表的第一个元素public E removeLast()删除并返回此列表的最后一个元素public E pop()从此列表所表示的堆栈处弹出一个元素 （removeFirst）public boolean isEmpty()判断列表是否为空
import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
System.out.println(linkedList); // [1, 2, 3]
linkedList.addFirst(0);
linkedList.addLast(4);
linkedList.push(-1);
System.out.println(linkedList); // [-1, 0, 1, 2, 3, 4]
System.out.println(linkedList.getFirst()); // -1
System.out.println(linkedList.getLast()); // 4
System.out.println(linkedList.removeFirst()); // -1
System.out.println(linkedList.removeLast()); // 4
System.out.println(linkedList.pop()); // 0
System.out.println(linkedList); // [1, 2, 3]
System.out.println(linkedList.isEmpty()); // false
linkedList.clear();
System.out.println(linkedList.isEmpty()); // true
}
}
4. Vector集合
- 底层也是数组，是单线程的。
三、Set接口
1. Set接口的介绍
java.util.Set接口 extends Collection接口- 特点：
- 不允许存储重复的元素
- 没有索引，没有带索引的方法，也不能使用普通的
for循环遍历。
2. HashSet集合介绍
java.util.HashSet集合 implements Set接口- 特点：
- 不允许存储重复的元素
- 没有索引，没有带索引的方法，也不能使用普通的
for循环遍历。 - 是一个无序集合，存储元素和取出元素的顺序有可能不一致。
- 底层是一个哈希表结构（查询速度快）。
import java.util.HashSet;
import java.util.Set;
public class Test {
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(3);
set.add(2);
set.add(1);
System.out.println(set); // [1, 2, 3]
}
}
3. 哈希值
-
哈希值：是一个十进制的整数，由系统随机给出（就是对象的地址值，是一个逻辑地址，是模拟出来得到的地址，不是数据实际存储的物理地址）。
-
在
Object类中有一个方法获取对象的哈希值：int hashCode()返回对象的哈希码值。 -
hashCode()方法的源码：public native int hashCode();native代表该方法调用的是本地操作系统的方法。
-
String类重写了该方法。
public class Test {
public static void main(String[] args) {
Person person1 = new Person();
int h1 = person1.hashCode();
System.out.println(h1); // 2001049719
Person person2 = new Person();
int h2 = person2.hashCode();
System.out.println(h2); // 1528902577
}
}
4. HashSet集合存储数据的结构（哈希表）
JDK1.8之前：哈希表 = 数组 + 链表。JDK1.8之后：- 哈希表 = 数组 + 链表；
- 哈希表 = 数组 + 红黑树。
- 若链表长度超过了8位，那么就会把链表转换为红黑树（提高查询速度）。
- 数组结构：将元素进行了分组（相同哈希值的元素是一组）。
- 链表/红黑树结构：将相同哈希值的元素链接到一起。
5. Set集合存储不重复元素的原理
Set集合在调用add方法的时候，add方法会调用元素的hashCode方法和equals方法，判断元素是否重复。Set集合存储不重复的元素的前提：存储的元素必须重写hashCode方法和equlas方法。
6. HashCode集合存储自定义类型元素
import java.util.Objects;
public class Person {
private String name;
private int age;
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
public Person() {
}
public Person(String name, int age) {
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;
}
}
import java.util.HashSet;
public class TestHashCode {
public static void main(String[] args) {
HashSet<Person> hashSet = new HashSet<>();
Person person01 = new Person("朱古力", 18);
Person person02 = new Person("朱古力", 18);
Person person03 = new Person("猪猪侠", 20);
hashSet.add(person01);
hashSet.add(person02);
hashSet.add(person03);
System.out.println(hashSet); // [Person{name='朱古力', age=18}, Person{name='猪猪侠', age=20}]
}
}
7. LinkedHashSet集合
Java.util.LinkedHashSet集合 extends 、HashSet集合- 特点：
- 底层是一个哈希表(数组+链表/红黑树) + 链表。
- 多出的一条链表用于记录元素的存储顺序，保证元素有序。
import java.util.HashSet;
import java.util.LinkedHashSet;
public class Test {
public static void main(String[] args) {
HashSet<String> hashSet = new HashSet<>();
hashSet.add("zhu");
hashSet.add("gu");
hashSet.add("li");
System.out.println(hashSet); // [zhu, li, gu] 无序
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("zhu");
linkedHashSet.add("gu");
linkedHashSet.add("li");
System.out.println(linkedHashSet); // [zhu, gu, li] 有序
}
}
四、可变参数
JDK1.5之后出现的新特性。- 前提：当方法的参数列表数据类型已经确定，但参数的个数不确定，就可以使用可变参数。
- 格式：
修饰符 返回值类型 方法名(数据类型...变量名){} - 可变参数的原理：可变参数的底层就是一个数组，根据传递参数个数不同，会创建不同长度的数组来存储这些参数。
- 传递的参数个数，可以是0个、1个、2个…多个。
- 注意事项：
- 一个方法的参数列表，只能有一个可变参数。
- 如果方法的参数有多个，那么可变参数必须写到参数列表的末尾。
public class Test {
public static void main(String[] args) {
int rs1 = add(10);
System.out.println(rs1); // 10
int rs2 = add(10,20);
System.out.println(rs2); // 30
int rs3 = add(10,20,30);
System.out.println(rs3); // 60
}
public static int add(int...arr) {
int rs = 0;
for (int temp : arr) {
rs += temp;
}
return rs;
}
}
五、Collections
java.util.Collections是集合工具类，用来对集合进行操作。
-
public static <T> boolean addAll(Collection<T> c, T...elements)往集合中添加一些元素。import java.util.ArrayList; import java.util.Collections; public class Test01 { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); Collections.addAll(list,1,2,3,4,5,6,7,8,9,0); System.out.println(list); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] } } -
public static void shuffle(List<?> list)打乱集合中元素的顺序。import java.util.ArrayList; import java.util.Collections; public class Test02 { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); Collections.addAll(list,1,2,3,4,5); System.out.println(list); // [1, 2, 3, 4, 5] Collections.shuffle(list); System.out.println(list); // [2, 4, 5, 3, 1] } } -
public static <T> void sort(List<?> list)将集合中元素按照默认升序的的规则排序。import java.util.ArrayList; import java.util.Collections; public class Test03 { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); Collections.addAll(list,1,5,3,7,2); System.out.println(list); // [1, 5, 3, 7, 2] Collections.sort(list); System.out.println(list); // [1, 2, 3, 5, 7] } }-
自定义类型使用
sort注意：- 被排序的集合里边的存储的元素，必须实现
Comparable接口，重写接口中的方法compareTo。 compareTo返回值：- 若为调用者
(this)减去 参数，则为升序；反之，为降序。
- 若为调用者
//实现Comparable接口 public class Person implements Comparable{ private String name; private int age; //覆盖重写compareTo方法 @Override public int compareTo(Object o) { Person p = (Person) o; return this.getAge() - p.getAge(); } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", age=" + age + '}'; } public Person() { } public Person(String name, int age) { 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; } } import java.util.ArrayList; import java.util.Collections; public class Test04 { public static void main(String[] args) { ArrayList<Person> people= new ArrayList<>(); Person person01 = new Person("朱古力",18); Person person02 = new Person("猪猪猪",22); Person person03 = new Person("猪猪侠",20); Collections.addAll(people,person01,person02,person03); System.out.println(people); // [Person{name='朱古力', age=18}, // Person{name='猪猪猪', age=22}, // Person{name='猪猪侠', age=20}] Collections.sort(people); System.out.println(people); // [Person{name='朱古力', age=18}, // Person{name='猪猪侠', age=20}, // Person{name='猪猪猪', age=22}] } } - 被排序的集合里边的存储的元素，必须实现
-
-
public static <T> void sort(List<T> list, Comparator<? super T>)将集合中元素按照指定规则排序。Comparator和Comparable的区别：Comparable：this与参数比较，自定义类需要实现Comparable接口，覆盖重写比较规则CompareTo方法。Comparator：相当于找一个第三方裁判进行比较。
public class Person /*implements Comparable*/{ private String name; private int age; @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", age=" + age + '}'; } public Person() { } public Person(String name, int age) { 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; } } import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class Test05 { public static void main(String[] args) { ArrayList<Person> people= new ArrayList<>(); Person person01 = new Person("朱古力",18); Person person02 = new Person("猪猪猪",22); Person person03 = new Person("猪猪侠",20); Collections.addAll(people,person01,person02,person03); System.out.println(people); // [Person{name='朱古力', age=18}, // Person{name='猪猪猪', age=22}, // Person{name='猪猪侠', age=20}] Collections.sort(people, new Comparator<Person>() { @Override public int compare(Person o1, Person o2) { return o1.getAge() - o2.getAge(); } }); System.out.println(people); // [Person{name='朱古力', age=18}, // Person{name='猪猪侠', age=20}, // Person{name='猪猪猪', age=22}] } }
转载：https://blog.csdn.net/weixin_44781238/article/details/106128495
查看评论