java总结--集合篇
java总结(1)
1.集合篇
1.1集合之间的比较
1.1 1ArrayLis vs Vector
ArrayList和Vector底层都是动态数组实现的。动态数组:在Java中数组一旦初始化后就不能再改变数组长度。ArrayList和Vector底层是通过创建新的数组的方式,来达到数组动态扩展的目的。
区别:ArrayList是线程不安全的集合,Vector是线程安全的集合,一般使用ArrayList。
1.12 LinkedList VS ArrayList
linked底层是双链表实现,链表是一种非常常见的线性数据结构(和数组类似),由一个一个的节点组成,每个节点都有一个指针,指向链表的下一个节点,因为有"指针"的存在,所以链表在内存空间上可以地址不连续,因此链表没有长度的限制(数组在内存空间上地址必须连续,长度有限)。双向链表就是普通链表的节点多了一个指向上一个节点的指针
区别:
1.插入性能对比:
**尾部:**ArrayList和LinkedList性能相近
**中间:**ArrayList的速度 >> LinkedList的速度,ArrayList虽然存在移位,但是底层通过C++直接操作内存的方式进行了优化,而LinkedList每次插入都需要通过遍历的方式找到元素,所以性能有所下降。
**头部:**LinkedList的速度 >> ArrayList的速度,ArrayList往头部插入元素,也就意味着每次都需要位移整个数组,虽然有优化,但是也不等于没有耗时,但是LinkedList查找靠前/后的元素速度很快,同时插入性能也很快,所以相对ArrayList性能更优
2.查询性能对比:
**尾部:**ArrayList和LinkedList性能相近
**中间:**ArrayList >>>>>>>> LinkedList
**头部:**ArrayList和LinkedList性能相近
1.13HashSet、LinkedHashSet、TreeSet
Set各个实现类的特点:
HashSet:无序、不可重复
**LinkedHashSet:**不可重复,但是元素有序(插入顺序)
**TreeSet:**不可重复,但是元素有序(字典顺序)
1.14HashMap、Hashtable
1.HashMap和Hashtable底层都是由哈希表实现的,Hashtable和HashMap的关系与Vector和ArrayList之间的关系类似,Hashtable线程安全,HashMap线程不安全
2.哈希表是一种用于快速搜索的数据结构,精准查询(通过key查询value)效率极高,和元素的数量(理想型,实际过程中,多少还是有点关系)无关,所以时间复杂度为O(1)
3.红黑树本身是一种特殊的二叉树,是用于快速查询的数据结构
4.二叉搜索树:在一颗二叉树中,任意节点的左子树节点都比当前节点要小,右子树节点都比当前节点要大,那么这颗二叉树就称之为二叉搜索树
二叉搜索树的缺点:如果插入的元素有一定的顺序,那么就可以导致树的失衡,从而严重降低树的查询能力
红黑树就是为了解决二叉搜索树,失衡问题而设计的一颗二叉搜索平衡树
1.15 LinkedHashMap
key有序(插入顺序),不可重复;
底层原理:在HashMap的基础上,新增了一个链表结构(和解决哈希冲突的链表是两回事),这个链表是用来维护元素的插入顺序的
本质上LinkedHashMap和HashMap的实现方式几乎一致,只是添加元素时,需要额外的去维护一个插入顺序的链表,所以添加元素的性能比HashMap略低,但是正因为有这个链表的存在,所以遍历哈希表的性能反而要高于HashMap
1.16 TreeMap
key有序(字典排序),不可重复;
底层原理:没有哈希表,底层完全有红-黑树实现。查询性能和添加性能平均情况都低于HashMap,所以除非真的需要key有顺序,否则我们都应该使用HashMap,而不是TreeMap
在TreeMap中判断两个key是否相同的方式,不是用==,也不是用equals方法,而是通过比较器(compare)的方法判断是否返回0,如果比较器返回0了,就表示key相同了。
1.2Collection集合
1.21 collection
1.collection为所有单列集合的父接口,单列集合(List和Set)通用的方法有:
-
public boolean add(E e)
: 把给定的对象添加到当前集合中 。 -
public void clear()
:清空集合中所有的元素。 -
public boolean remove(E e)
: 把给定的对象在当前集合中删除。 -
public boolean contains(E e)
: 判断当前集合中是否包含给定的对象。 -
public boolean isEmpty()
: 判断当前集合是否为空。 -
public int size()
: 返回集合中元素的个数。 -
public Object[] toArray()
: 把集合中的元素,存储到数组中。
2.collection遍历主要使用Iterator迭代器,也使用增强for循环。
-
获取迭代器的方法:
public Iterator iterator()
: 获取集合对应的迭代器,用来遍历集合中的元素的 -
迭代器接口常用的方法:
public E next()
:返回迭代的下一个元素。
public boolean hasNext()
:如果仍有元素可以迭代,则返回 true。 -
增强for循环:是JDK1.5以后出来的一个高级for循环,专门用来遍历数组和集合的。它的内部原理其实是个Iterator迭代器,所以在遍历的过程中,不能对集合中的元素进行增删操作。格式:
for(元素的数据类型 变量 : Collection集合or数组){ //写操作代码 }
3.泛型:只要把对象存储集合后,那么这时他们都会被提升成Object类型。当我们在取出每一个对象,并且进行相应的操作,这时必须采用类型转换。泛型可以在类或方法中预支地使用未知的类型。一般在创建对象时,将未知的类型确定具体的类型。当没有指定泛型时,默认类型为Object类型。
好处:1.将运行时期的ClassCastException,转移到了编译时期变成了编译失败。2.避免了类型强转的麻烦。
1)定义和使用含有泛型的类:
修饰符 class 类名<代表泛型的变量> { }
在创建对象时确定泛型
2)含有泛型的方法:
修饰符 <代表泛型的变量> 返回值类型 方法名(参数){ }
调用方法时确定泛型的类型
3)含有泛型的接口:
修饰符 interface接口名<代表泛型的变量> { }
使用格式:1.定义类时确定泛型的类型;2.始终不确定泛型的类型,直到创建对象时,确定泛型的类型
泛型通配符:不知道使用什么类型来接收的时候,此时可以使用?,?表示未知通配符。
通配符高级使用----受限泛型:之前设置泛型的时候,实际上是可以任意设置的,只要是类就可以设置。但是在JAVA的泛型中可以指定一个泛型的上限和下限
泛型的上限:
-
格式:
类型名称 <? extends 类 > 对象名称
-
意义:
只能接收该类型及其子类
泛型的下限:
-
格式:
类型名称 <? super 类 > 对象名称
-
意义:
只能接收该类型及其父类型
比如:现已知Object类,String 类,Number类,Integer类,其中Number是Integer的父类
1.22 数据结构
栈:先进后出,进又叫压栈,出又叫弹栈;压栈时存元素,把元素存储到栈的顶端位置,栈中已有元素依次向栈底方向移动一个位置。弹栈是取元素,,把栈的顶端位置元素取出,栈中已有元素依次向栈顶方向移动一个位置。
队列:其与堆栈一样,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除,其特点:先进先出;队列的入口和出口各占一侧
数组:有序的元素序列,数组是在内存中开辟一段连续的空间,并在此空间存放元素。其特点:查找元素快、增删慢
增删慢的原因:
指定索引位置增加元素:需要创建一个新的数组,将指定新元素存储到指定索引位置,再把原数组元素根据索引,复制到新数组对应索引的位置
指定索引位置删除元素:需要创建一个新的数组,把元数组元素根据索引,复制到数组对应索引的位置,原数组指定索引位置不复制到新数组中
链表: linked list 由一系列结点node(链表中每一个元素称为结点)组成,结点可以在运行时i动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表。其特点:多个结点之间,通过地址进行连接(手拉手);查找元素慢(查找某个元素,需要通过连接的节点依次向后查找指定的元素);增删快(增加元素只需要修改连接下个元素的地址即可;删除元素只需要修改连接下个元素的地址即可)
红黑树:红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。
红黑树的约束: 1.节点可以是红色的或者黑色的 2.根节点是黑色3.叶子节点(特指空节点)是黑色的4.每个红色节点的子节点都是黑色的5.任何一个节点到其 每一个叶子节点的所有路径上黑色节点数相同
红黑树的特点:速度特别快,趋*衡树,查找叶子元素最少和最多次数不多于二倍
1.3 List接口
List接口的特点:1. 它是一个元素存取有序的集合;2. 它是一个带有索引的集合,通过索引就可以精确的操作集合中的元素;3. 集合中可以有重复的元素,通过元素的equals方法,来比较是否为重复的元素。子类:ArrayList和LinkedList
常用方法:
- public void add(int index, E element) : 将指定的元素,添加到该集合中的指定位置上。
- public E get(int index) :返回集合中指定位置的元素。
- public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
- public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
1.4 Set接口
Set集合取出元素的方式可以采用:迭代器、增强for。
1.41 HashSet
HashSet 是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于: hashCode 与equals 方法。
HashSet中存放自定义类型元素时,需要重写对象中的hashCode和equals方法,建立自己的比较方式,才能保证HashSet集合中的对象唯一(比如,创建一个Student类,在使用Student作为HashSet的类型时,需要在Student类中重写hashCode和equals方法。
1.42 LinkedHashSet
HashSet保证元素唯一但存放无序,其子类LinkedHashset它是链表和哈希表组合的一个数据存储结构
1.5Collections
常用功能:(静态方法,直接类调用方法)
- public static boolean addAll(Collection c, T… elements) :往集合中添加一些元素
- public static void shuffle(List<?> list) 打乱顺序:打乱集合顺序。
- public static void sort(List list) :将集合中元素按照默认规则排序。
- public static void sort(List list,Comparator<? super T> ) :将集合中元素按照指定规则排
序。
1.6 比较器Comparable和Comparator区别
Comparable:强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序,类的compareTo方法被称为它的自然比较方法。只能在类中实现compareTo()一次,不能经常修改类的代码实现自己想要的排序。实现此接口的对象列表(和数组)可以通过Collections.sort(和Arrays.sort)进行自动排序,对象可以用作有序映射中的键或有序集合中的元素,无需指定比较器
Comparator强行对某个对象进行整体排序。可以将Comparator 传递给sort方法(如Collections.sort或Arrays.sort),从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构(如有序set或有序映射)的顺序,或者为那些没有自然顺序的对象collection提供排序。
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getAge()‐o1.getAge();//以学生的年龄降序
}
});
public class Student implements Comparable<Student>{
....
@Override
public int compareTo(Student o) {
return this.age‐o.age;//升序
}
}
1.7 Map接口
Map 接口常用的子类有HashMap和LinkedHashMap集合,其中:
HashMap :存储数据采用的哈希表结构,元素的存取顺序不能保证一致。由于要保证键的唯一、不重复,需要重写键的hashCode()方法、equals()方法。
LinkedHashMap:HashMap下有个子类LinkedHashMap,存储数据采用的哈希表结构+链表结构。通过链表结构可以保证元素的存取顺序一致;通过哈希表结构可以保证的键的唯一、不重复,需要重写键的hashCode()方法、equals()方法
Map接口中常用方法:
- public V put(K key, V value) : 把指定的键与指定的值添加到Map集合中。
public V remove(Object key) : 把指定的键 所对应的键值对元素 在Map集合中删除,返回被删除元素的
值。
public V **get(Object key) **根据指定的键,在Map集合中获取对应的值。
public Set keySet() : 获取Map集合中所有的键,存储到Set集合中。
public Set<Map.Entry<K,V>> **entrySet() **: 获取到Map集合中所有的键值对对象的集合(Set集合)。
Map集合遍历键找值得方式:通过元素中的键,获取键对应的值。步骤:
-
获取Map中所有的键,由于键是唯一的,所以返回一个Set集合存储所有的键。方法提示: keyset()
-
遍历键的Set集合,得到每一个键。
-
根据键,获取键所对应的值。方法提示: get(K key)
其中:当给HashMap中存放自定义对象时,如果自定义对象作为key存在,这时要保证对象唯一,必须复写对象的hashCode和equals方法(如果忘记,请回顾HashSet存放自定义对象)。如果要保证map中存放的key和取出的顺序一致,可以使用java.util.LinkedHashMap 集合来存放。
上一篇: VBA判断单元格内容格式、颜色、合并单元格及返回数值
下一篇: 【C++基础】sort函数