13_集合框架
一 集合概述
1.1 什么是集合 Collections
集合Collection,也是一个数据容器,类似于数组,但是和数组是不一样的。集合是一个可变的容器,可以随时向集合中添加元素,也可以随时从集合中删除元素。另外,集合还提供了若干个用来操作集合中数据的方法。
集合里的数据,我们称之为元素(elements);集合只能用来存储引用类型的数据,不能存储八大基本数据类型的数据。
1.2 引入泛型
Java SE 5.0以前,集合的元素只要是Object类型就行,那个时候任何对象都可以存放在集合内,但是从集合中获取对象后,需要进行正确的强制类型转换。但是,Java SE 5.0 以后,可以使用新特性”泛型”,用来指定要存放在集合中的对象类型。避免了强制转换的麻烦。
public static void main(String[] args){ArrayList list = new ArrayList();list.add(new Person());list.add(5);list.add("helloworld");Object obj = list.get(0);Person p = (Person)obj;String name = p.getName();System.out.println("name:"+name);
}
1.3 集合与数组
- 数组是定长的容器,一旦实例化完成,长度不能改变。集合是变长的,可以随时的进行增删操作。
- 数组中可以存储基本数据类型和引用数据类型的元素,集合中只能存储引用数据类型的元素。
- 数组的操作比较单一,只能通过下标进行访问。集合中提供了若干个方便对元素进行操作的方法。
小贴士: 在存储引用类型时,集合与数组,存储的其实都是对象的地址。
1.4 集合框架体系图
二 父接口Collection
2.1 简介
Collection 接口是 List、Set 和 Queue 接口的父接口,该接口里定义了他们三个子接口的共同方法。既可用于操作 Set 集合,也可用于操作 List 和 Queue 集合。作为父接口,其子类集合的对象,存储元素的特点,可能是无序的,也可能是有序的,因此在父接口中并没有定义通过下标获取元素的方法功能。
2.2 常用方法
2.3 集合的迭代
在进行集合的遍历的时候,方式其实很多。但是,基本上所有的遍历,都与 Iterable 接口有关。这个接 口提供了对集合进行迭代的方法。只有实现了这个接口,才可以使用增强for循环进行遍历。
1)增强for循环
for (String ele : collection) {System.out.println(ele);
}
注意事项:
- 增强for循环中不允许对集合中的元素进行修改,修改是无效的
- 增强for循环中不允许对集合的长度进行修改,否则会出现 ConcurrentModificationException
2)迭代器
迭代器Iterator,是一个接口, Collection集合中有一个方法 iterator() 可以获取这个接口的实现类 对象。在这个迭代器中,维护了一个引用,指向集合中的某一个元素。默认指向一个集合前不存在的元 素,可以认为是下标为-1的元素。
迭代器的工作原理:循环调用 next() 方法进行向后的元素指向,并返回新的指向的元素。同时,在向 后进行遍历的过程中,使用 hasNext() 判断是否还有下一个元素可以迭代。
在迭代器使用的过程中,需要注意:
- 不应该对集合中的元素进行修改
- 不应该对集合的长度进行修改
- 如果非要修改,需要使用迭代器的方法,不能使用的集合的方法。
// 1、获取迭代器对象,这里的 iterator 是一个 Iterator 接口的实现类对象
Iterator<String> iterator = collection.iterator();// 2、使用迭代器进行集合的遍历
while (iterator.hasNext()) {// 让迭代器向后指向一位,并返回这一位的元素String element = iterator.next();System.out.println(element);
}
三 子接口List
3.1 简介
- List 是一个元素有序、且可重复的集合,集合中的每个元素都有其对应的顺序索引,从0开始
- List 允许使用重复元素,可以通过索引来访问指定位置的集合元素。
- List 默认按元素的添加顺序设置元素的索引。
- List 集合里添加了一些根据索引来操作集合元素的方法
3.2 ArrayList和LinkedList
这两个类都是List接口的实现类(子类)。两者在实现上的底层原理对比
- ArrayList是实现了基于动态数组的数据结构,对象存储在连续的位置上
- LinkedList基于双链表的数据结构,链表中的每个节点都包含了前一个和后一个节点的引用。
- 对于随机访问get和set,ArrayList绝对优于LinkedList,因为LinkedList要移动指针。
- 对于插入和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。
PS:当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比,如果数据和运算量很小,那么对比将失去意义
Vector:是一个古老的集合, JDK1.0版本时候出现,现在已经被ArrayList和LinkedList替代。
Stack:是一个古老的集合, JDK1.0版本时候出现,模拟栈结构存储数据。
3.3 常用方法
ArrayList和LinkedList两个实现类的常用方法基本相同,会一个的话,另一个就会了。
1)添加元素
- boolean add(E e)
作用:向列表末尾添加指定的元素
- void add(int index, E element)
作用:在列表的指定位置添加元素
- boolean addAll(Collection c)
作用:将集合c中的所有元素添加到列表的结尾
- boolean addAll(int index, Collection c)
作用::将集合c中的所有元素添加到列表的指定位置
2)获取元素
- E get(int index)
作用:返回列表指定位置的元素
3)查找元素
- int indexOf(Object obj)
作用:返回列表中指定元素第一次出现的位置,如果没有该元素,返回-1
- int lastIndexOf(Object obj)
作用:返回列表中指定元素最后一次出现的位置,如果没有该元素,返回-1
4)移除元素
- E remove(int index)
作用:移除集合中指定位置的元素,返回被移除掉的元素对象
5)修改元素
- E set(int index, E element)
作用:用指定元素替换指定位置上的元素,返回被替换出来的元素对象
6)截取子集
- List subList(int fromIndex, int toIndex)
作用:截取子集,返回集合中指定的fromIndex 到 toIndex之间部分视图,包前不包后
3.4 ListIterator
ListIterator是Iterator接口的子接口,继承到了Iterator中所有的方法,同时自己也添加了若干个方法。 允许使用ListIterator在进行元素迭代的时候,对集合中的数据进行修改,或者对集合的长度进行修改。 同时,使用ListIterator还可以进行倒序的迭代。
注意事项:
在进行迭代的过程中,允许修改集合。但是要注意,这个修改集合,只能通过子接口中的方法进行,并不能够通过集合中的方法进行修改。
// 3、在迭代的过程中,修改集合
while (iterator.hasNext()) {// 向后指向一位,并返回当前指向的元素String ele = iterator.next();if (ele.equals("Vertu")) {// 在迭代的过程中,删除这个元素iterator.remove();// 在迭代的过程中,添加一个元素(加在当前迭代的这个元素的后面)iterator.add("HTC");// 在迭代的过程中,对当前迭代的元素进行修改iterator.set("Nokia");}
}
四 子接口Queue
4.1 简介
-
队列Queue也是Collection的一个子接口,它也是常用的数据结构,可以将队列看成特殊的线性表,队列限制对线性表的访问方式:只能从一端添加(offer)元素,从另一端取出(poll)元素。
-
队列遵循先进先出(FIFO first Input First Output)的原则
-
实现类LinkedList也实现了该接口,选择此类实现Queue的原因在于Queue经常要进行添加和删除操作,而LinkedList在这方面效率比较高。
-
其主要方法如下:
方法 解析 boolean offer(E e) 作用:将一个对象添加到队尾,如果添加成功返回true E poll() 作用:从队首删除并返回这个元素 E peek() 作用:查看队首的元素
public void testQueue(){Queue<String> queue = new LinkedList<>();queue.offer("a");queue.offer("b");queue.offer("c");System.out.println(queue); // [a,b,c]String str = queue.peek();System.out.println(str); // awhile(queue.size() > 0){str = queue.poll();System.out.println(str+" "); // a b c}}
4.2 Deque
Deque是Queue的子接口,定义了所谓的”双端队列”,即从队列的两端分别可以入队(offer)和出队(poll)。同样,LinkedList实现了该接口
如果将Deque限制为只能一端入队和出队,则可以实现“栈”(Stack)的数据结构,对于栈而言,入栈被称为push,出栈被称为pop。遵循先进后(FILO)出原则
public void testDeque(){Deque<String> stack = new LinkedList<>();stack.push("a");stack.push("b");stack.push("c");System.out.println(push); // [c,b,a]String str = queue.peek();System.out.println(str); // cwhile(stack.size() > 0){str = stack.pop();System.out.println(str+" "); // c b a}
}
五 子接口Set
5.1 简介
- Set集合中的元素是无序的(取出或者打印的顺序与存入的顺序无关)
- Set集合中的元素不能重复
即不能把同一个东西或者相似的东西两次添加到同一个Set容器中,每次放入时都会进行判断是否存在,如果存在,就不添加。如果能放入,与我们的设计初衷相违背了。
5.2 实现类
1)HashSet
HashSet 是 Set 接口的典型实现,大多数时候使用 Set 集合时都使用这个实现类。
HashSet 按 Hash 算法来存储集合中的元素,因此具有很好的存取和查找性能。
HashSet 具有以下特点:
- 不能保证元素的排列顺序
- HashSet 不是线程安全的
- 集合元素可以是 null
当向 HashSet 集合中存入一个元素时,HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值,然后根据 hashCode 值决定该对象在 HashSet 中的存储位置。
如果两个元素的 equals() 方法返回 true,但它们的 hashCode() 返回值不相等,hashSet 将会把它们存储在不同的位置,但依然可以添加成功。
2)LinkedHashSet
- LinkedHashSet 是 HashSet 的子类
- LinkedHashSet 集合根据元素的 hashCode 值来决定元素的存储位置,但它同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
- LinkedHashSet 性能插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能。
- LinkedHashSet 不允许集合元素重复。
3)TreeSet
TreeSet 是 SortedSet 接口的实现类, TreeSet集合是用来对元素进行排序的,同样他也可以保证元素的唯一。TreeSet 可以确保集合元素处于排序状态。
TreeSet 支持两种排序方法:自然排序和定制排序。默认情况下,TreeSet 采用自然排序。
5.3 常用方法
Set接口中没有新增的方法,所有的方法都是从父接口 Collection 中继承到的。
5.4 Set的去重原理
1)HashSet 、LinkedHashSet
2)TreeSet
如果元素的比较规则中,两个对象的比较结果是0,则视为是同一个元素,去重。
六 List排序
6.1 Comparable接口
如果集合里的元素想要排序,那么元素对象之间一定要有大小之分。这个大小之分是如何界定的呢??
此时,元素类型必须是Comparable接口的实现类,该接口提供了方法
- int compareTo(T t) 。规范了其子类是可以比较的,因此子类必须重写此抽象方法。
比较规则:(默认升序)
- 如当前对象大于给定对象,那么返回值应为>0的整数 -(this-o)
- 若小于给定对象,那么返回值应为<0的整数
- 若两个对象相等,则应返回0
6.2 工具类提供的排序方法
Collections是集合的工具类,提供了很多便于我们操作集合的方法,其中就有用于集合排序的sort方法。
- static void sort(List list)
作用是对指定的集合元素进行自然排序。前提元素类型必须实现Comparable接口
6.3 Comparator比较器接口
java类一旦定义好,就不要轻易再去修改它。因此当java类实现了Comparable接口,也就代表比较规则已经确定.
但是,有的时候我们想临时改变一下比较规则,怎么办呢?
此时我们可以采用Comparator接口回调的方式。它提供了一个抽象方法:
- int compare(T o1 , T o2)
比较规则如下
- 若o1>o2, 则返回值应该>0
- 若o1<o2,则返回值应该<0
- 若o1==o2, 则返回值应该为0
工具类中提供了sort方法的重载方法
- static void sort(List list , Comparator c)
作用:使用比较器c,指定临时排序规则
6.4 Collections
Collections 是一个操作 Set、List 和 Map 等集合的工具类,提供了大量方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
1)排序操作
- reverse(List):反转 List 中元素的顺序
- shuffle(List):对 List 集合元素进行随机排序
- sort(List):根据元素的自然顺序对指定 List 集合元素按升序排序
- sort(List,Comparator):根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
- swap(List,int, int):将指定 list 集合中的 i 处元素和 j 处元素进行交换
2)查找、替换
- Object max(Collection):根据元素的自然顺序,返回给定集合中的最大元素
- Object max(Collection,Comparator):根据 Comparator 指定的顺序,返回给定集合中的最大元素
- Object min(Collection)
- Object min(Collection,Comparator)
- int frequency(Collection,Object):返回指定集合中指定元素的出现次数
- boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换 List 对象的所有旧值
七 父接口Map
7.1 Map简介
Map是集合框架中的另一个父接口,它用来保存具有映射(一对一)关系的数据,这样的数据称之为键值对(Key-Value-Pair)。key可以看成是value的索引。特点如下:
- key和value必须是引用类型的数据
- 作为key,在Map集合中不允许重复,Value可以重复
- key可以为null
- key和value之间存在单向一对一关系,通过指定的key总能找到唯一,确定的value
根据内部数据结构的不同,Map接口有多种实现类,其中常用的有内部为hash表实现的
HashMap和内部为排序二叉树实现的TreeMap
7.2 常用方法
7.3 Map的遍历
Map提供了三种遍历方式
- 遍历所有的key
- Set keySet();
- 该方法会将当前Map中的所有key存入一个Set集合后返回
- 遍历所有的key-value
- Set<Entry<K,V>> entrySet()
- 该方法会将当前Map中的每一组key-value封装成Entry对象存入Set集合后返回
- 遍历所有的value(不常用)
- Collection values
7.4 HashMap的实现原理
1)原理
HashMap的底层主要是基于数组和链表来实现的,它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象对多了,就有可能不同的对象所算出来的hash值是相同的,这就出现了所谓的hash冲突
图中,紫色部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中
2)装载因子及其HashMap优化
capacity:容量,hash表里bucket(桶)的数量,也就是散列数组大小
initial capacity:初始容量,创建hash表时,初始bucket的数量,默认构建容量为16,也可以使用特定容量。
size:大小,当前散列表中存储数据的数量
load factor:加载因子,默认值0.75也就是75%,当向散列表增加数据时,如果size/capacity的值大于loadfactor,则发生扩容并且重新散列(rebash)
性能优化:加载因子较小时,散列查找性能会提高,但是也浪费了散列桶空间容量。0.75是性能和空间相对平衡结果。在创建散列表时指定合理容量,减少rehash能提供性能
7.5HashMap与HashTable
HashMap 和 Hashtable 是 Map 接口的两个典型实现类
区别:
- Hashtable 是一个古老的 Map 实现类,不建议使用
- Hashtable 是一个线程安全的 Map 实现,但 HashMap 是线程不安全的。
- Hashtable 不允许使用 null 作为 key 和 value,而 HashMap 可以
与 HashSet 集合不能保证元素的顺序的顺序一样,Hashtable 、HashMap 也不能保证其中 key-value 对的顺序
7.6 LinkedHashMap
LinkedHashMap 是 HashMap 的子类
LinkedHashMap 可以维护 Map 的迭代顺序:迭代顺序与 Key-Value 对的插入顺序一致
7.7 TreeMap
TreeMap 存储 Key-Value对时,需要根据 Key 对 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。
注意:TreeMap里的key,是使用comparaTo来确定是否唯一的,而不是调用HashCode和equals的
TreeMap 的 Key 的排序:
- 自然排序:TreeMap 的所有的 Key 必须实现 Comparable 接口,而且所有的 Key 应该是同一个类的对象,否则将会抛出 ClassCastException
- 定制排序:创建 TreeMap 时,传入一个 Comparator 对象,该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口
7.8 Properties
Properties 类是 Hashtable 的子类,该对象用于处理属性文件
由于属性文件里的 key、value 都是字符串类型,所以 properties 里的 Key 和 Value 都是字符串类型的
八 练习题
1、设计一个方法,随机生成10个不重复的10以内的数字,存入一个List集合。
//1、设计一个方法,随机生成10个不重复的10以内的数字,存入一个List集合。public List<Integer> makeNumber(int length){List<Integer> list =new ArrayList<>();for (int i = 0; i < length; i++) {int number = (int)(Math.random()*length);if(!list.contains(number)){list.add(number);}else{i--;}}return list;}
2、设计一个方法,删除一个集合中,所有的指定的元素。例如,将集合中所有的3都删除。
//2、设计一个方法,删除一个集合中,所有的指定的元素。例如,将集合中所有的3都删除。public <T> List<T> deleteElement(List<T> list,T t){for (Iterator<T> it = list.listIterator();it.hasNext();){if(Objects.equals(it.next(),t)){it.remove();}}return list;}
3、设计一个方法,将一个存储有体重信息的集合,所有的数据乘2
//3、设计一个方法,将一个存储有体重信息的集合,所有的数据乘2public void doubleWeight(List<Number> list){ListIterator<Number> it = list.listIterator();while(it.hasNext()){it.set(it.next().doubleValue()*2);}}
4、设计一个方法,在一个存储了若干个视频的集合中,删除所有的以.mp4结尾的元素。
//4、设计一个方法,在一个存储了若干个视频的集合中,删除所有的以.mp4结尾的元素。public void deleteMp4(List<String> list) {ListIterator<String> it = list.listIterator();while (it.hasNext()) {String element = it.next();if (element.endsWith(".mp4")) {it.remove();}}}}
5、程序设计:图书管理器,设计一个图书管理器,实现对图书进行的存储管理操作,实现功能
-
添加一本图书(书名、作者(姓名,年龄,性别)、售价)
-
删除一本图书(通过书名删除)
-
删除所有的指定作者的书(通过作者姓名删除)
-
将所有的图书按照图书售价降序排序。若售价相同,按照作者年龄升序)
public void addBooK(List<Book> list, Book book) {ListIterator<Book> it = list.listIterator();boolean exists = false;while (it.hasNext()) {if (it.next().getBookName().equals(book.getBookName())) {exists = true;break;}}if (!exists) {it.add(book); // 在游标位置插入}}//删除一本图书(通过书名删除)public void deleteBook(List<Book> list, String bookName){ListIterator<Book> it = list.listIterator();while (it.hasNext()) {Book element = it.next();if (element.getBookName().equals(bookName)) {it.remove();}}}//删除所有的指定作者的书(通过作者姓名删除)public void deleteByName(List<Book> list, String name){ListIterator<Book> it = list.listIterator();while (it.hasNext()) {Book element = it.next();if (element.getAuthor().getName().equals(name)) {it.remove();}}}//将所有的图书按照图书售价降序排序。若售价相同,按照作者年龄升序)public void sortBook(List<Book> list){Collections.sort(list, new Comparator<Book>() {@Overridepublic int compare(Book o1, Book o2) {if(o1.getPrice()-o2.getPrice()==0){return o1.getAuthor().getAge() - o2.getAuthor().getAge();}else{return (int)(o2.getPrice()-o1.getPrice());}}});}
6、设计一个动物类Animal类,有编号,姓名,性别,年龄属性,将多个动物对象添加到一个HashSet集合中时,若所有的属性值都相同则是为相同对象;在主方法中创建三个Animal对象,添加到一个HashSet集合中,输出集合中元素的个数
Animal a1 = new Animal(10,"猴子1",'公',4);Animal a2 = new Animal(11,"猴子2",'母',6);Animal a3 = new Animal(12,"猴子3",'公',5);Animal a4 = new Animal(10,"猴子1",'公',4);Set<Animal> set = new HashSet<>();set.add(a1);set.add(a2);set.add(a3);set.add(a4);System.out.println(set.size());for(Animal a:set){System.out.println(a);//a1,a2,a3}
7、向TreeSet集合中加入5个员工的对象,根据员工的年龄(升序)进行排序,若年龄相同,再根据工龄(降序)来排序,若工龄相同,根据薪水(降序)排序(用两种方式实现)
public class Employee implements Comparable<Employee> {//.......
@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Employee employee = (Employee) o;return age == employee.age && Seniority == employee.Seniority && Double.compare(salary, employee.salary) == 0 && Objects.equals(name, employee.name);}@Overridepublic int hashCode() {return Objects.hash(name, age, Seniority, salary);}@Override //比较规则要考虑完善,不然规则可能判定相等,无法存入public int compareTo(Employee o) {int r = this.getAge() - o.getAge();if( r== 0){r = o.getSeniority()- this.Seniority;if(r == 0){r =(int)(o.getSalary() -this.getSalary());}}return r;}public static void main(String[] args) {Employee e1 = new Employee("赵一",23,2,9000);Employee e2 = new Employee("钱二",24,1,10000);Employee e3 = new Employee("孙三",20,2,8000);Employee e4 = new Employee("李小四",20,1,6000);Employee e5 = new Employee("王大五",23,2,10000);//注意创建TreeSet对象时要实现Comparable接口//集合里添加元素的去重规则实际上调用的是 compareTo 方法,并不是HashCode 方法 和 equals方法Set<Employee> emp = new TreeSet<>(); emp.addAll(Arrays.asList(e1,e2,e3,e4,e5));for (Employee e: emp){System.out.println(e);}System.out.println("===============");//使用比较器Comparator对象来进行自定义排序Comparator c1 = new Comparator<Employee>() {@Overridepublic int compare(Employee o1, Employee o2) {int r = o1.getAge() - o2.getAge();if( r== 0){r = o2.getSeniority()- o1.Seniority;if(r == 0){r =(int)(o2.getSalary() -o1.getSalary());}}return r;}};Set<Employee> emp1 = new TreeSet<>(c1);emp1.addAll(Arrays.asList(e1,e2,e3,e4,e5));for (Employee e: emp1){System.out.println(e);}}
}
8、随机产生10个不重复的1-30之间的随机数保存到
List集合中,对数组进行降序排列,将排列后的数组存放到集合ArrayList中。将集合中大于10的输出并统计数量。
public static void main(String[] args) {int count =0;//set集合不能排序,要排序用他的子接口或者转成其他类型// Set<Integer> set = new HashSet<>();
// while(set.size()<=10){
// int number = (int)(Math.random()*30)+1;
// set.add(number);
// }
// System.out.println(set);List<Integer> list = new ArrayList<>();while(list.size()<10){int number = (int)(Math.random()*30)+1;if(list.contains(number) ==false){list.add(number);}}System.out.println(list);list.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}});System.out.println(list);for(Integer i:list){if(i>10){System.out.print(i+" ");count++;}}System.out.println();System.out.println("大于10的个数为:"+count);}
}
9、从控制台输入一串字符串,统计这个字符串中每一个字符出现的次数,并整理成新的字符串输出。
输入: abccaabdsswaabbsc
输出:a(5)b(4)c(3)d(1)s(3)w(1)
public static void main(String[] args) {//String text = "abccaabdsswaabbsc";String text = "abccaabdsswaabbsrtgwsertgwsetgwestgeuu464363sc";String a = "";Map<String,Integer> map = new HashMap<>();//字符串变成字符串数组String[] str =text.split("");List<String> list = Arrays.asList(str);for(String s:list){map.put(s,map.getOrDefault(s,0)+1);}Set<String> key = map.keySet();for(String s:key){a+= s+"("+map.get(s)+")";}System.out.println(a);//}