java基础-集合
java基础-集合
以下内容为本人的学习笔记,如需要转载,请声明原文链接 https://www.cnblogs.com/lyh1024/p/16738857.html
1.集合框架概述
1.1集合框架 的作用
在实际开发中,我们经常会对一组相同类型的数据进行统一管理操作。到目前为止,我们可以使用数组结构,链表结构,二叉树来实现。
数组的最大问题在于数组中的元素个数是固定的,要实现动态数组,还是比较麻烦,
在JDK1.2版本后,java完整提供了类集合的概念,封装了一组强大的,非常方便的集合框架API,让我们在开发中大大的提高了效率。
集合中分为三大接口;
Collection、Map、Iterator
集合框架的接口和类在java.util包中
1.2 集合框架结构图:
注:虚线表示接口,实现表示实现类。
1.3 Collection接口
Collection 层次结构 中的根接口。Collection 表示一组对象,这些对象也称为 collection 的元素。一些 collection 允许有重复的元素,而另一些则不允许。一些 collection 是有序的,而另一些则是无序的。JDK 不提供此接口的任何直接 实现:它提供更具体的子接口(如 Set
和 List
)实现。此接口通常用来传递 collection,并在需要最大普遍性的地方操作这些 collection。
接口的定义:
public interface Collection<E> extends Iterator<E>
2集合框架List接口
2.1 List接口
public interface List<E> extends Collection<E>
有序的 collection(也称为序列)。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素。
/**
Collection接口:用于存储单个对象的集合
List接口:
1.有序的,可重复
2.允许多个null元素
3.具体的实现类有常用的:ArrayList,LinkedList,Vector
Set接口
*/
public class ListDemo{
private static void arrayList(){
//使用集合来存储多个不同类型的元素(对象),在处理时会比较麻烦,在实际开发中,不建议这样使用
// List list = new ArrayList();
//在集合中存储相同类型的对象,第二个<>里在jdk1.8可以不用写类型Sting
List<String> list = new ArrayList<>();//加泛型约束String类型
list.add("小米");
list.add("调度");
list.add("狗蛋");
list.add("二毛");
list.add("旺财");
//遍历集合
//for(int i = 0;i<list.size() ;i++),局部变量size会进栈,调用栈会比调用方法快,性能高得多,局部变量size只求一次,而方法要一直调用
int size = list.size();
for(int i = 0;i<size ;i++){
System.out.println(list.get(i))//list.get(int i),获取下标为i 的值
}
System.out.println(list.contains("小米"))//contains():List是否包含"小米"
list.remove("小米")//删除"小米"
String[] array = list.toArray(new String[]{});//toArray(),转换成array数组,参数:定义数组类型
for(String s: array){
System.out.println(s);
}
}
public static void main(String[] args){
arrayList();
}
}
在实际开发中,我们如何选择list的具体实现?
1.安全性问题
2.是否频繁插入,删除操作(LinkedList)
3.是否是存储后遍历
面试题:怎么实现ArrayList,即ArrayList的原理?
2.2ArrayList
public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,Serializable
List
接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括 null
在内的所有元素。除了实现 List
接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(
/**ArrayList
1.实现原理,采用动态对象数组实现,默认构造方法创建了一个空数组
2.第一次添加元素,扩展容量为10,之后的扩充算法:原来数组大小+原来数组的一半
3.不适合进行删除或插入操作,否则导致位置会变
4.为了防止数组动态扩充次数过多,建议创建ArrayList时,给定初始容量
5.多线程中使用不安全,适合在单线程访问时使用,在单线程下使用效率高
JDK1.2开始
*/
2.3 Vector
Vector
类可以实现可增长的对象数组。与数组一样,它包含可以使用整数索引进行访问的组件。但是,Vector
的大小可以根据需要增大或缩小,以适应创建 Vector
后进行添加或移除项的操作。
private static void vector(){
/**
Vector
1.实现原理,采用动态对象数组实现,默认构造方法创建了一个大小为10的对象数组
2.扩充的算法:当增量为0时,扩充为原来大小的2倍,当增量>0时,扩充为原来大小+增量
3.不适合删除或插入操作
4.为了防止数组动态扩充次数过多,建议创建Vector时,给定初始容量
5.线程安全,适合在多线程访问时使用,在单线程下使用效率较低,因为内部方法加了synchronized同步锁
*/
Vector<String> vector = new Vector<>();
vector .add("小米");
vector .add("调度");
vector .add("狗蛋");
vector .add("二毛");
vector .add("旺财");
for(int i = 0;i<v.size();i++){
System.out.println(v.get(i))
}
public static void main(String[] args){
vector();
}
}
面试题:Vector与ArrayLIst的区别?
2.4 LinkedList
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>,Deque<E>,Cloneable,Serializable
List
接口的链接列表实现。实现所有可选的列表操作,并且允许所有元素(包括 null
)。除了实现 List
接口外,LinkedList
类还为在列表的开头及结尾 get
、remove
和 insert
元素提供了统一的命名方法。
/**
LinkedList
1.实现原理,采用双向链表结构实现
2.适合插入,删除操作,性能高
*/
private static void linkedList(){
LinkedList<String> list = new LinkedList<>();
list.add("小米");
list.add("调度");
list.add("狗蛋");
list.add("二毛");
list.add("旺财");
//遍历集合
int size = list.size();
for(int i = 0;i<size ;i++){
System.out.println(list.get(i));
}
}
3集合框架Set接口
3.1 set接口
public interface Set<E> extends Collection<E>
一个不包含重复元素的 collection。更确切地讲,set 不包含满足 e1.equals(e2)
的元素对 e1
和 e2
,并且最多包含一个 null 元素。正如其名称所暗示的,此接口模仿了数学上的 set 抽象。
3.2HashSet
-
public class **HashSet<E>**extends AbstractSet<E>implements Set<E>, Cloneable, Serializable
此类实现 Set
接口,由哈希表(实际上是一个 HashMap
实例)支持。它不保证 set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用 null
元素。
/**
Set接口
1.无序的(不保证顺序)
2.不允许重复元素
实现类:HashSet,TreeSet,LinkedHashSet,三者底层实现与Map关联
选择使用
如果要排序,选择treeSet
如果不要排序,也不用保证顺序选择HashSet
不要排序,要保证顺序,选择LinkedHashSet
*/
public class SetDemo{
public static void main(Sting[] args){
/**
HashSet
1.实现原理,基于哈希表(HashMap)实现
2.不允许重复,可以有一个NULL元素
3.不保证顺序恒久不变(例:添加元素后,输出顺序会变)
4.添加元素时把元素作为HashMap的key存储,HashMap的value使用一个固定的Object对象
5.排除重复元素是通过equals来检查对象是否相同
6.判断两个对象是否相同,先判断两个对象的hashCode是否相同,(如果两个对象的hashCode相同,不一定是同一个对象,如果不同,那一定不是同一个对象;整数范围就这么大,有可能重复),如果不同,则两个对象不是同一个对象,如果相同,还要进行equals判断,equals相同则是同一个对象,不同则不是同一个对象。
7.自定义对象要认为属性值都相同时为同一个对象,有这种需求时,那么我们要重写对象所在实体类的hashCode和equals方法
小结
(1)哈希表的存储结构:数组+链表,数组里的每个元素以链表的形式存储
(2)如何把对象存储到哈希表中,先计算对象的hashCode值,再对数组的长度求余数,来决定对象要存储在数组中的哪个位置(不同的值放到数组里,相同的值按先后顺序作为链表放在一格数组里,先放进去的就是根,后进去的作为根的next)
(3)解决hashSet中的重复值使用的方式是:参考第六点
*/
private static void hashSet(){
Set<String> set = new HashSet<>();
set.add("张飞");
set.add("关羽");
set.add("刘备");
set.add("诸葛亮");
set.add("曹操");
set.add("诸葛亮");//把上面的"诸葛亮"替换掉,添加自定义的不同对象,且相同值的对象时不会被替换
String[] names = set.toArray(new String[]{})
for(String s : names){
System.out.println(s);
}
}
}
}
hashCode深入分析
hashCode()方法,在Object类中定义如下:
public native int hashCode();//native本地方法
hashCode是本地方法,它的实现是根据本地机器相关,当然我们可以在自己写的类中覆盖hashCode()方法,比如 String ,Integer,Double……等等这些类都是覆盖了hashCode()方法的。
-
判断两个对象是否相同:先判断两个对象的hashCode是否相同,([重写hashCode(),根据值来计算hashCode,值相等判定为同一对象,]如果两个对象的hashCode相同,不一定是同一个对象,如果不同,那一定不是同一个对象;整数范围就这么大,有可能重复),如果不同,则两个对象不是同一个对象,如果相同,还要进行equals判断,equals相同则是同一个对象,不同则不是同一个对象。
-
如何把对象存储到哈希表中:先计算对象的hashCode值,再对数组的长度求余数,来决定对象要存储在数组中的哪个位置(不同的值放到数组里,相同的值按先后顺序作为链表放在一格数组里,先放进去的就是根,后进去的作为根的next)
3.3 TreeSet(排序)
-
public class **TreeSet<E>**extends AbstractSet<E>implements NavigableSet<E>, Cloneable, Serializable
基于 TreeMap的 NavigableSet实现。使用元素的自然顺序对元素进行排序,或者根据创建 set 时提供的 Comparator 进行排序,具体取决于使用的构造方法。
/**
有序的,基于TreeMap(二叉树数据结构),对象需要比较大小,通过对象比较器来实现,
对象比较器还可以用来去除重复元素,
如果自定义的数据类,没有实现比较器接口,将无法添加到TreeSet集合中。
*/
private static void treeSet(){
TreeSet<String> tree = new TreeSet<>(new CatComparetor());
Cat c1 = new Cat("wanwan",2,1) //参数:名字,年龄,编号
Cat c2 = new Cat("guanguan",3,2)
Cat c3 = new Cat("wanwan",2,3)
Cat c4 = new Cat("wanwan",2,1)
tree.add(c1);
tree.add(c2);
tree.add(c3);
tree.add(c4);
System.out.println(tree.size() );//如果创建TreeSet实例时没有传入new CatComparetor()比较器的话,对象间无法比较排序,报类型转换异常错误
for(Cat c : tree){
System.out.println(c);
}
}
public class CatComparetor implements Comparator<Cat>{
public int compare(Cat o1,Cat o2){
// return o1.getAge()-o2.getAge()//根据年龄来比较,相同年龄会被判定为同一对象,存不进去
}
}
3.4LinkedHashSet(顺序)
-
public class **LinkedHashSet<E>**extends HashSet<E>implements Set<E>, Cloneable, Serializable
具有可预知迭代顺序的 Set
接口的哈希表和链接列表实现。此实现与 HashSet
的不同之外在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,即按照将元素插入到 set 中的顺序(插入顺序)进行迭代。注意,插入顺序不 受在 set 中重新插入的 元素的影响。(如果在 s.contains(e)
返回 true
后立即调用 s.add(e)
,则元素 e
会被重新插入到 set s
中。)
/**
哈希表和链接列表实现
维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,即按照将元素插入到 set 中的顺序(*插入顺序*)进行迭代
*/
private static void linkedHashSet(){
LinkedHashSet<String> set = new LinkedHashSet<>();//链表来记录位置
Cat c1 = new Cat("wanwan",2,1) //参数:名字,年龄,编号
Cat c2 = new Cat("guanguan",3,2)
Cat c3 = new Cat("wanwan",2,3)
Cat c4 = new Cat("wanwan",2,1)
set.add(c1);
set.add(c2);
set.add(c3);
set.add(c4);
for(Cat c : set){
System.out.println(c);
}
}
4.集合框架Iterator接口
4.1 集合输出
前面我们已经学习了集合的基本操作,很多情况下,我们需要把集合的内容进行输出,也就是遍历集合
遍历集合的方式有一下几种:
-
Iterator
-
ListIterator(一般用得很少)
-
Enumeration(枚举迭代接口)
-
foreach(,最方便,用得也多)
其中Iterator的使用率最高,在JDK1.5后新增了foreach,也被大量使用。有了Iterator迭代器,不同的集合也可以用相同的方式来迭代,而内部隐藏了不同的具体实现
4.2 Iterator
-
public interface **Iterator<E>**
对 collection 进行迭代的迭代器。迭代器取代了 Java Collections Framework 中的 Enumeration。
类型 | 说明 |
---|---|
boolean |
[hasNext()如果仍有元素可以迭代,则返回 true。 |
E |
next() 返回迭代的下一个元素。 |
void |
remove() 从迭代器指向的 collection 中移除迭代器返回的最后一个元素(可选操作)。 |
4.3 ListIterator
-
public interface **ListIterator<E>**extends Iterator<E>
系列表迭代器,允许程序员按任一方向遍历列表、迭代期间修改列表,并获得迭代器在列表中的当前位置。
类型 | 说明 |
---|---|
void |
[add(E e) 将指定的元素插入列表(可选操作)。 |
boolean |
hasPrevious()如果以逆向遍历列表,列表迭代器有多个元素,则返回 true。 |
int |
nextIndex()返回对 next 的后续调用所返回元素的索引。 |
E |
previous() 返回列表中的前一个元素。 |
int |
previousIndex()返回对 previous` 的后续调用所返回元素的索引。 |
void |
set(E e)用指定元素替换 next或 previous` 返回的最后一个元素(可选操作)。 |
4.4 Enumeration
-
public interface **Enumeration<E>**
实现 Enumeration 接口的对象,它生成一系列元素,一次生成一个。连续调用 nextElement
方法将返回一系列的连续元素。
注:此接口的功能与 Iterator 接口的功能是重复的。此外,Iterator 接口添加了一个可选的移除操作,并使用较短的方法名。新的实现应该优先考虑使用 Iterator 接口而不是 Enumeration 接口。
类型 | 说明 |
---|---|
boolean |
hasMoreElements() 测试此枚举是否包含更多的元素。 |
E |
nextElement() 如果此枚举对象至少还有一个可提供的元素,则返回此枚举的下一个元素。 |
/**
集合输出,迭代
*/
public class IteratorDemo{
//foreach,JDK1.5后才有
private static void foreach(Collection<Cat>){
for(Cat cat :c ){
System.out.println(cat);
}
}
//iterator,JDK1.5之前统一的迭代集合方式
private static void iterator(Collection<Cat>){
Iterator<Cat> iter = c.iterator();//iterator()以正确的顺序返回该列表中的元素的迭代器
while(iter.hasNext()){
System.out.println(iter.next());
}
//Enumeration,常搭配Vector使用
private static void enumeration(Collection<Cat>){
Vector<Stirng> vs = new Vector<>();
vs.add("tom");
vs.add("job");
vs.add("jack");
vs.add("lily");
Enumeration<String> es = vs.elements();
while(es.hasMoreElements()){
System.out.println(es.nextElement());
}
// ListIterator提供向上遍历的方法previous()
}
public static void main(String[] args){
List<Cat> list = new ArrayList<>();
Cat c1 = new Cat("wanwan",2,1) //参数:名字,年龄,编号
Cat c2 = new Cat("guanguan",3,2)
Cat c3 = new Cat("wanwan",2,3)
Cat c4 = new Cat("wanwan",2,1)
list.add(c1);
list.add(c2);
list.add(c3);
list.add(c4);
foreach(list);
iterator(list);//输出遍历
enumeration();
}
}
有待补充….
参考资料:
JDK1.6帮助文档