Day 9
集合类
集合的概念
-
当我们需要保存一组一样（类型相同）的元素的时候，我们应该使用一个容器
来存储，数组就是这样一个容器 -
数组的缺点： 数组一旦定义，长度将不能再变化
-
在开发的过程中，需要使用能够动态增长长度的容器来保存数据，而且我们需要对数据的保存的逻辑可能各种各样，于是就有了各种各样的数据结构。Java中对于各种数据结构的实现，就是我们用到的集合
集合与数组的区别
长度区别 : 集合长度可变，数组长度不可变
内容区别 : 集合可以存储不同类型的元素，数组只能存储单一类型的元素
元素区别 : 集合只能存储引用类型元素，数组可存储引用类型，也可存储基本类型
集合体系概述
Java的集合框架是由很多接口、抽象类、具体类组成的，都位于java.util包中
Java集合要从两大接口说起，一为Collection接口，二为Map接口，它们是同一个层次的。
Collection接口
-
Collection 接口－定义了存取一组对象的方法，其子接口Set和List分别定义了存储方式
● Set 中的数据对象没有顺序且不可以重复。
● List 中的数据对象有顺序且可以重复。 -
Collection 接口下定义的通用方法：
-
add(E e)添加元素; clear()清空元素; remove(E e)移除元素; size()元素数量;
toArray()集合转数组; contains(E e)判断元素是否存在; isEmpty()判断集合是否为空;
-
List
List继承了Collection接口,有三个实现的类
－ ArrayList
数组列表，数据采用数组方式存储。
－LinkedList
链表
－Vector
数组列表，添加同步锁,线程安全
-
ArrayList实现类
-
数据结构：数组；
-
特点：查询快，增删慢，主要用于查询遍历数据，为最常用集合之一；
-
数组结构是有序的元素序列，在内存中开辟一段连续的空间，在空间中存放元素，每个空间都有编号，通过编号可以快速找到相应元素，因此查询快；数组初始化时长度是固定的，要想增删元素，必须创建一个新数组，把源数组的元素复制进来，随后源数组销毁，耗时长，因此增删慢。
ArrayList方法代码演示
public static void main(String[] args){ Collection<String> s= new ArrayList<String>(); //在<> 中传入了参数"String" 则以后传入的全都是String类型 //s.add(1); 非String类型 报错 s.add("1"); s.add("2"); s.add("abc"); Object []objs1 = s.toArray(); //第二个括号里面不加参数指定转换的类型会自动上升为object类型 System.out.println(Arrays.toString(objs1));//object类型的数组 String []objs2 = s.toArray(new String[c.size()-1]);//加入参数String 转换为String类型数组 System.out.println(Arrays.toString(objs2)); /* 集合的方法 */ // s.clear();//清除所有元素 // System.out.println(s); s.remove("abc");//清除指定位置的指定元素 System.out.println(s.remove("1"));//会有返回值，true 表示成功清除，false 表示没有找到该元素 System.out.println(s.contains(1));//判断是否包含该元素 System.out.println(s.contains("2")); System.out.println(s.isEmpty());//判空 如果为空则返回true; System.out.println(s.size());//返回长度 } System.out.println(c.containsAll(c1));//判断c中是否完全包含c1 c.retainAll(c1); //只保留c中与c1相交部分 System.out.println(c); -
Linklisted实现类
-
数据结构：链表；
-
特点：查询慢，增删快；
-
链表分为单向和双向，就是一条链子和两条链子的区别；多出的那条链子记录了元素的顺序，因此单向链表结构无序，双向链表结构有序；链表结构没有索引，因此查询慢；链表的增删只需在原有的基础上连上链子或切断链子，因此增删快。
-
特有方法：getFirst() 返回开头元素； getLast() 返回结尾元素；pop() 从所在堆栈中获取一个元素； push(E e) 将元素推入所在堆栈；
addFirst(E e) 添加元素到开头，头插； addLast(E e) 添加元素到结尾，尾插；
LinkedListed方法代码演示
public static void main(String[] args) { LinkedList<String> llk = new LinkedList<String>(); //链表和线性表的差别 ： 线性表遍历较为方便但是从在中间插入删除比较麻烦，需要将其 // 中的元素往后面或者前面依次移动， //链表插入比较简单，链表具有数据域一个头指针和一个尾指针，尾指针指向下一个头指针，数据域用来存储数据信息。 //所以在中间插入只需要更改头指针和尾指针的地址即可，而如果遍历的话（llk.get())会判断传入的 // 索引和size/2进行比较，如果小于则从头开始遍，如果大于则从后向前遍历。 llk.add("1"); llk.add("2"); llk.add("3"); llk.add("1"); llk.add("2"); llk.add("3"); llk.add("1"); llk.add("2"); llk.add("3"); llk.add("1"); llk.add("2"); llk.add("3"); llk.add("1"); llk.add("2"); llk.add("3"); System.out.println(llk); System.out.println(llk.get(14)); System.out.println(llk.get(7)); System.out.println(llk.getFirst()); System.out.println(llk.getLast()); System.out.println(llk.remove(10)); System.out.println(llk); } -
Vector实现类
-
数据结构：数组；
特点：查询快，增删慢
和ArrayList一样，都是数组实现，因此具有相似的特性，它们之间的区别在于Vector是线程安全的，效率低，ArrayList是线程不安全的，但效率高。
Set接口
-
Set接口继承了collection接口，有两个实现类
－ Hashset -
HashSet类中的元素不能重复，即彼此调用equals方法比较，都返回false
-
底层数据结构是哈希表+链表哈希表依赖于哈希值存储
－TreeSet
-
可以给Set集合中的元素进行指定方式的排序。存储的对象必须实现Comparable接口
-
TreeSet底层数据结构是二叉树(红黑树是一种自平衡的二叉树)
-
Hashset实现类
数据结构：哈希表（数组+单向链表+红黑树），当链表长度超过阈值（8）时，链表将转换为红黑树。
特点：查询快，元素无序，元素不可重复，没有索引；
哈希表底层用数组+单向链表实现，即使用链表处理冲突，同一Hash值的元素都存储在一个链表里，但是当位于一个链表中的元素较多，即Hash值相等的元素较多，通过key值依次查找的效率降低。JDK1.8之后，哈希表底层采用数据+单向链表+红黑树实现，当链表长度超过阈值（8）时，链表将转换为红黑树，极大缩短查询时间。
哈希值是一个十进制的整数，是对象的地址值，是一个逻辑地址，不是实际存储的物理地址，由系统随机给出。Object类的int hashCode()方法，可以获取对象的哈希值。
HashSet方法代码演示
import java.util.HashSet; import java.util.Iterator; public class hash_demo { @Override public String toString() { return super.toString(); } public static void main(String[] args) { HashSet<String> hs = new HashSet<String>(); hs.add("123"); hs.add("123"); hs.add("df"); hs.add("d"); System.out.println(hs); // hs.clear(); 清除哈希表中的所有元素 hs.isEmpty();//判空 hs.size();//得到哈希表长度 // hs.remove(Object obj); 删除Set集合中的元素，删除成功返回true，否则返回false // hs.contains(Object o);判断是否包含某元素 // hs.iterator; 迭代器 Iterator<String> ite = hs.iterator(); while(ite.hasNext()) { System.out.println(ite.next()); } // HashSet<test_class> hs2 = new HashSet<test_class>(); // test_class t1 = new test_class("test",1); // test_class t2 = new test_class("test",2); // test_class t3 = new test_class("test",3); // test_class t4 = new test_class("test",4); // // hs2.add(t1); // hs2.add(t2); // hs2.add(t3); // hs2.add(t4); // System.out.println(hs2);//new 出来的对象的地址是不同的所以不重写方法就不能判断是否重复 } } -
TreeSet实现类
数据结构：红黑树
特点：查询快，元素有序，元素不可重复，没有索引；
底层分析：TreeSet实现了继承于Set接口的SortedSet接口 ，它支持两种排序方法，自然排序和定制排序，自然排序的意思就是放入元素“a”，“b”，a会自然地排在b前面，其中还有几个特有方法。
first() 返回第一个元素； last() 返回最后一个元素；comparator() 返回排序比较器；
TreeSet方法代码演示
import sun.reflect.generics.tree.Tree; import java.util.Comparator; import java.util.Iterator; import java.util.TreeSet; public class TreeSetDemo{ public static void main(String[] args) { TreeSet<Integer> ts = new TreeSet<>(); ts.add(-5); ts.add(2); ts.add(3); ts.add(1); ts.add(-8); ts.add(1); System.out.println(ts); // TreeSet 底层实现为自平衡二叉树(红黑树) 自动排序 // ts.clear(); 清除哈希表中的所有元素 ts.isEmpty();//判空 ts.size();//得到哈希表长度 // ts.remove(Object obj); 删除Set集合中的元素，删除成功返回true，否则返回false // ts.contains(Object o);判断是否包含某元素 // ts.iterator(); 迭代器 ts.iterator(); Iterator<Integer> ite= ts.iterator(); while(ite.hasNext()){ System.out.println(ite.next()); } // // Car car1 = new Car(10,"car1"); // Car car2 = new Car(8,"car2"); // Car car3 = new Car(0,"car3"); // Car car4 = new Car(-10,"car4"); // Car car5 = new Car(5,"car5"); // // TreeSet<Car> tset2 = new TreeSet<>(); // tset2.add(car1); // tset2.add(car2); // tset2.add(car3); // tset2.add(car4); // tset2.add(car5); // // Iterator<Car> ite= tset2.iterator(); // while(ite.hasNext()){ // System.out.println(ite.next()); // } } }