集合(##)

1.1为什么会出现集合框架
[1] 之前的数组作为容器时,不能自动拓容
[2] 数值在进行添加和删除操作时,需要开发者自己实现添加和删除。

1.2Collection接口
1.2.1Collection基础API
Java集合框架提供了一套性能优良、使用方便的接口和类,它们位于java.util包中。
Collection表示集合的根接口,可以看成一个容器,存储了很多对象,这些对象称为Collection元素。Collection要求元素必须是引用数据类型。
Collection 根据其元素的特征可以分为
List接口->元素有序、可重复
Set 接口-> 元素无序、不可重复


image.png

思考:Collection提供了具备什么能力?=> 对容器增删改查
public class Test01 {
public static void main(String[] args) {
/**
* 增:add/addAll
* 删:clear/remove/removeAll/retainAll
* 改:
* 查:contains/constainsAll/size/isEmpty
* 其他:equals
* 遍历:iterator()
*/

    Collection col1 = new ArrayList();
    col1.add("apple");  // Object obj = "apple" 多态
    col1.add("banana");         // Integer i = 1;   装箱
    // 注意:Collection可以添加任意类型的数据,最好添加统一类型的数据方便未来统一访问。
    
    Collection col2= new ArrayList();
    col2.add("apple");
    col2.add("banana");
    // col1.addAll(col2);
    //System.out.println(col1);
    
    
    //col1.clear();         // 清空集合
    //col1.remove("apple"); // 移除指定元素
    //col1.removeAll(col2); // 移除指定集合中的多个元素
    //col1.retainAll(col2); // 保留指定集合col2中的元素,其他删除
    //System.out.println(col1);
    
    //col1.remove(1);           // [apple, banana, 2]
    //System.out.println(col1.contains("apple"));
    //System.out.println(col1.containsAll(col2));
    //System.out.println(col1.size());  // 返回元素个数
    //System.out.println(col1.isEmpty());
    
    boolean r = col1.equals(col2);
    System.out.println(r);
    
}

}
1.2.2遍历和Iterable
Iterable 表示可遍历的,具备遍历的能力。其定义了一个方法iterator用于返回集合上的迭代器,该迭代器用于foreach快速遍历。
1.2.2遍历和Iterable
Iterable 表示可遍历的,具备遍历的能力。其定义了一个方法iterator用于返回集合上的迭代器,该迭代器用于foreach快速遍历。

public static void main(String[] args) {
    
    Collection col1 = new ArrayList();
    col1.add("apple");
    col1.add("coco");
    col1.add("banana");
    
    // 遍历集合中的元素
    /*
     * Object 表示迭代元素类型
     * item 表示迭代变量
     * */ 
    // 快速遍历
    for (Object item : col1) {
        System.out.println(item);
    }
    
    // 迭代器遍历
    Iterator it1 = col1.iterator(); // 返回集合的迭代器
    while(it1.hasNext()) {
        String item = (String)it1.next();
        System.out.println(item);
    }
    
    // 写法(更节省内存)
    for(Iterator it2 = col1.iterator();it2.hasNext();) {
        String item = (String)it2.next();
        System.out.println(item);
    }
}

1.3List接口
List 接口称为有序的序列,提供了索引(index)对容器中的元素进行增、删、改、查。
index让List集合中的元素有序、可重复。

1.3.1List接口常用方法

public static void main(String[] args) {
/**
* 增:add(index,e)/addAll(index,c)/add(e)/addAll(c)/
* 删:remove(index)/clear()/remove(e)/removeAll(c)/retainAll(c)
* 改:set(index,e);
* 查:get(index)/indexOf(e)/lastIndexOf(e)/contains/constainsAll/size/isEmpty
* 其他:equals
* 遍历:iterator() / listIterator()
*/

    List list1 = new ArrayList();
    // 【1】添加
    // 追加
    list1.add("apple");
    list1.add("banana");
    // 在指定index位置添加元素coco
    list1.add(0,"coco");
    
    List list2 = new ArrayList();
    list2.add(1);
    list2.add(2);
    list1.addAll(0, list2);
    System.out.println(list1);
    
    // 【2】移除
    //list1.remove(0);
    //System.out.println(list1);
    
    // 【3】修改
    list1.set(0, 100);
    System.out.println(list1);
    
    // 【4】查看元素 可能产生IndexOutOfBoundsException

// System.out.println(list1.get(6));
System.out.println(list1.indexOf(200));

    // list1.add(2);
    // System.out.println(list1.lastIndexOf(2));
    
}

1.3.2List接口遍历
List接口中提供了一个listIterator方法,返回列表的列表迭代器,属于ListIterator接口,提供以任意方向(正向、逆向)遍历列表,同时在遍历列表的过程中还可以操作列表。
public static void main(String[] args) {

    // List 集合的遍历
    List list = new ArrayList();
    list.add("apple");
    list.add("banana");
    list.add("coco");
    // 【1】 for 循环
    for(int i=0;i<list.size();i++) {
        String item = (String) list.get(i);
        System.out.println(item);
    }
    
    // 【2】 快速遍历
    for(Object item:list) {
        System.out.println(item);
    }
    
    // 【3】iterator
    Iterator it1 = list.iterator();
    while(it1.hasNext()) {
        System.out.println(it1.next());
    }
    
    // 【4】listIterator  获取列表的迭代器
    ListIterator it2 = list.listIterator();
    // 正向遍历(A)
    while(it2.hasNext()) {
        System.out.println(it2.next());
    }
    // 逆向遍历(B)
    while(it2.hasPrevious()) {
        System.out.println(it2.previous());
    }
    
    // 【5】从指定位置开始迭代(C)
    System.out.println("--listIterator(index)--");
    ListIterator it3 = list.listIterator(1);
    while(it3.hasNext()) {
        System.out.println(it3.next());
    }
}

思考:Iterator和ListIterator区别?

1.4数据结构(补充知识)
1.4.1线性表
根据物理空间是否连续,可以把线性表分为数组和链表。

数组:物理上连续、逻辑上也连续的内存空间,通过index来访问元素。


image.png

链表:物理上不连续、逻辑上连续的内存空间,也可以通过index来访问元素。


image.png

1.4.2队列
队列是以一个方向先进先出的数据结构
image.png

1.4.3栈
栈是一种先进后出的数据结构


image.png

1.5ArrayList、 LinkedList、Vector
1.5.1ArrayList
ArrayList 类是List接口的实现类,底层数据结构是数组。
ArrayList 是数组的包装类,jdk1.2出现,提供了操作底层数据的很多方法,同时向ArrayList中添加元素时,容器可以自动拓容。
ArrayList 是线程不安全。

API和List接口一样。
1.5.2Vector
Vector 类是List接口的实现类,底层数据结构也是数组。
Vector是数组的包装类,jdk1.0出现,提供了操作底层数据的很多方法,同时向Vector中添加元素时,容器可以自动拓容,也提供了自身特有的方法xxxElement等方法。
Vector 是线程安全。

面试题:ArrayList和Vector有什么区别?
相同点:
[1] 都是List接口的实现类、底层数据结构都是数组

不同点
[1] ArrayList jdk1.2;Vector jdk1.0
[2] ArrayList 线程不安全,效率高;Vector 线程安全,效率低
[3] Vector较ArrayList拥有特有的方法。

1.5.3LinkedList
LinkedList 是List接口的实现类,底层数据结构是链表。
LinkedList是链表的包装类,jdk1.2出现,提供了操作底层数据的很多方法,当向LinkedList中添加元素时,通过链入元素增加容量。
LinkedList线程不安全。

public class Test01 {
public static void main(String[] args) {

    List list1 = new LinkedList();
    
    // 【1】添加
    list1.add("apple");
    list1.add("banana");
    list1.add("coco");
    System.out.println(list1);
    
    // 【2】删除
    list1.remove("apple");
    
    // 【3】修改
    list1.set(0, "banana x");
    System.out.println(list1);
    
    // 【4】查看
    System.out.println(list1.get(0));
    
}

}

LinkedList也实现了栈、队列、双向队列接口。
以栈的方式访问LinkedList


image.png

public class Test02 {
public static void main(String[] args) {

    // 以栈形式访问
    LinkedList stack1 = new LinkedList();
    
    // 入栈
    stack1.push("apple");
    stack1.push("banana");
    
    // 出栈
    System.out.println(stack1.pop());
    System.out.println(stack1.pop());
    
    // 如果栈中没有元素,抛出NoSuchElementException
    System.out.println(stack1.pop());
}

}

以队列(Queue接口)的方式访问LinkedList


image.png

public static void main(String[] args) {

    // 以队列形式访问
    LinkedList queue = new LinkedList();
    
    // 入队
    /*
    头(出口)<----------尾(入口)
    ---------------------
    apple banana coco
    ---------------------
    */
    //queue.add("apple");
    //queue.add("banana");
    //queue.add("coco");
    //System.out.println(queue);
    
    // 出队
    //queue.remove();
    //queue.remove();
    //queue.remove();
    // 抛出NoSuchElementException
    //queue.remove();
    //System.out.println(queue);
    
    
    // 检测元素:获取但不移除此列表的头(第一个元素)
    //System.out.println(queue.element());
    //System.out.println(queue.element());
    
    
    
    /*queue.offer("apple");
    queue.offer("banana");
    queue.offer("coco");*/
    System.out.println(queue);
    
    //queue.poll();
    //System.out.println(queue);
    //queue.poll();
    //queue.poll();
    // 如果队列为空,返回null
    //String item = (String)queue.poll();
    //System.out.println(item);
    
    System.out.println(queue.peek());
}

以双向队列(DeQue接口)方式访问LinkedList


image.png

public static void main(String[] args) {

    // 以双向队列形式访问
    LinkedList queue = new LinkedList();
    

    /*
     * 
    头                   尾
    <-------------------
    ---------------------
    apple banana coco
    ---------------------
    ------------------->
    
    */
    
    queue.addFirst("apple");
    queue.addLast("banana");
    queue.addLast("coco");
    
    //queue.removeFirst();
    //queue.removeLast();
    //queue.removeLast();
    
    // NoSuchElementException
    //queue.removeLast();
    //System.out.println(queue);

    System.out.println(queue.getFirst());
    System.out.println(queue.getLast());
}

1.6泛型(generic)
1.6.1泛型概念(A)
泛型允许程序员在强类型程序设计语言中编写代码时定义一些可变部分。
那些可变部分在使用前必须作出指明。形式
ArrayList<T> list = null;
表示声明了一个ArrayList容器,容器中存储的数据类型是T类型,T类型此时就是泛型。
T表示一种数据类型,但现在还不确定。

泛型在使用时,一定要确定类型。

ArrayList<String> list2 = new ArrayList<String>();
表示声明了一个ArrayList容器,容器中存储的数据类型是String类型。

泛型只在编译器起作用,运行时不知道泛型的存在。

1.6.2泛型擦除(C)
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();

    System.out.println(list instanceof ArrayList);
    System.out.println(list instanceof ArrayList<?>);
    System.out.println(list instanceof ArrayList<Integer>); //error
    
}

Cannot perform instanceof check against parameterized type ArrayList<Integer>. Use the form ArrayList<?> instead since further generic type information will be erased at runtime

泛型就是程序设计过程中将类型参数化。

1.6.3泛型类(A)
当一个类中的属性类型不确定时,此时可以把该属性声明为泛型。
public class Student<T> {
private T t;

public T getT() {
    return t;
}

public void setT(T t) {
    this.t = t;
}

}

思考:请设计一个容器,提供增删改查的方法?

1.6.4泛型方法(A)
当一个方法的形参参数类型不确定时,可以使用泛型。
public class Student{

/*
public void add(int a,int b) {
    System.out.println(a+b);
}

public void add(float a,float b) {
    System.out.println(a+b);
}

public void add(char a,char b) {
    System.out.println(a+b);
}

public void add(String a,String b) {
    System.out.println(a+b);
}
*/

public <T> void add(T a,T b) {
    System.out.println(a.toString()+b.toString());
}

}

泛型方法在一定程度上优化了方法重载,不能取代。

泛型的可变参数
// 方法的可变参数
/public void add(int...args) {
// 方法的可变参数在方法调用时,以args数组形式存在于方法中
System.out.println(Arrays.toString(args));
}
/

public <T> void add(T...args) {     
    System.out.println(Arrays.toString(args));
}

泛型的可变参数方法进一步优化了方法重载,不能完全取代。

1.6.5泛型接口(C)
当泛型接口中的方法类型(返回值、形参)不太确定,可以使用泛型接口。
public interface MyInterface<T> {
public void showInfo(T a);
}

实现类知道操作接口中方法的参数类型
public class ImplClass implements MyInterface<String>{

@Override
public void showInfo(String a) {
    // TODO Auto-generated method stub
    
}

}

实现类不知道实现接口中方法的参数类型,实现类继续泛下去。
public class ImplClass2<T> implements MyInterface<T>{

@Override
public void showInfo(T a) {
    // TODO Auto-generated method stub
    
}

}

1.6.6泛型的上限和下限(C)
[1]泛型上限
public static void print(ArrayList<? extends Pet> list) {
for(Pet pet:list) {
pet.showInfo();
}
}
<? extends A> 表示?必须A的子类,A作为上限已经确定。
ArrayList<? extends A> list 表示声明了一个容器list,list中存储的元素必须是A的子类。
[2]泛型下限
<? super A> 表示?必须A的父类,A作为下限已经确定。
ArrayList<? super A> list 表示声明了一个容器list,list中存储的元素必须是A的父类。

1.7Iterator和ListIterator (s)
读Iterator实现类源码(hasNext、next)

public static void main(String[] args) {

    ArrayList<String> list = new ArrayList<String>();
    list.add("apple");
    list.add("banana");
    list.add("coco");
    
    // 需求:在遍历的过程中,添加元素
    Iterator<String> it = list.iterator();
    while(it.hasNext()) {
        String item = it.next();
        if(item.equals("banana")) {
            // list.add("test");
        }
    }
    System.out.println(list);
    
    ListIterator<String> it2 = list.listIterator();
    while(it2.hasNext()) {
        String item = it2.next();
        if(item.equals("banana")) {
            it2.add("test");
        }
    }
    System.out.println(list);

}

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayListItr.checkForComodification(ArrayList.java:909) at java.util.ArrayListItr.next(ArrayList.java:859)
at cn.sxt06.iterator.Test01.main(Test01.java:18)
当遍历一个集合时,不能对集合进行添加操作,可能会出现并发修改异常。如果要对其进行添加操作,需要使用ListIterator接口。

1.8Set接口
Set接口表示的集合元素是无序、唯一的。
public static void main(String[] args) {
/**
* 增:add/addAll
* 删:clear/remove/removeAll/retainAll
* 改:
* 查:contains/containsAll/isEmpty/equals/size
* 遍历:iterator
*/

    Set<String> set = new HashSet<String>();
    // 【1】添加
    boolean r;
    r = set.add("apple");
    System.out.println(r);
    set.add("coco");
    set.add("banana");
    
    r =  set.add("apple"); // 没有添加成功
    System.out.println(r);
    
    // 【2】删除
    // set.clear();
    set.remove("coco");
    System.out.println(set);
}

set遍历
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
set.add("apple");
set.add("coco");
set.add("banana");

    // foreach
    for(String str:set) {
        System.out.println(str);
    }
    
    Iterator<String> it = set.iterator();
    while(it.hasNext()) {
        System.out.println(it.next());
    }
}

1.8.1HashSet
HashSet是Set接口的实现类,底层数据结构是哈希表。
HashSet 线程不安全。

1.8.1.1HashSet的工作原理
HashSet底层数据结构是哈希表/散列表


image.png

HashSet存储元素时
[1] 求元素的hash码
[2] equals比较集合是否存在相同元素。

思考:如何把自定义对象存入HashSet中?
package cn.sxt02.hashset;

public class Student {

private String id;
private String name;
private int age;

// …

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + age;
    result = prime * result + ((id == null) ? 0 : id.hashCode());
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    
    Student other = (Student) obj;
    if (age != other.age)
        return false;
    if (id == null) {
        if (other.id != null)
            return false;
    } else if (!id.equals(other.id))
        return false;
    if (name == null) {
        if (other.name != null)
            return false;
    } else if (!name.equals(other.name))
        return false;
    return true;
}

@Override
public String toString() {
    return "Student [id=" + id + ", name=" + name + ", age=" + age + "]";
}

}

总结:
[1]存入HashSet中的元素必须实现hashCode和equals方法
[2]元素的hashCode一样,经过y=k(x)散列出来的位置一定一样。元素的hashCode不一样,经过y=k(x)散列出来的位置有可能一样。
[3] 散列函数多半是 hashCode % 空间长度。为什么?

1.8.2LinkedHashSet
LinkedHashSet 是Set接口的实现类,底层数据结构是哈希表+链表,其中链表应用维持添加次序。

画LinkedHashSet工作原理图?

1.8.3TreeSet
TreeSet 是Set接口的实现类,底层数据结构是二叉树,按照自然升序存储。
TreeSet实现线程不安全的。

1.8.3.1TreeSet工作原理


image.png

TreeSet<Integer> set = new TreeSet<Integer>();
set.add(2);
set.add(3);
set.add(1);
set.add(4);
set.add(3);
System.out.println(set);

当向TreeSet存入一个元素时,
[1]把待添加的元素T和根节点比较,如果T小于根节点,T存入左子树;如果T大于根节点,T存入右子树
[2]一旦确定子树后,T元素要和子树根节点比较,重复[1]步骤,如果需要相等,丢弃T。

需求: 把自定义对象按年龄存入TreeSet中?

把自定义对象存入TreeSet中一定要提供比较策略,否则会出现ClassCastException异常。

比较策略分为两种,一种是内部比较器,一种是外部比较器。
1.8.3.2内部比较器
内部比较器就是实现Comparable接口
package cn.sxt04.treeset;
public class Student implements Comparable<Student>{

private String id;
private String name;
private int age;

 //  . . .
@Override
public int compareTo(Student o) {
    // 按照年龄比较
    if(this.getAge() < o.getAge()) {
        return -1;
    }else if(this.getAge() == o.getAge()) {
        return 0;
    }else {
        return 1;
    }
}

}

思考:把自定义对象按年龄升序存入treeset中,如果年龄一样,再按照名字自然升序。
@Override
public int compareTo(Student o) {

    // return this.getAge() - o.getAge();
    
    // 按照年龄比较
    if(this.getAge() < o.getAge()) {
        return -1;
    }else if(this.getAge() == o.getAge()) {
        
        /*if(this.getName().compareTo(o.getName()) < 0) {
            return -1;
        }else if(this.getName().compareTo(o.getName()) == 0) {
            return 0;
        }else {
            return 1;
        }*/
        
        return this.getName().compareTo(o.getName());
        
    }else {
        return 1;
    }
}

1.8.3.3外部比较器
当开发者不知道添加元素类的源代码时,此时可以使用外部比较策略。外部比较器就是Compartor接口。

public class Test04 {
public static void main(String[] args) {

    LenCompare lenCompare = new LenCompare();
    TreeSet<String> set = new TreeSet<String>(lenCompare);
    set.add("alex");
    set.add("ben");
    set.add("cocos");

    set.add("scott");

    // 需求:按照字符串的长度升序?
    System.out.println(set);

}

}

class LenCompare implements Comparator<String> {

@Override
public int compare(String o1, String o2) {
    // [1] 按名称长度升序
    // System.out.println("o1:"+o1);
    // System.out.println("o2:"+o2);
    // return o1.length() - o2.length();

    // [2] 先按照名称长度,如果相等,按名称自然顺序
    /*if (o1.length() == o2.length()) {
        return o1.compareTo(o2);
    }
    return o1.length() - o2.length();*/
    
    
    // [3]按照长度降序
    return o2.length() - o1.length();

}

}
package cn.sxt04.treeset;

import java.util.Comparator;
import java.util.TreeSet;

public class Test05 {
public static void main(String[] args) {

    LenCompare lenCompare = new LenCompare();
    
    TreeSet<String> set = new TreeSet<String>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.length() - o2.length();
        }
    });
    
    set.add("alex");
    set.add("ben");
    set.add("cocos");

    set.add("scott");

    // 需求:按照字符串的长度升序?
    System.out.println(set);

}

}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,378评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,356评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,702评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,259评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,263评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,036评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,349评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,979评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,469评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,938评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,059评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,703评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,257评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,262评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,501评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,792评论 2 345