[数据结构与算法]集合框架及背后的数据结构、Collection，Map、ArrayList的使用

一、类和接口总览

Java 集合框架的优点及作用

• 使用成熟的集合框架，有助于我们便捷、快速的写出高效、稳定的代码
• 学习背后的数据结构知识，有助于我们理解各个集合的优缺点及使用场景

二、Collection 接口

1、Collection 常用方法

• 将元素放入集合中、返回集合中的元素个数

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        System.out.println(collection.size()); // 2

        // 尖括号中 不能放简单的基本类型 一定是类类型
        Collection<Integer> collection1 = new ArrayList<>();
        collection1.add(10);
    }
}

• 删除集合中的所有元素、判断集合是否没有任何元素

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        System.out.println(collection); // [hello, world]
        collection.clear();
        System.out.println(collection); // []

        System.out.println(collection.isEmpty()); // true
    }
}

• 返回一个装有所有集合中元素的数组

不建议进行整体的强制类型转换

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        Object[] objects = collection.toArray();
        System.out.println(Arrays.toString(objects)); // [hello, world]
    }
}

• 如果元素 e 出现在集合中，删除其中一个

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("hello");
        collection.add("world");
        collection.remove("world");
        System.out.println(collection); // [hello]
    }
}

2、Map 接口

import java.util.ArrayList;
import java.util.Collection;

public class TestDemo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("及时雨", "宋江");
        map.put("豹子头", "林冲");

        System.out.println(map.isEmpty()); // false
        System.out.println(map.size()); // 2

        String ret = map.get("及时雨");
        System.out.println(ret); // 宋江
        // 没有找到用默认值代
        System.out.println(map.getOrDefault("花和尚", "鲁智深")); // 鲁智深

        System.out.println(map.containsKey("豹子头")); // true
        System.out.println(map.containsValue("林冲")); // true

        // 不是按顺序
        System.out.println(map); // {豹子头=林冲, 及时雨=宋江}

        Set<Map.Entry<String, String>> entrySet = map.entrySet(); // 把k v组装成一个整体

        for (Map.Entry<String, String> entry : entrySet) {
            System.out.println("key: "+entry.getKey()+" value:"+entry.getValue());
        }
    }
}

三、预备知识-泛型(Generic)

class MyArrayList<E>代表这个类是一个泛型类，此时的这个E，就是一个占位符而已

public class Test {
    public static void main(String[] args) {
        // 把类型 参数化了
        MyArrayList<String> myArrayList1 = new MyArrayList<>();
        MyArrayList<Integer> myArrayList2 = new MyArrayList<>();
        MyArrayList<Boolean> myArrayList3 = new MyArrayList<>();
    }

泛型的意义：
1. 自动对类型进行检查
2. 自动对类型进行了强制类性转换

class MyArrayList<E> {
    private E[] elem;
    private int usedSize;
    public MyArrayList() {
        this.elem = (E[])new Object[10];
    }
    public void add(E val) {
        this.elem[usedSize] = val;
        usedSize++;
    }
    public E get(int pos) {
        return this.elem[pos];
    }
}

public class Test {
    public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();
        myArrayList.add("ABC");
        myArrayList.add("bit");
        String ret = myArrayList.get(1);
        System.out.println(ret); // bit

        MyArrayList<Integer> myArrayList1 = new MyArrayList<>();
        myArrayList1.add(11);
        myArrayList1.add(22);
        int ret2 = myArrayList1.get(1);
        System.out.println(ret2); // 22
    }
}

• 泛型中尖括号中的内容，不参与类型的组成

关于Object[] 强制类型转换的思考

		// 前提：Object数组进行向下转换
		String[] strings = new String[10];
        Object o1 = new String[10];
        Object[] o2 = new String[10];

JAVA提高六：泛型

泛型是怎么编译的？

泛型是编译时期的一种机制，擦除机制（-> Object）

Creating a Generic Array in Java
使用泛型数组时的注意事项：
数组和泛型之间的一个重要区别是它们如何强制执行类型检查。 具体来说，数组在运行时存储和检查类型信息。 然而，泛型在编译时检查类型错误，并且在运行时没有类型信息。

四、预备知识-包装类(Wrapper Class)

public class TestDemo {
    public static void main(String[] args) {
        String str = "123";
        int ret = Integer.valueOf(str);
        System.out.println(ret+1); // 124
    }
}

装箱(boxing)和拆箱(unboxing)

public class TestDemo {
    public static void main(String[] args) {
        Integer a = 123; //装箱  装包【隐式的】
        int b = a; //拆箱  拆包【隐式的】
        System.out.println(a+" " + b); // 123 123

        System.out.println("=============");

        Integer a2 = Integer.valueOf(123); //显示地装包
        Integer a3 = new Integer(123); // 显示地装包

        int b2 = a2.intValue(); // 显示地拆包
        double d = a2.doubleValue(); // 显示地拆包
        int i = 10; // 显示地初始化
    }
}

一道面试题：

public class TestDemo {
    public static void main(String[] args) {
        Integer a = 128;
        Integer b = 128;
        System.out.println(a == b); // false
    }
}

五、List

public class Test {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(20);

        ArrayList<String> list2 = new ArrayList<>();
    }
}

1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

六、ArrayList使用

1、ArrayList的构造

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("hello");
        list.add("bit");
        list.add("haha");
        System.out.println(list);

        // 使用另外一个ArrayList对list3进行初始化
        ArrayList<String> list3 = new ArrayList<>(list);
    }
}

2、ArrayList的遍历

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("hello");
        list2.add("bit");
        list2.add("haha");
        // 重写了ToString()
        System.out.println(list2);
        System.out.println("================");
        for(int i = 0; i < list2.size(); i++) {
            System.out.print(list2.get(i)+" ");
        }
        System.out.println();
        System.out.println("==================");
        for (String s : list2) {
            System.out.print(s+" ");
        }
        System.out.println();
        System.out.println("========迭代器打印==========");
        Iterator<String> it = list2.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }

        System.out.println();
        System.out.println("========迭代器List相关打印==========");
        ListIterator<String> it2 = list2.listIterator();
        // Iterator<String> it2 = list2.listIterator();
        while (it2.hasNext()) {
            System.out.print(it2.next()+" ");
        }
    }
}

Iterator 和 ListIterator 的区别

• remove

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("hello");
        list2.add("bit");
        list2.add("haha");

        Iterator<String> it = list2.iterator();
        while (it.hasNext()) {
            String ret = it.next();
            if(ret.equals("hello")) {
                it.remove(); // 首先需要使用next方法迭代出集合中的元素 ，然后才能调用remove方法
            }else {
                System.out.print(ret + " ");
            }
        }

        ListIterator<String> it2 = list2.listIterator();
        while (it2.hasNext()) {
            String ret = it2.next();
            if(ret.equals("hello")) {
                it2.remove(); // 首先需要使用next方法迭代出集合中的元素 ，然后才能调用remove方法
            }else {
                System.out.print(ret + " ");
            }
        }
    }
}

• add
  Iterator没有add方法

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        // CopyOnWriteArrayList<String> list2 = new CopyOnWriteArrayList<>(); // 线程安全的
        list2.add("hello");
        list2.add("bit");
        list2.add("haha");

        ListIterator<String> it2 = list2.listIterator();
        while (it2.hasNext()) {
            String ret = it2.next();
            if(ret.equals("bit")) {
                it2.add("gaobo"); // 放到下一个
            }else {
                System.out.print(ret + " ");
            }
        }
        System.out.println("=================");
        System.out.println(list2);
        // hello haha =================
        // [hello, bit, gaobo, haha]
    }
}

3、ArrayList常见操作

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        // add方法，默认放到数组的最后一个位置
        System.out.println(list2); // [a, b, c]
        
        list2.add(0, "hello");
        System.out.println(list2); // [hello, a, b, c]

        ArrayList<String> list3 = new ArrayList<>();
        list3.add("我是测试List1");
        list3.add("我是测试List2");
        list3.add("我是测试List3");
        list2.addAll(list3); // [hello, a, b, c, 我是测试List1, 我是测试List2, 我是测试List3]
        System.out.println(list2);
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        String ret = list2.remove(0);
        System.out.println(ret); // a
        System.out.println(list2); // [b, c]

		boolean flag = list2.remove("c");
        System.out.println(flag); // true
        System.out.println(list2); // [b]
    }
}

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        String ret = list2.get(0);
        System.out.println(ret); // a
        System.out.println(list2); // [a, b, c]

        String ret2 = list2.set(0, "p");
        System.out.println("原来的字符串是："+ret2); // 原来的字符串是：a
        System.out.println(list2); // [p, b, c]

        // 判断是否包含"p"
        System.out.println(list2.contains("p")); // true

        // 查找下标
        System.out.println(list2.indexOf("c")); // 2

        System.out.println(list2.lastIndexOf("c")); // 2

        // 清空
        list2.clear();
        System.out.println(list2); // []
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        list2.add("f");
        list2.add("g");
        List<String> sub = list2.subList(1, 3);
        System.out.println(sub); // [b, c]

        sub.set(0, "bit");
        // 把截取的[b, c] 起始位置给了sub
        System.out.println(sub); // [bit, c]
        System.out.println(list2); // [a, bit, c, f, g]
    }
}

4、ArrayList的扩容机制

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>(); // 初始的大小是几？答案是0
        list1.add("bit"); // 当第一次存放数据元素的时候，顺序表被分配大小为10
        System.out.println(list1);
        ArrayList<String> list2 = new ArrayList<>(13); //初始大小是指定的13
    }

结论：

• 如果ArrayList调用，不带参数的构造方法，那顺序表的大小0，第一次add时，整个顺序表才变为了10
  当这10个放满了，开始扩容，以1.5倍的方式扩容
• 如果调用的是给定容量的构造方法，顺序表的大小就是你给定的容量，放满了还是以1,5倍进行扩容

5、模拟实现ArrayList

import java.util.Arrays;

class MyArrayList<E> {
    private Object[] elementData;//数组
    private int usedSize;//代表有效的数据个数

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public MyArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public MyArrayList(int capacity) {
        //对参数进行判断
        if(capacity > 0) {
            this.elementData = new Object[capacity];
        }else if(capacity == 0) {
            this.elementData = new Object[0];
        }else {
            throw new IllegalArgumentException("初始化的容量不能为负数");
        }
    }

    /**
     * 添加元素,相当于存放在了数组的最后位置
     * @param e 数据
     * @return
     */
    public boolean add(E e) {
        //确定一个真正的容量,预测->扩容【把检查顺序表空和满和扩容放到了一起】
        ensureCapacityInternal(usedSize+1);
        elementData[usedSize] = e;
        usedSize++;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        //1、计算出需要的容量
        int capacity = calculateCapacity(elementData,minCapacity);
        //2、拿着计算出的容量，去看，满了扩容。空的也是。给一个明确的容量
        ensureExplicitCapacity(capacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // 进不去if语句，数组还没有放满
        if (minCapacity - elementData.length > 0)
            //扩容了
            grow(minCapacity);
    }

    private static final int MAX_ARRAY_SIZE =  Integer.MAX_VALUE-8;

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5倍扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE> 0)
            //说明你要的容量非常大
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //1、是否之前elementData数组分配过大小
        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10,minCapacity);
        }
        //2、分配过 就返回+1后的值
        return minCapacity;
    }

    /**
     * 给index位置添加元素
     * @param index
     * @param e
     */
    public void add(int index,E e) {
        //1、检查下标是否合法
        rangeCheckForAdd(index);
        //2、确定真正的容量
        ensureCapacityInternal(usedSize+1);
        //3、挪数据
        copy(index,e);
        usedSize++;
    }

    private void copy(int index,E e) {
        for (int i = usedSize-1; i >= index ; i--) {
            elementData[i+1] = elementData[i];
        }
        elementData[index] = e;
    }

    private void rangeCheckForAdd(int index) {
        if(index < 0 || index > size()) {
            throw new IndexOutOfBoundsException("index位置不合法，不能插入！");
        }
    }

    /**
     * 获取顺序表的大小
     * @return
     */
    public int size() {
        return this.usedSize;
    }

}

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

    }
}

七、练习

1、自定义数据类型

比特科技有若干学生(学生对象放在一个List中)，每个学生有一个姓名(String)、班级(Strin和考试成绒属性(double)
某次考试结束后,每个学生都获得了一个考试成绩
遍历list集合,并把学生对象的属性打印出来

class Student {
    private String name;
    private String  classes;
    private double score;
    public Student(String name, String classes, double score) {
        this.name = name;
        this.classes = classes;
        this.score = score;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getClasses() {
        return classes;
    }
    public void setClasses(String classes) {
        this.classes = classes;
    }
    public double getScore() {
        return score;
    }
    public void setScore(double score) {
        this.score = score;
    }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", classes='" + classes + '\'' +
                ", score=" + score +
                '}';
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<Student> students = new ArrayList<>();
        students.add(new Student("bit", "102-1", 10.9));
        students.add(new Student("zhangsan", "102-2", 70.9));
        students.add(new Student("lisi", "102-1", 50.9));
        System.out.println(students);
    }
}

2、使用Collections排序

public static void main(String[] args) {
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(12);
        integers.add(53);
        integers.add(37);
        Collections.sort(integers); // [12, 37, 53]
        System.out.println(integers);
        Collections.reverse(integers);
        System.out.println(integers); // [53, 37, 12]
    }

3、Welcome to CVTE

删除第一个字符串中出现的第二个字符串中的字符
例：
String str1 = “welcome to CVTE”;
String str2 = “come”;
输出：wl t CVTE

public class Test {
    // 2
    public static void main2(String[] args) {
        // 用ArrayList
        String str1 = "welcome to CVTE";
        String str2 = "come";
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if(!str2.contains(ch+"")) {
                list.add(ch);
            }
        }
        // System.out.println(list); // [w, l,  , t,  , C, V, T, E]
        for (char ch : list) {
            System.out.print(ch);
        }
    }

    // 1
    public static void main(String[] args) {
        String str1 = "welcome to CVTE";
        String str2 = "come";
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if(!str2.contains(ch+"")) {
                sb.append(ch);
            }
        }
        System.out.println(sb);
    }
}

5、扑克牌

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Card {
    private int rank; // 数字
    private String suit; // 花色

    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public String toString() {
        return "[ "+this.suit+":"+this.rank+" ]";
    }
}

public class TestDemo {
    public static final String[] suits = {"?","?","?","?"};

    public static List<Card> budCard() {
        ArrayList<Card> cards = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                /*String suit = suits[i];
                int rank = j;
                Card card = new Card(rank, suit);
                cards.add(card);*/
                cards.add(new Card(j, suits[i]));
            }
        }
        return cards;
    }

    // 交换
    public static void swap(List<Card> cards, int i, int j) {
        Card tmp = cards.get(i);
        cards.set(i, cards.get(j));
        cards.set(j, tmp);
    }

    // 洗牌
    public static void shuffle(List<Card> cards) {
        int size = cards.size();
        for (int i = size - 1; i > 0; i--) {
            Random random = new Random();
            int rand = random.nextInt(i);
            swap(cards, i, rand);
        }
    }

    public static void main(String[] args) {
        List<Card> cards =  budCard();
        System.out.println("买牌"+cards);

        shuffle(cards);
        System.out.println("洗牌"+cards);

        System.out.println("揭牌：3个人每人轮流揭5张牌");

        ArrayList<List<Card>> hand = new ArrayList<>();

        List<Card> hand1 = new ArrayList<>();
        List<Card> hand2 = new ArrayList<>();
        List<Card> hand3 = new ArrayList<>();

        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                Card card = cards.remove(0);
                hand.get(j).add(card);
            }
        }

        System.out.println("第1个人的牌："+hand1);
        System.out.println("第2个人的牌："+hand2);
        System.out.println("第3个人的牌："+hand3);
        System.out.println("剩下的牌："+cards);
    }
}

6、杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        // 第一行
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        ret.add(list1); // 此时才把第一行的数据放到了ret中
        for (int i = 1; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1); // 每行开始都是1
            List<Integer> preRow = ret.get(i-1); // 上一行
            for (int j = 1; j < i; j++) {
                int num = preRow.get(j) + preRow.get(j-1);
                list.add(num);
            }
            list.add(1); // 结尾都是1
            ret.add(list);
        }
        return ret;
    }
}