java中集合(Collection部分)

集合的继承结构

要点

集合在java中是一个容器，一个对象。集合不能直接存储基本数据类型，也不能直接存储java对象，
集合当中存储的都是java对象的内存地址（引用）
    list.add(100);//100自动装箱成Integer类型

java中每一个不同的集合底层对应不同的数据结构，往不同集合中存储元素就是将数据放到了不同的数据结构中。
数据结构是数据存储的结构，不同数据结构，数据存储方式不同。
java已经将常见的数据结构实现了封装成集合类，我们只需要学会怎么调用集合类即可

在java中集合分为两大类:
一类是单个方式存储元素:
    这一类集合中超级父接口:java.util.Collection;
一类是以键值对的方式存储元素
    这一类集合中超级父接口:java.util.Map;
Collection集合和Map集合没有关系，二者独立存在。

Collection继承结构图(常用部分)

Map继承结构图(常用部分)：

Collection中的常用方法

要点

1、Collection能存放什么类型?
没有使用“泛型”之前, Collection中可以存储Object的所有子类型。(集合中不能直接存储基本数据类型,也不能存java对象,只是存储java对象的内存地址。)
使用了“泛型”之后, Collection中只能存储某个具体的类型。

2、Collection 中的常用方法
boolean add(Object e)   向集合中添加元素
int size()  获取集合中元素的个数
void clear()    清空集合
boolean contains(Object o)  判断当前集合中是否包含元素o ,包含返回true，不包含返回false
    contains方法在底层调用equals方法进行比对判断集合中是否包含某个元素。

boolean remove(Object o)    删除集合中的某个元素。
    remove方法在底层调用equals方法进行比对判断集合中是否包含某个元素。

boolean isEmpty()   判断该集合中元素的个数是否为0
Object[] toArray()  调用这个方法可以把集合转换成数组。[作为了解，使用不到]

实例一

public class CollectionTest01 {
    public static void main(String[] args) {
        //创建一个集合对象
        //Collection c = new Collection(); //接口是抽象的,无法实例化。
        //多态
        //Collection c = new ArrayList();
        //测试collection 接口中的常用方法
        c.add(1200); //自动装箱(java5的新特性。),实际上是放进去了一个对象的内存地址。Integer x = new Integer(1200)
        c.add(3.14); //自动装箱
        c.add(new Object());
        c.add(new Student());
        c.add(new Object());
        c.add(new Student());
        c.add(true); //自动装箱

        //获取集合中元素的个数
        System.out.println("集合中元素个数是:"+ c.size()); // 5
        //清空集合
        c.clear();
        System.out.println("集合中元素个数是:"+ c.size()); //0
        //再向集合中添加元素
        c.add("hello");// "hello"对象的内存地址放到了集合当中。
        c.add("wor1d");
        c.add("浩克");
        c.add("绿巨人");
        c.add(1);
        boolean flag2 = c.contains("绿巨人2")
        System.out.println(flag2); // false
        System.out.print1n(c. contains(1)); // true
        System.out.println("集合中元素个数是:"+ c.size()); // 5.

        //删除集合中某个元素
        c.remove(1);
        System.out.println("集合中元素个数是:"+ c.size()); // 4
        //判断集合是否为空(集合中是否存在元素)
        System.out.println(c.isEmpty()); // false
        //清空
        c.clear();
        System.out.println(c.isEmpty()); // true( true表示集合中没有元素了! )

        c.add("abc");
        c.add("def");
        c.add(100);
        c.add("hellowor1d!");
        //转换成数组
        Object[] objs = c.toArray();

        for(int i = 0; i < objs.1ength; i++){
            //遍历数组
            Object o= objs[i];
            System.out.print1n(o);
        }
    }
}
class Student {
    //todo...
}

关于集合当中的遍历/迭代

Iterator iterator(); 获取集合所依赖的迭代器对象
通过迭代器中方法完成集合的迭代(遍历)。
boolean hasNext() 如果还有元素可以迭代，则返回true。
Object next()返回迭代的下一个元素。
    
注意：这种方式是所有集合子类通用的遍历方式。

关于集合元素的remove
    重点:当集合的结构发生改变时，迭代器必须重新获取，如果还是用以前老的迭代器，会出现异常: 
    java.util.ConcurrentModificationException

    重点:在迭代集合元素的过程中，一定要使用迭代器Iterator的remove方法，删除元素，
    不能调用集合对象的remove方法删除元素，会出现: java.util.ConcurrentModificationException
    

实例一

public class CollectionTest02{
    
    public static void main(String[] args){
        
        //创建集合对象
        Collection c = new ArrayList();
        
        //添加元素
        c.add(100); //自动装箱
        c.add(3.14); //自动装箱
        c.add(false);//自动装箱
        
        
        //迭代,遍历
        //1.获取迭代器对象
        //不需要关心底层集合的具体类型，所有集合依赖的迭代器都实现了java.util.Iterator;接口
        Iterator it = c.iterator();
        //迭代器是面向接口编程.
        //it是引用，保存了内存地址，指向堆中的“迭代器对象”
        
        //2.开始调用方法，完成遍历，迭代。
        //while循环
        /*
        while(it.hasNext()){
            Object element = it.next();
            System.out.println(element); //100 3.14 false
        }
        */
        
        /*
            boolean b = it.hasNext(); 判断是否有更多的元素，如果有返回true
            Object o = it.next(); 将迭代器向下移动一位，并且取出指向的元素.
            
            原则：调用it.next()方法之前必须调用it.hasNext();
        */
                    
        //for循环
        for(Iterator it = c.iterator()){
            if(it.hasNext()){
                Object o = it.next();
                System.out.println(o);
        }      
    }
}

实例二

public class CollectionTest03{
    public static void main(String[] args) {
        //创建集合
        Collection c = new ArrayList();
        //注意:此时获取的迭代器，指向的是那是集合中没有元素状态下的迭代器。
        //注意:集合结构只要发生改变，迭代器必须重新获取。
        //当集合结构发生了改变，迭代器没有重新获取时，调用next()方法时:java.util.ConcurrentModificationException
        Iterator it = c.iterator();

        //添加元素
        c.add(1); // Integer类型
        C.add(2);
        c.add(3);

        Collection c2 = new ArrayList();
        c2.add("abc");
        c2.add("def");
        c2.add("xyz");
        Iterator it2 = c2.iterator();
        while(it2.hasNext()){
            Object o = it2.next();
            //删除元素
            //删除元素之后,集合的结构发生了变化,应该重新去获取迭代器
            //但是,循环下一次的时候并没有重新获取迭代器,所以会出现异常:java.util.ConcurrentModificationException
            //出异常根本原因是:集合中元素删除了,但是没有更新迭代器(迭代器不知道集合变化了)
            //c2.remove(o); //直接通过集合去删除元素,没有通知迭代器。( 导致迭代器的快照和原集合状态不同。)
            //使用迭代器来删除可以吗?
            //用迭代器删除时，会自动更新迭代器，并且更新集合(删除集合中的元素)。

            it2.remove(); //删除的一定是迭代器指向的当前元素。
            System.out.println(o);
        }
        System.out.println(c2.size()); //0
    }
}
    

迭代器迭代原理

集合中不能直接存储基本数据类型，只能存储引用数据类型。为了方便理解迭代器原理，下图所画的在集合中直接存储了数据，其实存储的是引用。

contains方法的原理

boolean contains(Object o)
判断集合中是否包含某个对象o
如果包含返回true，如果不是包含返回false。

contains方法在底层调用equals方法进行比对判断集合中是否包含某个元素。

注意：
remove方法在底层也调用equals方法进行比对判断集合中是否包含某个元素。

所以存放在一个集合中的类型一定要重写equals()方法！！！
因为Object中的equals方法比较内存地址，在现实的业务逻辑当中应该比较内容。

实例

public class CollectionTest03{
    public static void main(String[] args) {
        //创建集合对象
        Collection C = new ArrayList();

        //向集合中存储元素
        String s1 = new String("abc"); // s1 = 0x1111
        c.add(s1); //放进去了一个"abc"
        String s2 = new String("def"); // s2 = 0x2222
        c.add(s2);

        //集合中元素的个数
        System.out.println("元素的个数是:"+ c.size()); // 2

        //新建的对象String
        String x = new String("abc"); // x = 0x5555
        // c集合中是否包含x?结果猜测一下是true还是false?
        System.out.println(c.contains(x)); //判断集合中是否存在"abc" true
    }
}

内存图分析

List

List中的常用接口

测试List接口中常用方法
    1、List集合存储元素特点:有序可重复
        有序:List集合中的元素有下标，从0开始,依次递增。
        可重复:存储一个1,还可以再存储1。
    2、List既然是Collection接口的子接口,那么肯定list接口有自己“特色”的方法:
        以下只列出List接口特有的常用的方法:
            void add(int index, Object element)
            Object set(int index, Object element)
            Object get(int index)
            int indexOf(Object o)
            int lastIndexOf(Object o)
            Object remove(int index)

实例一

public class CollectionTest03{
    public static void main(String[] args) {
        //创建List类型的集合。
        //List myList = new LinkedList();
        //List myList = new Vector();
        List myList = new ArrayList();
        //添加元素
        myList.add("A"); //默认都是向集合未尾添加元素。
        myList.add("B");
        myList.add("C");
        myList.add("C");
        myList.add("D");
        
        //在列表的指定位置插入指定元素(第一个参数是下标)
        //这个方法使用不多，因为对Arraylist集合来说效率比较低。
        myList.add(1,"KING" );
        //迭代
        Iterator it = myList.iterator();

        while(it.hasNext()){
        Object elt = it.next();
        System.out.println(elt);
        }

        //根据下标获取元素
        Object firstObj = myList.get(0);
        System.out.println(firstObj);
        //因为有下标，所以List集台有自己比较特殊的遍历方式
        //通过下标遍历，List集合特有的方式，Set没有。
        for(int i = 0; i < myList.size(); i++){
            Object obj = myList.get(i);
            System.out.println(obj);
        }

        //获取指定对象第一次出现处的索引。
        System.out.println(myList.indexOf("C")); // 3
        //获取指定对象最后一次出现处的索引。
        System.out.println(myList.lastIndexOf("C")); // 4
        //删除指定下标位置的元素
        //删除下标为0的元素
        myList.remove(0);
        System.out.println(myList.size()); // 5

        System.out.println("=============================");
        //修改指定位置的元素
        myList.set(2, "Soft");
        //遍历集合
        for(int i = 0; i < myList.size(); i++){
            Object obj = myList.get(i);
            System.out.println(obj);
        }
    }
}

ArrayList

ArrayList集合: 
1、默认初始化容量10(底层先创建了一个长度为0的数组，当添加第一个元素的时候，初始化容量10。)
2、集合底层是一个Object[]数组。
3、构造方法:
    new ArrayList(); 
    new ArrayList(int);
4、ArrayList集合的自动扩容:
    增长到原容量的1.5倍。
    ArrayList集合底层是数组,怎么优化?
        尽可能少的扩容。因为扩容需要数组拷贝。数组拷贝很耗内存，数组扩容效率比较低。
        建议在使用ArrayList集合的时候预估计元素的个数，给定一个初始化容量。
5、数组优点:
    检索效宰比较高。( 每个元素占用空间大小相同，内存地址是连续的，知道首元素内存地址，
    然后知道下标，通过数学表达式计算出元素的内存地址，所以检索效率最高。)
6、数组缺点:
    随机增删元素效率比较低。
    数组无法存储较大数据量（很难找到一块巨大的连续的内存空间。）
7、向数组末尾添加元素，效率很高，不受影响。
8、面试官经常问的一个问题?
    这么多的集合中，你用哪个集合最多?
        答:ArrayList集合。
        因为往数组末尾添加元素，效率不受影响。
        另外，我们检索/查找某个元素的操作比较多。
9、ArrayList是非线程安全的。

LinkedList

LinkedList底层是双向链表

链表的优点:
由于链表上的元素在空间存储上内存地址不连续。
所以随机增删元素的时候不会有大量元素位移，因此随机增删效率较高。
在以后的开发中，如果遇到随机增删集合中元素的业务比较多时，建议使用Linkedlist。

链表的缺点:
不能通过数学表达式计算被查找元素的内存地址，每一次查找都是从头节点开始遍历，直到找到为止。
所以LinkedList集合检索/查找的效率较低。

ArrayList: 把检索发挥到极致。（末尾添加元素效率还是比较高的）
LinkedList: 把随机增删发挥到极致。

加元素一般都是往末尾添加，所以ArrayList用的比LinkedList多。

实例

public class LinkedListTest01 {
    public static void main(String[] args) {
        // LinkedList集合底层也是有下标的。
        // 注意:ArrayList之所以检索效率比较高,不是单纯因为下标的原因。是因为底层数组发挥的作用。
        // Linkedlist 集合照样有下标，但是检索/查找某个元素的时候效率比较低,因为只能从头节点开始一个一个遍历。

        // LinkedList集合有初始化容量吗?没有。
        //最初这个链表中没有任何元素。first和last引用都是null。
        //不管是LinkedList还是Arraylist，以后写代码时不需要关心具体是哪个集合。
        //因为我们要面向接口编程，调用的方法都是接口中的同名方法。
        //List list2 = new ArrayList(); //这样写表示底层你用了数组。
        List list2 = new LinkedList(); //这样写表示底层你用了双向链表。

        //以下这些方法你面向的都是接口编程。
        list2.add("123");
        list2.add("456");
        list2.add("789"); 

        for(int i = 8; i < list2.size(); i++){
            System.out.println(list2.get(i));
}
}

Vector

Vector :
    1、底层也是一个数组。
    2、初始化容量:10
    3、怎么扩容的?：扩容之后是原容量的2倍。10-->20 -->40 --> 80
    4、ArrayList集合扩容特点: ArrayList集合扩容是原容量1.5倍。
    5、Vector中所有的方法都是线程同步的，都带有synchronized关键字是线程安全的。效率比较低，使用较少了。
    6、怎么将一个线程不安全的ArrayList集合转换成线程安全的呢?
        使用集合工具类:
        java.util.Collections;
        java.util.Collection是集合接口。
        java.util.Collections是集合工具类。
        eg：将ArrayList对象myList变成线程安全的： Collections.synchronizedList(myList);

实例

public class VectorTest {
public static void main(String[] args) {
    //创建一个Vector集合
    List vector = new Vector();
    //Vector vector = new Vecotr();

    //添加元素，默认容量10个,满了以后扩容为原容量的两倍
    vector.add(1);
    vector.add(2);
    vector.add(3);
    vector.add(4);
    vector.add(5);
    vector.add(6);

    Iterator it = vector.iterator();
    while (it.hasNext()) {
        Object obj=it.next();
        System.out.println(obj);
    }
    //这个可能以后要使用！！！！
    List myList=new ArrayList();//非线程安全的
    Collections.synchronizedList(myList);//变成线程安全的

    //myList集合现在是线程安全的了
    myList.add("111");
    myList.add("222");
}
}

Set

Set和 Map 密不可分

HashSet要点

1.HashSet底层实际上是一个HashMap,HashMap底层采用了哈希表数据结构。

2.哈希表又叫做散列表，哈希表底层是一个数组，这个数组中每一个元素
是一个单向链表。每个单向链表都有一个独一无二的hash值，代表数组的
下标。hash值实际上是key调用hashCode方法，在通过"hash function"转换成的值。

3.HashSet其实是HashMap中的key部分，往HashSet添加元素其实是将元素添加到map的key部分了。
HashSet有什么特点，HashMap中的key应该不同。
HashMap中有一个put方法，put(key,value) key是无序不可重复的。
    public boolean add(E e){
        return map.put(e,PRESENT)==null;
    }

重要：存储在HashSet集合或者HashMap集合key部分的元素，需要同时重写hashCode+equals方法

实例

public class SetTest01{
    
    public static void main(String[] args){
        
        //创建集合
        Set es = new HashSet();
        
        Employee e1 = new Employee("1000","JACK");
        Employee e2 = new Employee("1000","JACK");
        Employee e3 = new Employee("1000","SCOTT");
        Employee e4 = new Employee("2001","SUN");
        Employee e5 = new Employee("3000","JIM");
        Employee e6 = new Employee("3001","COOK");
        
        System.out.println(e1.hashCode());
        System.out.println(e2.hashCode());
        
        //添加元素
        es.add(e1);
        es.add(e2);
        es.add(e3);
        es.add(e4);
        es.add(e5);
        es.add(e6);
        
        //查看集合元素个数
        System.out.println(es.size()); //5
        
        
    }
}


//根据现实的业务逻辑得知：该公司员工编号是: 1000 - 9999
class Employee{
    
    //编号
    String no;
    
    //姓名
    String name;
    
    //Constructor
    Employee(String no,String name){
        this.no = no;
        this.name = name;
    }
    
    //重写equals方法.
    //如果员工编号相同，并且名字相同，则是同一个对象
    public boolean equals(Object o){
        if(this==o){
            return true;
        }
        if(o instanceof Employee){
            Employee e = (Employee)o;
            if(e.no.equals(this.no) && e.name.equals(this.name)){
                return true;
            }
        }
        
        return false;
    }
           
    //重写hashCode方法.
    public int hashCode(){
        //以员工编号分组.
        return no.hashCode();
    }
}

TreeSet要点

TreeSet集合存储元素特点：
    1. 无序不可重复，但是可以按照元素的大小顺序自动排序，称为：可排序集合。
        这里的无序指的是存进去的顺序和取出来的顺序不同，没有下标。

实例

public class TreeSetTest {
    public static void main(String[] args) {
        Set<String> strs =new TreeSet<>();
        strs.add("A");
        strs.add("B");
        strs.add("Z");
        strs.add("Y");
        strs.add("Z");
        strs.add("M");
        //遍历
        /*
            A
            B
            M
            Y
            Z
        */
        for (String s : strs){
            System.out.println(s);
        }
}