java基础-集合

2022 年 9 月 28 日
筆記
JAVA

java基础-集合

以下内容为本人的学习笔记，如需要转载，请声明原文链接 //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();
}
}

Tags: JAVA