侧边栏壁纸
博主头像
coydone博主等级

记录学习,分享生活的个人站点

  • 累计撰写 306 篇文章
  • 累计创建 51 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

List和Set

coydone
2021-02-04 / 0 评论 / 0 点赞 / 370 阅读 / 11,900 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

对象数组

对象数组指的就是存储引用类型的数组。

对象数组的使用

/*
 *对象数组(引用数组):该数组中存储的是引用类型因此我们叫它对象数组或者引用数组
 *  引用数组中存储的是对象的地址值而不是对象
 */
public class Demo {
    public static void main(String[] args) {
        //1.定义一个Student类型的数组
        //int[]  arr = new int[3]
        Student[] stus=new Student[2];

        //2.给数组中的元素赋值
        //arr[0]=3;
        stus[0]=new Student("张三",13);
        stus[1]=new Student("李四",24);

        //3.遍历这个引用数组
        /*
         * for(int i=0;i<arr.length;i++){
         *    System.out.println(arr[i])
         * }
         */
        for(int i=0;i<stus.length;i++){
            System.out.println(stus[i]);
        }
    }
}

内存图

List体系

List接口介绍

API中介绍:有序的 collection(也称为序列)。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素。与 set 不同,列表通常允许重复的元素

List接口:

  • 它是一个元素存取有序的集合。例如,存元素的顺序是11、22、33。那么集合中,元素的存储就是按照11、22、33的顺序完成的)。

  • 它是一个带有索引的集合,通过索引就可以精确的操作集合中的元素(与数组的索引是一个道理)。

  • 集合中可以有重复的元素,通过元素的equals方法,来比较是否为重复的元素。

  • List接口的常用子类有:ArrayList、LinkedList

ArrayList类

ArrayList是List接口的实现类,ArrayList底层是用数值实现的存储。特点:查询效率高,增删改效率低,线程不安全。

ArrayList实现原理

ArrayList集合特点:底层使用是一个引用数组(Object[])

扩容思想:创建一个ArrayList的时候,底层会生成一个空数组,当使用add()方法添加时,底层会开辟长度为10的数组,采用的是延迟初始化,调用add()方法会不断的往数组中添加元素当添加了10个元素。再添加第11个元素的时候,数组满了,无法存入,此时会新建一个长度为原来长度1.5倍的数组(10+10/2),接着会把原有元素拷贝到新数组中,再把第11个元素追加到末尾。

ArrayList中特有方法

增加元素方法
  add(Object e):向集合末尾处,添加指定的元素 
  add(int index, Object e):向集合指定索引处,添加指定的元素,原有元素依次后移
删除元素删除
  remove(Object e):将指定元素对象,从集合中删除,返回值为被删除的元素
  remove(int index):将指定索引处的元素,从集合中删除,返回值为被删除的元素
替换元素方法
  set(int index, Object e):将指定索引处的元素,替换成指定的元素,返回值为替换前的元素
查询元素方法
  get(int index):获取指定索引处的元素,并返回该元素 

方法演示:

import java.util.ArrayList;
public class Demo {
    public static void main(String[] args) {
        //list中可以存储任意数据类型,必须是对象
        ArrayList list = new ArrayList();
        list.add(12);//12是Integer一个对象,自动装箱
        list.add("abc");
        list.add("def");
        list.add("abc");
        System.out.println(list);//[12, abc, def, abc]
        list.add(3,"zzz");
        System.out.println(list);//[12, abc, def, zzz, abc]
        System.out.println( list.get(1));//abc
        list.set(3,"www");
        System.out.println(list);//[12, abc, def, www, abc]
        list.remove("abc");
        System.out.println(list);//[12, def, www, abc]
    }
}

ArrayList存储自定义对象

public class Person {
    private int id;
    private String name;
    //省略构造方法、setter()、getter()、toString()
}
 ​
import java.util.ArrayList;
import java.util.Iterator;
public class PersonDemo {
    public static void main(String[] args) {
        ArrayList<Person> list = new ArrayList<Person>();
        list.add(new Person(01,"张三"));
        list.add(new Person(02,"李四"));
        Iterator it = list.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
        //Person{id=1, name='张三'}
        //Person{id=2, name='李四'}
    }
}

ArrayList特点

查询元素较快:因为底层是数组,数组有索引。

增删元素较慢:添加慢,因为每次添加都需要移动大量的元素,导致浪费内存资源,效率低。

添加慢的原因:

删除慢的原因:

Vector类

Vector底层是用数组实现的,相关的方法都加了同步检查,因此“线程安全,效率低”。比如,indexOf()方法就增加了synchronized同步标记。

Vector的使用与ArrayList是相同的,因为他们都实现了List接口,对List接口中的抽象方法做了具体实现。

Vector底层初始化数组采用的是立即初始化的方式,当创建Vector时底层就会创建长度为10的数组。Vector扩容是采用2倍的方式进行扩容。

Stack

Stack栈容器,是Vector的一个子类,它实现了一个标准的后进先出(LIFO:Last In First Out)的栈。

特点:后进先出。它通过5个操作方法对Vector进行扩展,允许将向量视为堆栈。

操作栈的方法:

public class Test {
    public static void main(String[] args) {
        //实例化栈容器
        Stack<String> stack = new Stack<>();
        //入栈
        stack.push("aa");//返回值为该元素 aa
        stack.push("bb");
        stack.push("cc");
        //查看栈顶的元素
        System.out.println(stack.peek()); //cc
        //查询对象在栈中的位置,从1开始计数,栈顶为1
        System.out.println(stack.search("aa")); //3
        //弹栈
        System.out.println(stack.pop()); //cc
    }
}

使用Stack判断元素对称性

//匹配符号的对称性
public static void symmetry() {
    String str = "...{..{..[..()..]..}..}...";
    Stack<String> stack = new Stack<>();
    boolean flag = true; //假设是对称的
    //拆分字符串获取字符
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (c == '{') {
            stack.push("}");
        }
        if (c == '[') {
            stack.push("]");
        }
        if (c == '(') {
            stack.push(")");
        }
        //判断符号是否匹配
        if (c == '}' || c == ']' || c == ')') {
            if (stack.empty()) {
                flag = false;
                break;
            }
            String pop = stack.pop();
            if (pop.charAt(0) != c) {
                flag = false;
                break;
            }
        }
    }
    if (!stack.empty()) {
        flag = false;
    }
    System.out.println(flag);
}

LinkedList类

LinkedList底层用双向链表实现的存储。特点:查询效率低,增删效率高,线程不安全。

双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向前一个节点和后一个节点。所以,从双向链表中的任意一个节点开始,都可以很方便地找到所有节点。

双向链表

LinkedList实现思想

底层使用一个链表,第一个元素记录下一个元素的地址值最终形成一条链子。

LinkedList特有方法

LinkedList特点

查询元素相对ArrayList较慢:因为链表都是从头开始查。

增删元素相对ArrayList较快:因为链表仅仅需要改变元素中记录的地址值,而不需要移动大量元素,节省内存开销提高效率。

栈和队列数据结构

  • 栈:元素后进先出(先进后出),如手枪弹夹。

  • 队列:元素先进先出(后进后出),如银行叫号。

LinkedList增删元素原理:

Set体系

学习Collection接口时,记得Collection中可以存放重复元素,也可以不存放重复元素,那么我们知道List中是可以存放重复元素的。那么不重复元素给哪里存放呢?那就是Set接口,它里面的集合,所存储的元素就是不重复的。

Set接口继承自Collection,Set接口中没有新增方法,方法和Collection保持完全一致。

Set接口介绍

Set特点:无序、不可重复。无序指Set中的元素没有索引,我们只能遍历查找;不可重复指不允许加入重复的元素。更确切地讲,新元素如果和Set中某个元素通过equals()方法对比为true,则只能保留一个。

Set常用的实现类有:HashSet、TreeSet等,我们一般使用HashSet。

HashSet类

HashSet是一个没有重复元素的集合,不保证元素的顺序,是线程不安全的。而且HashSet 允许有null元素。HashSet是采用哈希算法实现,底层实际是用HashMap实现的(HashSet本质就是一个简化版的HashMap,底层将值存在HashMap的key中),因此,查询效率和增删效率都比较高。

无序:在HashSet 中底层是使用HashMap存储元素的。HashMap底层使用的是数组与链表实现元素的存储。元素在数组中存放时,并不是有序存放的也不是随机存放的,而是对元素的哈希值进行运算决定元素在数组中的位置。

不重复:当两个元素的哈希值进行运算后得到相同的在数组中的位置时,会调用元素的equals()方法判断两个元素是否相同。如果元素相同则不会添加该元素,如果不相同则会使用单向链表保存该元素。

HashSet基本使用

HashSet依然具有集合通用的特点:利用add添加元素,使用迭代器遍历,使用增强for遍历。

方法列表:

 add()       remove()        contains()      clear()     size()
  • Set无序,所有没有下标的获取方式。因此没有get(i)。

  • Set中不能查看一个元素

/*
 * Set接口:没有索引,存储的元素唯一,存取顺序不一定一致
 *   HashSet:没有索引,保证元素唯一,存的顺序和取的顺序不一定一致
 *   成员方法:
 *     Iterator<E> iterator() 
 */
import java.util.HashSet;
import java.util.Iterator;
public class Demo {
    public static void main(String[] args) {
        HashSet<String> hs=new HashSet<String>();
        hs.add("aa");
        hs.add("bb");
        hs.add("cc");
        //1.获取迭代器对象
        Iterator<String> it=hs.iterator();
        //2.循环遍历
        //迭代器
        while(it.hasNext()){
            String str=it.next();
            System.out.println(str);
        }
        /*增强for
        for(String str : hs){
            System.out.println(str);
        }
        */
    }
}
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
//Set集合过滤字符串
public class Demo {
    //Scanner输入字符串去重
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入字符串:");
        String str = input.nextLine();
        //1.String-->Char[]
        char[] cs = str.toCharArray();
        //2.Set集合
        Set<Character> set = new HashSet<>();
        //3.将每个字符放在Set中
        for (int i = 0 ; i < cs.length ; i++){
            set.add(cs[i]);//add()自带过滤重复
        }
        System.out.println(set);
    }
}

add():判断对象是否重复,依赖contains()。

contains():底层依赖equals(),重写equals()就能在Set集合中解决对象重复的问题

哈希算法

哈希算法,也称之为散列算法。Hash算法相对于普通查找更快。

哈希算法保证唯一原理

HashSet存入字符串保证唯一原理

存入HashSet的字符串依赖两个方法,一个是hashCode()方法,一个是equals()方法,注意这两个方法出自Object类,但是String都把这两个方法重写了,String的类的hashCode()方法不再像Object类的hashCode()方法返回内存地址值,而是根据一定的算法计算字符串中字符的ASCII码值,String类的equals()方法就是比较两个字符串的内容。

import java.util.HashSet;
/*
 * HashSet唯一原理
 *   先调用hashCode()方法比较元素的哈希值
 *   如果添加的元素哈希值与集合中的元素的哈希值不同,直接存入
 *   如果添加的元素哈希值与集合中的元素的哈希值相同
 *      调用equals()方法比较两个元素的内容
 *         equals()返回true,说明两个元素内容相同,认为重复,不存
 *         equals()返回false,说明两个元素内容不同,存
 *   Object类中原始的hashCode()返回的就是内存地址值
 */
public class Demo {
    public static void main(String[] args){
        HashSet<String> hs=new HashSet<String>();
        hs.add("ab");//当存入第一个ab时候直接存入
        hs.add("ab");//当存入第二ab的时候,先调用hashCode()方法获取两个元素哈希值,比较发现相同
        //在调用equals方法比较,"ab".euqlas("ab")//true,第二个ab就不存

        hs.add("bc");//当存入bc的时候,先调用hashCode()方法获取两个元素哈希值
        //比较发现不同,直接存入    
        System.out.println(hs);//[ab, bc]
        System.out.println("ab".hashCode());//3105
        System.out.println("bc".hashCode());//3137
    }
}

HashSet存取自定义对象保证唯一原理

当我们存储自定义对象中出现同名同年龄的,利用HashSet不能去重。因为Person利用的是从Object类中继承的hashCode方法,获取的是元素的地址值比较,而每个Person都是新new的Person,地址值均不同。

public class Person /*extends Object*/ {
    private String name;
    private int age;
	//省略构造方法、getter、setter方法
}

import java.util.HashSet;
/*
 * 利用HashSet存储自定义对象
 */
public class PersonDemo {
    public static void main(String[] args) {
        //1.创建HashSet集合
        HashSet<Person> hs=new HashSet<Person>();

        //2.创建3个Person对象
        /*Person p=new Person("张三",12);
         *hs.add(p);
         */
        hs.add(new Person("张三",12));//匿名对象
        hs.add(new Person("张三",12));//调用hashCode()方法获取哈希值(内存地址值),去比较
        //第二个Person对象的哈希值和第一个Person的哈希值不同
        //第二个Person直接存入
        hs.add(new Person("王五",16));

        //3.遍历HashSet集合
        for(Person p : hs){
            System.out.println(p.getName()+" "+p.getAge());
        }
        //张三 12
        //张三 12
        //王五 16
    }
}

我们尝试改写(重写)原有的hashCode()与equals()方法保证同名同年龄的人被过滤掉。

public class Person /*extends Object*/ {
    private String name;
    private int age;
    //省略构造方法、getter、setter方法
    
    /*我们在重写hashCode()一般用上这个类的所有属性来产生哈希值*/
	/*@Override
	public int hashCode() {
		 //return 10;
		return name.hashCode() + age;
	}*/
    /*
     *return 10,让所有元素都产生了相同哈希值,所有元素都得去调用
     *equals()比较
     * 对于new Person("张三", 12)还有new Person("王五", 16)
     *  两者的姓名和年龄都不同,没必要再去调用equals比较
     */

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

    /*
     * euqual方法的重写与之前的相同
     *  如果两个人的姓名和年龄均相同,认为是同一个人,返回true
     *  如果两个人的姓名和年龄至少有一个不同返回false
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Person other = (Person) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
}

import java.util.HashSet;
public class PersonDemo {
    public static void main(String[] args) {
        // 1.创建HashSet集合
        HashSet<Person> hs = new HashSet<Person>();

        // 2.创建3个Person对象
        Person p1=new Person("张三", 12);
        Person p2=new Person("张三", 12);
        Person p3=new Person("王五", 16);
        hs.add(p1);//p1直接存入
        hs.add(p2);//存入p2,需要调用hashCode()方法获取p1,p2的哈希值
        //哈希值相同,需要再去比较equals(),返回true,认为相同元素,不存
        hs.add(p3);//存入p3,需要调用hashCode()方法获取p3,p1的哈希值
        //不同,直接将p3存入

        System.out.println(p1.hashCode());//776222
        System.out.println(p2.hashCode());// 776222
        System.out.println(p3.hashCode());// 938522

        // 3.遍历HashSet集合
        for (Person p : hs) {
            System.out.println(p.getName() + " " + p.getAge());
        }
        //王五 16
        //张三 12
    }
}

TreeSet类

TreeSet是一个可以对元素进行排序的容器。底层实际是用TreeMap实现的,内部维持了一个简化版的TreeMap,通过 key来存储Set的元素。TreeSet内部需要对存储的元素进行排序,因此,我们需要给定排序规则。

排序规则实现方式:通过元素自身实现比较规则、通过比较器指定比较规则。

通过元素自身实现比较规则

在元素自身实现比较规则时,需要实现Comparable接口中的compareTo()方法,该方法中用来定义比较规则。TreeSet 通过调用该方法来完成对元素的排序处理。

class User implements Comparable<User> {
    private String name;
    private Integer age;
	//省略有参构造方法、getter()、setter()、toString()

    //定义比较规则:正数 大,负数 小,0 相等
    @Override
    public int compareTo(User o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        return -1;
    }
}
public class Test {
    public static void main(String[] args) {
        Set<User> set = new TreeSet<>();
        set.add(new User("张三",18));
        set.add(new User("李四",15));
        for (User user : set) {
            System.out.println(user);
        }
    }
}

通过比较器实现比较规则

通过比较器定义比较规则时,我们需要单独创建一个比较器,比较器需要实现Comparator接口中的compare()方法来定义比较规则。在实例化Treeset时将比较器对象交给TreeSet来完成元素的排序处理。此时元素自身就不需要实现比较规则了。

class User {
    private String name;
    private Integer age;
	//省略有参构造方法、getter()、setter()、toString()
}

class UserComparator implements Comparator<User> {

    @Override
    public int compare(User o1, User o2) {
        if (o1.getAge() > o2.getAge()) {
            return 1;
        }
        return -1;
    }
}

public class Test {
    public static void main(String[] args) {
        Set<User> set = new TreeSet<>(new UserComparator()); //传入比较器
        set.add(new User("张三",18));
        set.add(new User("李四",15));
        for (User user : set) {
            System.out.println(user);
        }
    }
}

队列和栈

Queue、Deque

队列(Queue)是一种特殊的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端( front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

LinkedList是Queue接口的实现类

boolean add(E e):将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回true,如果当前没有可用的空间,则抛出IllegalStateException。

E element():获取,但是不移除此队列的头。

boolean offer(E e):将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于add(E),后者可能无法插入元素,而只是抛出一个异常。

E peek():获取但不移除此队列的头;如果此队列为空,则返回null。

E poll():获取并移除此队列的头,如果此队列为空,则返回null。

E remove():获取并移除此队列的头。

Queue<String> queue = new LinkedList<>();
queue.add("aa");
queue.add("bb");
queue.add("cc");
System.out.println(queue.peek()); //aa

Deque:一个线性Collection,支持在两端插入和移除元素。此接口既支持有容量限制的双端队列,也支持没有固定大小限制的双端队列。接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。

Deque<String> deque = new LinkedList<>();
deque.add("aa");
deque.add("bb");
deque.add("cc");
System.out.println(deque.getFirst()); //aa

Stack

Stack:Stack类代表最后进先出(LIFO)堆栈的对象。它扩展了类别Vector与五个操作,允许一个向量被视为堆栈。设置在通常的push和pop操作,以及作为一种方法来peek在堆栈,以测试堆栈是否为empty的方法,以及向search在栈中的项目的方法在顶部项目和发现多远它是从顶部。

Stack<String> stack = new Stack<>();
//压栈
stack.push("aa");
stack.push("bb");
stack.push("cc");
0

评论区