java集合(上)

java集合(上)

1. Java集合框架概述

集合、数组都是对多个数据进行存储操作的结构，简称Java容器。说明：此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储。

1.1. 数组在存储多个数据的特点

一旦初始化以后，其长度就确定了。
数组一旦定义好，其元素的类型也就确定了。我们也就只能操作指定类型的数据了。比如：String[] arr;int[] arr1;Object[] arr2;

1.2. 数组在存储多个数据方面的缺点

一旦初始化以后，其长度就不可修改。
数组中提供的方法非常有限，对于添加、删除、插入数据等操作，非常不便，同时效率不高。
获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
数组存储数据的特点：有序、可重复。对于无序、不可重复的需求，不能满足。

1.3. Java 集合可分为 Collection 和 Map 两种体系

day23_java集合(上)学习笔记 - 图1

|——Map接口：双列集合，用来存储一对(key - value)一对的数据 —>高中函数：y = f(x)
|——HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

day23_java集合(上)学习笔记 - 图2

2. Collection接口中的方法

add(Object e)：将元素e添加到集合coll中

size()：获取添加的元素的个数

addAll(Collection coll1)：将coll1集合中的元素添加到当前的集合中

clear()：清空集合元素，但是集合不会变为null

isEmpty()：判断当前集合是否为空，即判断集合元素的个数是否为0。

contains(Object obj)：判断当前集合中是否包含obj，在判断时会调用obj对象所在类的equals()方法。所以向Collection接口的实现类的对象中添加数据obj时，要求obj所在类要重写equals()方法。

containsAll(Collection coll)：判断形参coll中的所有元素是否都存在于当前集合中。会涉及调用equals()方法

remove(Object obj)：从当前集合中移除obj元素。会涉及调用equals()方法

removeAll(Collection coll)：从当前集合中移除coll中所有的元素。把他们共有的元素移除

retainsAll(Collection coll)：交集：获取当前集合和coll集合的交集，并返回给当前集合。返回值是boolean。会涉及调用equals()方法

equals(Object obj)：要想返回true，需要当前集合和形参集合的元素都相同。

hashCode()：返回当前对象的哈希值

toArray()：集合 —-> 数组。返回Object类型的数组

拓展：数组 —-> 集合：调用Arrays类的静态方法asList()。

    //如果数组元素是基本数据类型，调用Arrays.asList()之后，list中只有一个元素
    List arr1 = Arrays.asList(new int[]{123, 456});
    System.out.println(arr1.size());//1
    //当数组元素是引用数据类型时，才会正常
    List arr2 = Arrays.asList(new Integer[]{123, 456});
    System.out.println(arr2.size());//2

iterator()：返回Iterator接口的实例，用于遍历集合元素。

总结：

向Collection接口的实现类的对象中添加数据obj时，要求obj所在类要重写equals()方法。

3. Iterator迭代器接口

主要用于遍历Collection集合中的元素。

内部的方法：hasNext()和next()和remove()
集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。
内部定义了remove()，可以在遍历的时候，删除集合中的元素。此方法不同于集合直接调用remove()。如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，再调用remove都会报IllegalStateException。

    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add(new Person("Jerry",20));
    coll.add(new String("Tom"));
    coll.add(false);
    Iterator iterator = coll.iterator();
    //方式一：
    //        System.out.println(iterator.next());
    //        System.out.println(iterator.next());
    //        System.out.println(iterator.next());
    //        System.out.println(iterator.next());
    //        System.out.println(iterator.next());
    //        //报异常：NoSuchElementException
    //        System.out.println(iterator.next());
    //方式二：不推荐
    //        for(int i = 0;i < coll.size();i++){
    //            System.out.println(iterator.next());
    //        }
    //方式三：推荐
    ////hasNext():判断是否还有下一个元素
    while(iterator.hasNext()){
        //next():①指针下移 ②将下移以后集合位置上的元素返回
        System.out.println(iterator.next());
    }

3.1. 迭代器的执行原理

day23_java集合(上)学习笔记 - 图3

3.2. 迭代器的两种错误写法

        Collection coll = new ArrayList();
        coll.add(123);
        coll.add(456);
        coll.add(new Person("Jerry",20));
        coll.add(new String("Tom"));
        coll.add(false);
        //错误方式一：
//        Iterator iterator = coll.iterator();
//        while((iterator.next()) != null){
//            System.out.println(iterator.next());
//        }
        //错误方式二：
        //集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。
        while (coll.iterator().hasNext()){
            System.out.println(coll.iterator().next());
        }

3.3. Iterator的remove()方法

3.4. foreach循环(增强for)

Java 5.0 提供了 foreach 循环迭代访问 Collection和数组。内部仍然调用的是迭代器。

格式：for(集合/数组元素的类型局部变量 : 集合/数组对象)

        @Test
        public void test1(){
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry",20));
            coll.add(new String("Tom"));
            coll.add(false);
            //for(集合元素的类型 局部变量 : 集合对象)
            //内部仍然调用了迭代器。
            for(Object obj : coll){
                System.out.println(obj);
            }
        }
        @Test
        public void test2(){
            int[] arr = new int[]{1,2,3,4,5,6};
            //for(数组元素的类型 局部变量 : 数组对象)
            for(int i : arr){
                System.out.println(i);
            }
        }

笔试题：

//练习题
    @Test
    public void test3(){
        String[] arr = new String[]{"MM","MM","MM"};
//        //方式一：普通for赋值
//        for(int i = 0;i < arr.length;i++){
//            arr[i] = "GG";
//        }
        //方式二：增强for循环
        for(String s : arr){
            s = "GG";
        }
        for(int i = 0;i < arr.length;i++){
            System.out.println(arr[i]);
        }
    }

4. Collection子接口一：List

存储有序的、可重复的数据。

|——Collection接口：单列集合，用来存储一个一个的对象
|——List接口：存储有序的、可重复的数据。 —>“动态”数组
|——ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储
|——LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储
|——Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[] elementData存储

面试题：ArrayList、LinkedList、Vector三者的异同？

同：三个类都是实现了List接口，存储数据的特点相同：存储有序的、可重复的数据。

不同：见上

4.1. ArrayList源码分析：

4.1.1. jdk7情况下：

ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementData

list.add(123);//elementData[0] = new Integer(123);

……

list.add(11);//如果此次的添加导致底层elementData数组容量不够，则扩容。

默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。

结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)

4.1.2. jdk8情况下ArrayList的变化：

ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}.并没有创建长度为10的数组

list.add(123);//第一次调用add()时，底层才创建了长度10的数组，并将数据123添加到elementData[0]

……

后续的添加和扩容操作与jdk 7 无异。

4.1.3. 小结：

jdk7中的ArrayList的对象的创建类似于单例的饿汉式，而jdk8中的ArrayList的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

4.2. LinkedList源码分析

LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null

list.add(123);//将123封装到Node中，创建了Node对象。

其中，Node定义为：体现了LinkedList的双向链表的说法

Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

4.3. Vector

jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。

在扩容方面，默认扩容为原来的数组长度的2倍。

4.4. List接口中的常用方法

void add(int index, Object ele)：在index位置插入ele元素
boolean addAll(int index, Collection eles)：从index位置开始将eles中的所有元素添加进来
Object get(int index)：获取指定index位置的元素
int indexOf(Object obj)：返回obj在集合中首次出现的位置
int lastIndexOf(Object obj)：返回obj在当前集合中末次出现的位置
Object remove(int index)：移除指定index位置的元素，并返回此元素
Object set(int index, Object ele)：设置指定index位置的元素为ele
List subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的左闭右开区间的子集合。

总结：

增：add(Object obj)
删：remove(int index) / remove(Object obj)
改：set(int index, Object ele)
查：get(int index)
插：add(int index, Object ele)
长度：size()
遍历：① Iterator迭代器方式
② 增强for循环
③ 普通的循环

4.5. 面试题

day23_java集合(上)学习笔记 - 图4

这里jvm默认是调用remove(int index)而不是remove(Object obj)。

5. Collection子接口二：Set

|——Collection接口：单列集合，用来存储一个一个的对象
|——Set接口：存储无序的、不可重复的数据 —>高中讲的“集合”
|——HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
|——LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历。对于频繁的遍历操作，LinkedHashSet效率高于HashSet.
|——TreeSet：可以按照添加对象的指定属性，进行排序。

Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法。
要求：向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()
要求：重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列码。重写两个方法的小技巧：对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

set：存储无序的，不可重复的数据

已HashSet为例说明

无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
不可重复性：保证添加的元素按照equals()方法判断时，不能返回true。即相同的元素只能添加一个。

5.1. 添加元素的过程

添加元素的过程：以HashSet为例：

我们向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），判断数组在此位置上是否已经有元素：

如果此位置上没有其他元素，则元素a添加成功。——>情况1

如果此位置上有其他元素b（或以链表形式存在的多个元素），则比较元素a与元素b的hash值：

如果hash值不同，则元素a添加成功。 ---->情况2
如果hash值相同，进而需要调用元素a所在类的equals()方法：
    equals()返回true，元素a添加失败
    equals()返回false，则元素a添加成功。 ---->情况3

对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。
jdk 7 :元素a放到数组中，指向原来的元素。头插法
jdk 8 :原来的元素在数组中，指向元素a 尾插法
总结：七上八下

HashSet底层：数组+链表

重写了equals方法就必须要重写hashCode方法，不然即使两个对象的属性完全相同，添加的时候也会认为是不重复的，从而添加了两个重复的对象，就违背了set接口的不可重复性。

5.2. LinkedHashSet使用

LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。

优点：对于频繁的遍历操作，LinkedHashSet效率高于HashSet

5.3. TreeSet

向TreeSet中添加的数据，要求是相同类的对象。必须实现其中一种排序方式不然会报异常。因为TreeSet添加元素的时候需要根据其中一种排序方式排序，如果没有提供就会报异常

两种排序方式：自然排序（实现Comparable接口）和定制排序（Comparator）

自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals().说明在equals()方法中不能只根据一个属性进行排序比较，如果只根据一个属性排序的时候，两个对象恰好他们的那个属性都一样，但是其他的属性不一样时。后面的添加的那个对象添加不进去。因为这时候判断两个对象是否相同的标准已经不是equals()方法了，而是你指定的排序方式。

定制排序中，比较两个对象是否相同的标准为：compare()返回0，不再是equals().

TreeSet调用remove()方法、contains()方法也是用的compareTo()方法或者compare()方法

5.3.1 TreeSet课后练习

定义一个 Employee 类。

该类包含：private 成员变量 name,age,birthday，其中 birthday 为 MyDate 类的对象；

并为每一个属性定义 getter, setter 方法；

并重写 toString 方法输出 name, age, birthday

MyDate 类包含: private 成员变量 year,month,day；并为每一个属性定义 getter, setter 方法；

创建该类的 5 个对象，并把这些对象放入 TreeSet 集合中（下一章： TreeSet 需使用泛型来定义）

分别按以下两种方式对集合中的元素进行排序，并遍历输出：

1). 使 Employee 实现 Comparable 接口，并按 name 排序

2). 创建 TreeSet 时传入 Comparator 对象，按生日日期的先后排序。

5.5. Set课后两道面试题

面试题一

    HashSet set = new HashSet();
    Person p1 = new Person(1001,"AA");
    Person p2 = new Person(1002,"BB");
    set.add(p1);
    set.add(p2);
    p1.name = "CC";
    set.remove(p1);
    System.out.println(set);
    set.add(new Person(1001,"CC"));
    System.out.println(set);
    set.add(new Person(1001,"AA"));
    System.out.println(set);

其中Person类中重写了hashCode()和equal()方法

题目分析：set.remove(p1)：remove()方法首先调用hashCode()方法找到存储的数组索引位置，但是现在使用的是p1.name=”CC”之后求的hashCode()的值。所以定位的hashCode()索引上肯定没有元素，remove()自然也不会成功。所以set仍然是两个元素。

set.add(new Person(1001,”CC”))：调用hashCode方法找到数组索引位置上没有元素，因为p1添加进来的时候还没有改name属性。所以hashCode与改name属性后的hashCode不一样。所以添加成功。第二个输出有三个元素。

set.add(new Person(1001,”AA”))：调用hashCode方法找找到数组索引位置上发现有元素，然后调用equals方法。是false，所以添加成功。第三个输出有4个元素。

面试题二

练习：在List内去除重复数字值，要求尽量简单

    public static List duplicateList(List list) {
        HashSet set = new HashSet();
        set.addAll(list);
        return new ArrayList(set);
    }
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(new Integer(1));
        list.add(new Integer(2));
        list.add(new Integer(2));
        list.add(new Integer(4));
        list.add(new Integer(4));
        List list2 = duplicateList(list);
        for (Object integer : list2) {
            System.out.println(integer);
        }
    }