Java语言基础学习Java集合(二):Collection子接口---List接口与Set接口

一、List接口概述

鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组

List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。

 List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据 序号存取容器中的元素。

JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector。

List接口框架

  |----Collection接口：单列集合，用来存储一个一个的对象

      |----List接口：存储有序的、可重复的数据。  -->“动态”数组,替换原有的数组

        |----ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储

        |----LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储

        |----Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[] elementData存储

二、List实现类之一：ArrayList

1. ArrayList的源码分析：

*  1.1 jdk 7情况下

*      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)

*

*  1.2 jdk 8中ArrayList的变化：

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

*

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

*      ...

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

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

    Arrays.asList(…) 方法返回的 List 集合，既不是 ArrayList 实例，也不是 Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合。

三、List实现类之二：LinkedList 

LinkedList的源码分析：

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

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

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

      private static class Node<E> {

            E item;

            Node<E> next;

            Node<E> prev;

            Node(Node<E> prev, E element, Node<E> next) {

            this.item = element;

            this.next = next;

            this.prev = prev;

            }

        }

    定义内部类Node，作为LinkedList中保存数据的基 本结构。Node除了保存数据，还定义了两个变量： 

        prev变量记录前一个元素的位置

        next变量记录下一个元素的位置

四、List 实现类之三：Vector 

Vector的源码分析：

      jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。在扩容方面，默认扩容为原来的数组长度的2倍。

五、请问ArrayList/LinkedList/Vector的异同？谈谈你的理解？ArrayList底层 是什么？扩容机制？Vector和ArrayList的最大区别?

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

ArrayList和LinkedList的异同

二者都线程不安全，相对线程安全的Vector，执行效率高。 此外，ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。对于 随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。对于新增 和删除操作add(特指插入)和remove，LinkedList比较占优势，因为ArrayList要移动数据。

ArrayList和Vector的区别

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于 强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用 ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大 小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

六、List接口方法 

List除了从Collection集合继承的方法外，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位置的子集合

@Test

    public void test1(){

        ArrayList list = new ArrayList();

        list.add(123);

        list.add(456);

        list.add("AA");

        list.add(new Person("Tom",12));

        list.add(456);

        System.out.println(list);

        //void add(int index, Object ele):在index位置插入ele元素

        list.add(1,"BB");

        System.out.println(list);

        //boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来

        List list1 = Arrays.asList(1, 2, 3);

        list.addAll(list1);

//        list.add(list1);

        System.out.println(list.size());//9

        //Object get(int index):获取指定index位置的元素

        System.out.println(list.get(0));

    }

@Test

    public void test2(){

        ArrayList list = new ArrayList();

        list.add(123);

        list.add(456);

        list.add("AA");

        list.add(new Person("Tom",12));

        list.add(456);

        //int indexOf(Object obj):返回obj在集合中首次出现的位置。如果不存在，返回-1.

        int index = list.indexOf(4567);

        System.out.println(index);

        //int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置。如果不存在，返回-1.

        System.out.println(list.lastIndexOf(456));

        //Object remove(int index):移除指定index位置的元素，并返回此元素

        Object obj = list.remove(0);

        System.out.println(obj);

        System.out.println(list);

        //Object set(int index, Object ele):设置指定index位置的元素为ele

        list.set(1,"CC");

        System.out.println(list);

        //List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的左闭右开区间的子集合

        List subList = list.subList(2, 4);

        System.out.println(subList);

        System.out.println(list);

    }

总结：常用方法

  增：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循环(foreach)

        ③ 普通的循环(for)

@Test

    public void test3(){//遍历

        ArrayList list = new ArrayList();

        list.add(123);

        list.add(456);

        list.add("AA");

        //方式一：Iterator迭代器方式

        Iterator iterator = list.iterator();

        while(iterator.hasNext()){

            System.out.println(iterator.next());

        }


        //方式二：增强for循环

        for(Object obj : list){

            System.out.println(obj);

        }


        //方式三：普通for循环

        for(int i = 0;i < list.size();i++){

            System.out.println(list.get(i));

        }

    }

/*

    区分List中remove(int index)和remove(Object obj)

    */

    @Test

    public void testListRemove() {

        List list = new ArrayList();

        list.add(1);

        list.add(2);

        list.add(3);

        updateList(list);

        System.out.println(list);//

    }

    private void updateList(List list) {

//        list.remove(2);//删除索引值为2的元素

        list.remove(new Integer(2));//删除元素value值为2的元素。

    }

一、Set 接口概述

Set接口是Collection的子接口，Set接口没有提供额外的方法

Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。

 Set 判断两个对象是否相同不是使用 == 运算符，而是根据equals() 方法。

向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()。

1. Set接口的框架：

*

* |----Collection接口：单列集合，用来存储一个一个的对象

*          |----Set接口：存储无序的、不可重复的数据  -->高中讲的“集合”

*              |----HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值

*                  |----LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历

*                                      对于频繁的遍历操作，LinkedHashSet效率高于HashSet.

*              |----TreeSet：可以按照添加对象的指定属性，进行排序。

二、Set实现类之一：HashSet

HashSet 是 Set 接口的典型实现，大多数时候使用 Set 集合时都使用这个实现类。

HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除 性能。

HashSet 具有以下特点： 不能保证元素的排列顺序 HashSet 不是线程安全的 集合元素可以是 null

HashSet 集合判断两个元素相等的标准：两个对象通过hashCode() 方法比较相 等，并且两个对象的 equals() 方法返回值也相等。 对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

一、Set：存储无序的、不可重复的数据

以HashSet为例说明：

1. 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。

2. 不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。

二、添加元素的过程：以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底层：数组+链表的结构。

向HashSet中添加元素的过程：

当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法 来得到该对象的 hashCode 值，然后根据 hashCode 值，通过某种散列函数决定该对象 在 HashSet 底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在 数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布， 该散列函数设计的越好）  如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果 为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了， 那么会通过链表的方式继续链接。

如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相 等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功。

三、Set实现类之二：LinkedHashSet

LinkedHashSet 是 HashSet 的子类 。

LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置， 但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入 顺序保存的。

LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全 部元素时有很好的性能。

LinkedHashSet 不允许集合元素重复。

四、Set实现类之三：TreeSet

TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。

TreeSet 两种排序方法：自然排序和定制排序。默认情况下，TreeSet 采用自然排序。

TreeSet底层使用红黑树结构存储数据 。

1.向TreeSet中添加的数据，要求是相同类的对象。

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

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

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

@Test

    public void test1(){

        TreeSet set = new TreeSet();

        //添加元素失败：不能添加不同类的对象

//        set.add(123);

//        set.add(456);

//        set.add("AA");

//        set.add(new User("Tom",12));

            //举例一：

//        set.add(34);

//        set.add(-34);

//        set.add(43);

//        set.add(11);

//        set.add(8);

        //举例二：

        set.add(new User("Tom",12));

        set.add(new User("Jerry",32));

        set.add(new User("Jim",2));

        set.add(new User("Mike",65));

        set.add(new User("Jack",33));

        set.add(new User("Jack",56));

        Iterator iterator = set.iterator();

        while(iterator.hasNext()){

            System.out.println(iterator.next());

        }

    }

@Test

    public void test2(){//定制排序

        Comparator com = new Comparator() {

            //按照年龄从小到大排列

            @Override

            public int compare(Object o1, Object o2) {

                if(o1 instanceof User && o2 instanceof User){

                  User u1 = (User)o1;

                  User u2 = (User)o2;

                  return Integer.compare(u1.getAge(),u2.getAge());

                }else{

                    throw new RuntimeException("输入的数据类型不匹配");

                }

            }

        };

        TreeSet set = new TreeSet(com);

        set.add(new User("Tom",12));

        set.add(new User("Jerry",32));

        set.add(new User("Jim",2));

        set.add(new User("Mike",65));

        set.add(new User("Mary",33));

        set.add(new User("Jack",33));

        set.add(new User("Jack",56));

        Iterator iterator = set.iterator();

        while(iterator.hasNext()){

            System.out.println(iterator.next());

        }

    }

}

//按照姓名从大到小排列,年龄从小到大排列

    @Override

    public int compareTo(Object o) {//自然排序

        if(o instanceof User){

            User user = (User)o;

//            return -this.name.compareTo(user.name);

            int compare = -this.name.compareTo(user.name);

            if(compare != 0){

                return compare;

            }else{

                return Integer.compare(this.age,user.age);

            }

        }else{

            throw new RuntimeException("输入的类型不匹配");

        }

    }

}

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,445评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,889评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,047评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,760评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,745评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,638评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,011评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,669评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,923评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,655评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,740评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,406评论 4赞 320
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,995评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,961评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,197评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,023评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,483评论 2赞 342