Collection集合概述 什么是集合 集合是一个大小可变的容器。 容器中的每个数据称为一个元素。数据==元素。 集合的特点是:类型可以不确定,大小不固定。集合有很多种,不同的集合特点和使用场景不同。
数组:类型和长度一旦定义出来就都固定了。
集合有啥用 在开发中,很多时候元素的个数是不确定的。 而且经常要进行元素的增删该查操作,集合都是非常合适的。 开发中集合用的更多!!
Java中集合的代表是:Collection. Collection集合是Java中集合的祖宗类。 学习Collection集合的功能,那么一切集合都可以用这些功能!!
Collection集合的体系:
Collection<E>(接口)
/ \
Set<E>(接口) List<E>(接口)
/ \ / \
HashSet<E>(实现类) TreeSet<>(实现类) ArrayList<E>(实现类) LinekdList<>(实现类)
/
LinkedHashSet<>(实现类)
集合的特点 Set系列集合:添加的元素是无序,不重复,无索引的。 – HashSet:添加的元素是无序,不重复,无索引的。 – LinkedHashSet:添加的元素是有序,不重复,无索引的。 – TreeSet:不重复,无索引,按照大小默认升序排序!! List系列集合:添加的元素是有序,可重复,有索引。 – ArrayList:添加的元素是有序,可重复,有索引。底层基于数组存储数据的,查询快,增删慢 – LinekdList:添加的元素是有序,可重复,有索引。底层是基于链表存储数据的,查询慢,增删快
小结: Collection是集合的祖宗类,Collection集合的功能是一切集合都可以直接使用的。
Collection集合的常用API Collection是集合的祖宗类,它的功能是全部集合都可以继承使用的,所以要学习它。 Collection API如下: public boolean add(E e): 把给定的对象添加到当前集合中 。 public void clear() :清空集合中所有的元素。 public boolean remove(E e): 把给定的对象在当前集合中删除。 public boolean contains(Object obj): 判断当前集合中是否包含给定的对象。 public boolean isEmpty(): 判断当前集合是否为空。 public int size(): 返回集合中元素的个数。 public Object[] toArray(): 把集合中的元素,存储到数组中
Collection集合的遍历方式 什么是遍历? 为什么开发中要遍历? 遍历就是一个一个的把容器中的元素访问一遍。 开发中经常要统计元素的总和,找最值,找出某个数据然后干掉等等业务都需要遍历。
Collection集合的遍历方式是全部集合都可以直接使用的,所以我们学习它。
Collection集合的遍历方式有三种:
(1)迭代器。
(2)foreach(增强for循环)。
(3)JDK 1.8开始之后的新技术Lambda表达式(了解)
a.迭代器遍历集合。
-- 方法:
public Iterator iterator(): 获取集合对应的迭代器,用来遍历集合中的元素的
E next():获取下一个元素值!
boolean hasNext():判断是否有下一个元素,有返回true ,反之。
--流程:
1.先获取当前集合的迭代器
Iterator<String> it = lists.iterator();
2.定义一个while循环,问一次取一次。
通过it.hasNext()询问是否有下一个元素,有就通过
it.next()取出下一个元素。
1 2 3 4 5 6 7 8 9 10 b.foreach(增强for循环)遍历集合。 foreach是一种遍历形式,可以遍历集合或者数组。 foreach遍历集合实际上是迭代器遍历的简化写法。 foreach遍历的关键是记住格式: for(被遍历集合或者数组中元素的类型 变量名称 : 被遍历集合或者数组){ } 小结: foreach遍历集合或者数组很方便。 缺点:foreach遍历无法知道遍历到了哪个元素了,因为没有索引。
1 c.JDK 1.8开始之后的新技术Lambda表达式。
常见的数据结构种类 1 2 3 4 5 6 7 8 集合是基于数据结构做出来的,不同的集合底层会采用不同的数据结构。 不同的数据结构,功能和作用是不一样的。 什么是数据结构? 数据结构指的是数据以什么方式组织在一起。 不同的数据结构,增删查的性能是不一样的。 不同的集合底层会采用不同的数据结构,我们要知道集合的底层是基于哪种数据结构存储和操作数据的。 这样才能知道具体场景用哪种集合。
Java常见的数据结构有哪些 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 数据存储的常用结构有:栈、队列、数组、链表和红黑树 a.队列(queue) -- 先进先出,后进后出。 -- 场景:各种排队。叫号系统。 -- 有很多集合可以实现队列。 b.栈(stack) -- 后进先出,先进后出 -- 压栈 == 入栈 -- 弹栈 == 出栈 -- 场景:手枪的弹夹。 c.数组 -- 数组是内存中的连续存储区域。 -- 分成若干等分的小区域(每个区域大小是一样的) -- 元素存在索引 -- 特点:查询元素快(根据索引快速计算出元素的地址,然后立即去定位) 增删元素慢(创建新数组,迁移元素) d.链表 -- 元素不是内存中的连续区域存储。 -- 元素是游离存储的。每个元素会记录下个元素的地址。 -- 特点:查询元素慢 增删元素快(针对于首尾元素,速度极快,一般是双链表) e.红黑树 二叉树:binary tree 永远只有一个根节点,是每个结点不超过2个节点的树(tree) 。 查找二叉树,排序二叉树:小的左边,大的右边,但是可能树很高,性能变差。 为了做排序和搜索会进行左旋和右旋实现平衡查找二叉树,让树的高度差不大于1 红黑树(就是基于红黑规则实现了自平衡的排序二叉树): 树尽量的保证到了很矮小,但是又排好序了,性能最高的树。 红黑树的增删查改性能都好!!!
List集合 ArrayList集合 1 2 3 4 5 6 7 8 9 10 11 List集合继承了Collection集合的全部功能,同时因为List系列集合有索引, 因为List集合多了索引,所以多了很多按照索引操作元素的功能: ArrayList实现类集合底层基于数组存储数据的,查询快,增删慢! - public void add(int index, E element): 将指定的元素,添加到该集合中的指定位置上。 - public E get(int index):返回集合中指定位置的元素。 - public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。 - public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回更新前的元素值。 小结: List系列集合有序,可重复,有索引的。 ArrayList实现类集合底层基于数组存储数据的,查询快,增删慢!! 开发中ArrayList集合用的最多!!
List系列集合的遍历方式有:4种 1 2 3 4 5 6 7 List系列集合多了索引,所以多了一种按照索引遍历集合的for循环。 List遍历方式: (1)for循环。 (2)迭代器。 (3)foreach。 (4)JDK 1.8新技术。
LinkedList集合 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 LinkedList也是List的实现类:底层是基于链表的,增删比较快,查询慢!! LinkedList是支持双链表,定位前后的元素是非常快的,增删首尾的元素也是最快的 所以LinkedList除了拥有List集合的全部功能还多了很多操作首尾元素的特殊功能: - public void addFirst(E e):将指定元素插入此列表的开头。 - public void addLast(E e):将指定元素添加到此列表的结尾。 - public E getFirst():返回此列表的第一个元素。 - public E getLast():返回此列表的最后一个元素。 - public E removeFirst():移除并返回此列表的第一个元素。 - public E removeLast():移除并返回此列表的最后一个元素。 - public E pop():从此列表所表示的堆栈处弹出一个元素。 - public void push(E e):将元素推入此列表所表示的堆栈。 小结: LinkedList是支持双链表,定位前后的元素是非常快的,增删首尾的元素也是最快的。 所以提供了很多操作首尾元素的特殊API可以做栈和队列的实现。 如果查询多而增删少用ArrayList集合。(用的最多的) 如果查询少而增删首尾较多用LinkedList集合。
Set集合 HashSet集合 1 2 3 研究两个问题(面试热点): 1)Set集合添加的元素是不重复的,是如何去重复的? 2)Set集合元素无序的原因是什么?
Set系列集合元素去重复的流程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 集合和泛型都只能支持引用数据类型。 1.对于有值特性的,Set集合可以直接判断进行去重复。 2.对于引用数据类型的类对象,Set集合是按照如下流程进行是否重复的判断。 Set集合会让两两对象,先调用自己的hashCode()方法得到彼此的哈希值(所谓的内存地址) 然后比较两个对象的哈希值是否相同,如果不相同则直接认为两个对象不重复。 如果哈希值相同,会继续让两个对象进行equals比较内容是否相同,如果相同认为真的重复了 如果不相同认为不重复。 Set集合会先让对象调用hashCode()方法获取两个对象的哈希值比较 / \ false true / \ 不重复 继续让两个对象进行equals比较 / \ false true / \ 不重复 重复了 需求:只要对象内容一样,就希望集合认为它们重复了。重写hashCode和equals方法。 小结: 如果希望Set集合认为两个对象只要内容一样就重复了,必须重写对象的hashCode和equals方法。
Set系列集合元素无序的根本原因。(面试必考) 1 2 3 4 5 6 7 8 9 Set系列集合添加元素无序的根本原因是因为底层采用了哈希表存储元素。 JDK 1.8之前:哈希表 = 数组 + 链表 + (哈希算法) JDK 1.8之后:哈希表 = 数组 + 链表 + 红黑树 + (哈希算法) 当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。 小结: Set系列集合是基于哈希表存储数据的 它的增删改查的性能都很好!!但是它是无序不重复的!如果不在意当然可以使用!
LinkedHashSet集合 1 2 3 4 5 6 7 8 9 10 11 是HashSet的子类,元素是“有序” 不重复,无索引. LinkedHashSet底层依然是使用哈希表存储元素的, 但是每个元素都额外带一个链来维护添加顺序!! 不光增删查快,还有序。缺点是多了一个存储顺序的链会占内存空间!!而且不允许重复,无索引。 总结: 如果希望元素可以重复,又有索引,查询要快用ArrayList集合。(用的最多) 如果希望元素可以重复,又有索引,增删要快要用LinkedList集合。(适合查询元素比较少的情况,经常要首尾操作元素的情况) 如果希望增删改查都很快,但是元素不重复以及无序无索引,那么用HashSet集合。 如果希望增删改查都很快且有序,但是元素不重复以及无索引,那么用LinkedHashSet集合。
TreeSet集合 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 TreeSet: 不重复,无索引,按照大小默认升序排序!! TreeSet集合称为排序不重复集合,可以对元素进行默认的升序排序。 TreeSet集合自自排序的方式: 1.有值特性的元素直接可以升序排序。(浮点型,整型) 2.字符串类型的元素会按照首字符的编号排序。 3.对于自定义的引用数据类型,TreeSet默认无法排序,执行的时候直接报错,因为人家不知道排序规则。 自定义的引用数据类型的排序实现: 对于自定义的引用数据类型,TreeSet默认无法排序 所以我们需要定制排序的大小规则,程序员定义大小规则的方案有2种: a.直接为对象的类实现比较器规则接口Comparable,重写比较方法(拓展方式) // 如果程序员认为比较者大于被比较者 返回正数! // 如果程序员认为比较者小于被比较者 返回负数! // 如果程序员认为比较者等于被比较者 返回0! b.直接为集合设置比较器Comparator对象,重写比较方法 // 如果程序员认为比较者大于被比较者 返回正数! // 如果程序员认为比较者小于被比较者 返回负数! // 如果程序员认为比较者等于被比较者 返回0! 注意:如果类和集合都带有比较规则,优先使用集合自带的比较规则。 小结: TreeSet集合对自定义引用数据类型排序,默认无法进行。 但是有两种方式可以让程序员定义大小规则: a.直接为对象的类实现比较器规则接口Comparable,重写比较方法(拓展方式) b.直接为集合设置比较器Comparator对象,重写比较方法 注意:如果类和集合都带有比较规则,优先使用集合自带的比较规则。
Collections工具类的使用 1 2 3 4 5 6 7 8 java.utils.Collections:是集合工具类 Collections并不属于集合,是用来操作集合的工具类。 Collections有几个常用的API: - public static <T> boolean addAll(Collection<? super T> c, T... elements) 给集合对象批量添加元素! - public static void shuffle(List<?> list) :打乱集合顺序。 - public static <T> void sort(List<T> list):将集合中元素按照默认规则排序。 - public static <T> void sort(List<T> list,Comparator<? super T> ):将集合中元素按照指定规则排序。
引用数据类型的排序 1 2 3 4 5 6 7 8 9 10 11 字符串按照首字符的编号升序排序! 自定义类型的比较方法API: - public static <T> void sort(List<T> list): 将集合中元素按照默认规则排序。 对于自定义的引用类型的排序人家根本不知道怎么排,直接报错! 如果希望自定义的引用类型排序不报错,可以给类提供比较规则:Comparable。 - public static <T> void sort(List<T> list,Comparator<? super T> c): 将集合中元素按照指定规则排序,自带比较器 注意:如果类有比较规则,而这里有比较器,优先使用比较器。
可变参数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 可变参数用在形参中可以接收多个数据。 可变参数的格式:数据类型... 参数名称 可变参数的作用: 传输参数非常灵活,方便。 可以不传输参数。 可以传输一个参数。 可以传输多个参数。 可以传输一个数组。 可变参数在方法内部本质上就是一个数组。 可变参数的注意事项: 1.一个形参列表中可变参数只能有一个!! 2.可变参数必须放在形参列表的最后面!!
Map集合 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 Map集合是另一个集合体系。 Collection是单值集合体系。 Map集合是一种双列集合,每个元素包含两个值。 Map集合的每个元素的格式:key=value(键值对元素)。 Map集合也被称为“键值对集合”。 Map集合的完整格式:{key1=value1 , key2=value2 , key3=value3 , ...} Map集合有啥用? 1.Map集合存储的信息更加的具体丰富。 Collection: ["苍老师","日本","女","动作演员",23,"广州"] Map : {name="苍老师" , jiaxiang=小日本 , sex="女" , age = 23 , addr=广州} 2.Map集合很适合做购物车这样的系统。 Map: {娃娃=30 , huawei=1 , iphonex=1} 注意:集合和泛型都只能支持引用数据类型,集合完全可以称为是对象容器,存储都是对象。 Map集合的体系: Map<K , V>(接口,Map集合的祖宗类) / \ TreeMap<K , V> HashMap<K , V>(实现类,经典的,用的最多) \ LinkedHashMap<K, V>(实现类) Map集合的特点: 1.Map集合的特点都是由键决定的。 2.Map集合的键是无序,不重复的,无索引的。 Map集合后面重复的键对应的元素会覆盖前面的整个元素! 3.Map集合的值无要求。 4.Map集合的键值对都可以为null。 HashMap:元素按照键是无序,不重复,无索引,值不做要求。 LinkedHashMap:元素按照键是有序,不重复,无索引,值不做要求。
Map集合的常用API(重点中的重点) 1 2 3 4 5 6 - public V put(K key, V value): 把指定的键与指定的值添加到Map集合中。 - public V remove(Object key): 把指定的键 所对应的键值对元素 在Map集合中删除,返回被删除元素的值。 - public V get(Object key) 根据指定的键,在Map集合中获取对应的值。 - public Set<K> keySet(): 获取Map集合中所有的键,存储到Set集合中。 - public Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)。 - public boolean containKey(Object key):判断该集合中是否有此键。
Map集合的遍历方式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Map集合的遍历方式有:3种。 (1)“键找值”的方式遍历:先获取Map集合全部的键,再根据遍历键找值。 (2)“键值对”的方式遍历:难度较大。 (3)JDK 1.8开始之后的新技术:Lambda表达式。 a.“键找值”的方式遍历Map集合。 1.先获取Map集合的全部键的Set集合。 2.遍历键的Set集合,然后通过键找值。 b.“键值对”的方式遍历: 1.把Map集合转换成一个Set集合:Set<Map.Entry<K, V>> entrySet(); 2.此时键值对元素的类型就确定了,类型是键值对实体类型:Map.Entry<K, V> 3.接下来就可以用foreach遍历这个Set集合,类型用Map.Entry<K, V> c.JDK 1.8开始之后的新技术:Lambda表达式。
Map集合存储自定义类型 1 2 3 4 5 Map集合的键和值都可以存储自定义类型。 小结: Map集合的键和值都可以存储自定义类型。 如果希望Map集合认为自定义类型的键对象重复了,必须重写对象的hashCode()和equals()方法
LinkedHashMap集合 1 2 3 4 5 6 7 8 9 10 11 12 13 LinkedHashMap是HashMap的子类。 -- 添加的元素按照键有序,不重复的。 HashSet集合相当于是HashMap集合的键都不带值。 LinkedHashSet集合相当于是LinkedHashMap集合的键都不带值。 底层原理完全一样,都是基于哈希表按照键存储数据的, 只是HashMap或者LinkedHashMap的键都多一个附属值。 小结: HashMap集合是无序不重复的键值对集合。 LinkedHashMap集合是有序不重复的键值对集合。 他们都是基于哈希表存储数据,增删改查都很好。
TreeMap集合 1 2 3 4 5 6 7 8 TreeMap集合按照键是可排序不重复的键值对集合。(默认升序) TreeMap集合按照键排序的特点与TreeSet是完全一样的。 小结: TreeMap集合和TreeSet集合都是排序不重复集合 TreeSet集合的底层是基于TreeMap,只是键没有附属值而已。 所以TreeMap集合指定大小规则有2种方式: a.直接为对象的类实现比较器规则接口Comparable,重写比较方法(拓展方式) b.直接为集合设置比较器Comparator对象,重写比较方法
输出一个字符串中每个字符出现的次数。(经典面试题) 1 2 3 4 5 (1)键盘录入一个字符串。aabbccddaa123。 (2)定义一个Map集合,键是每个字符,值是其出现的次数。 {a=4 , b=2 ,...} (3)遍历字符串中的每一个字符。 (4)拿着这个字符去Map集合中看是否有这个字符键,有说明之前统计过,其值+1 没有这个字符键,说明该字符是第一次统计,直接存入“该字符=1”
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public class MapDemo01 { public static void main(String[] args) { // (1)键盘录入一个字符串。aabbccddaa123。 Scanner scanner = new Scanner(System.in); System.out.print("请您输入一个字符串:"); String datas = scanner.nextLine(); // (2)定义一个Map集合,键是每个字符,值是其出现的次数。 Map<Character , Integer> infos = new HashMap<>(); // {a=2,b=2} // (3)遍历字符串中的每一个字符。 // datas = aabbccddaa123 for(int i = 0 ; i < datas.length() ; i++ ){ // 取出当前索引的字符 char ch = datas.charAt(i); // (4)拿着这个字符去Map集合中看是否有这个字符键,有说明之前统计过,其值+1 // 没有这个字符键,说明该字符是第一次统计,直接存入“该字符=1” if(infos.containsKey(ch)){ // 说明这个字符之前已经出现过,其值+1 infos.put(ch , infos.get(ch) + 1); }else{ // 说明这个字符第一次出现,直接存入 a=1 infos.put(ch , 1); } } // (5)输出结果 System.out.println("结果:"+infos); } }