Java中List集合与Set集合

一、List 集合

List 是一个接口,是有序的 collection,此接口的用户可以对列表中每个元素的插入位置进行精确的控制,用户可以根据元素的整数索引访问元素,并搜索列表中的元素。List 接口允许存放重复的元素,并且元素都是有序的(Set 接口不允许存放重复元素,元素是无序的)

1、List 接口特点

它是一个有序的集合

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

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

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

2、List 接口中常用的方法

boolean add(Object e):向集合末尾添加指定元素

void add(int index,Object e):向集合指定索引处添加指定元素,原有元素依次后移

remove(Object e):将指定元素对象从集合中删除,返回被删除的元素

remove(int index):将指定索引处的元素从集合中删除,返回被删除的元素

set(int index,Object e):将指定索引处的元素替换成指定的元素,返回替换前的元素

get(int index):获取指定索引处的元素,返回该元素

public static void main(String[] args)

{

    List<String> L = new ArrayList<>();

    //末尾添加元素

    L.add("abc");

    L.add("bcd");

    L.add("cde");

    L.add("def");

    L.add("efg");

    //指定位置添加元素

    L.add(2,"fgh");

    //删除指定元素

    L.remove("abc");

    //删除指定索引元素

    L.remove(1);

    //将指定索引处的元素替换成指定元素

    L.set(1,"hello");

    //获取指定索引处的元素

    L.get(1);

    //使用迭代器获取出集合中的元素,最好使用listIterator进行迭代

    Iterator<String> it = L.listIterator();

    while(it.hasNext())

    {

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

    }

    //由于List集合是有索引的,还可以使用索引进行迭代

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

    {

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

    }

}

注:

List 集合是带索引的有序集合,因此除了使用迭代器进行获取元素外,还可以使用索引下表进行元素获取

Iterator 迭代 List 异常问题:在迭代过程中,如果要添加一个新的元素,使用集合的方法对元素进行操作,会导致迭代器不知道集合中的变化,容易发生数据的不确定性。因此,通过 listIterator 迭代能避免这个异常。

3、List 集合存储数据结构

List 接口下有多个集合,它们存储元素所采用的数据结构方式有所不同,这就导致了不同集合有其不同特点,供程序员在不同的环境下使用。

数据存储的常用结构有:堆栈、队列、数组、链表

堆栈

(1) 先进后出

(2) 栈的入口、出口都是栈的顶端位置

(3) 压栈:即存元素

(4) 出栈:即取元素

队列

(1) 先进先出

(2) 队列的入口、出口为两端

数组

(1) 查找元素快:通过索引快速访问指定元素位置

(2) 增删元素慢:指定位置增加、删除元素都需要创建一个新的数组,将指定新元素存储在指定索引位置,再把原数组索引根据索引复制到新数组对应索引位置

链表

(1) 多个节点之间,通过地址进行连接

(2) 查找元素慢:想要查找某个元素,需要通过连接的节点,依次向后查找指定元素

(3) 增删元素快:只需修改连接下个元素的地址即可

4、ArrayList 集合

ArrayList 集合是最常用的集合,是用存储数据结构,元素增删慢,查找快。

在我的另一篇博客:Java中ArrayList集合有其的介绍,这里不多说

5、LinkedList 集合

LinkedList 集合数据存储的结构是链表结构,对元素的增删很方便,实际开发中对一个集合元素的增删经常涉及到首位操作,而 LinkedList 集合提供了大量的首位操作方法。

void addFirst(E e):将指定元素插入链表的开头

void addLast(E e):将指定元素插入链表的结尾

E getFirst():返回链表的第一个元素

E getLast():返回链表的最后一个元素

E removeFirst():移除并返回链表的第一个元素

E removeLast():移除并返回链表的最后一个元素

E pop(E e):取出链表栈顶元素

void push(E e):将元素推入此链表所示的堆栈

boolean isEmpty():判断链表中是否有元素

逻辑实例:

public static void main(String[] args)

{

    //创建链表

    LinkedList<String> link = new LinkedList<>();

    //添加元素

    link.add("abc");

    link.add("bcd");

    link.add("cde");

    link.add("def");

    //获取元素

    System.out.println(link.getFirst());

    System.out.println(link.getLast());

    //删除元素

    System.out.println(link.remove("abc"));

    System.out.println(link.removeFirst());

    while (link.isEmpty())  //判断集合是否有元素

    {

        System.out.println(link.pop());    //取出栈顶元素

    }

}

6、Vector 集合

Vector 集合数据存储结构是数组结构,与 ArrayList 不同之处在于提供了一个独特的取出方法:枚举Enumeration,与 Iterator 接口功能类似。Vector 集合已被 ArrayList 集合替代,枚举Enumeration 已被迭代器 Iterator 替代


二、Set 接口

Set 集合里面存储的是无序的不重复元素,没有索引,可以采用迭代器和增强for来获取元素,Set 常用的子类有 HashSet、LinkedHashSet 集合,可以通过 equals 方法来判断是否为重复元素。

1、HashSet 集合

HashSet 类实现 Set 接口,由哈希表支持(实际上是一个 HashMap 集合),HashSet 集合不能保证迭代顺序与元素存储顺序相同,采用哈希表结构存储数据结构,保证元素唯一性的方式依赖于:hashCode() 于 equals() 方法。

特点:无序集合,存储和取出的顺序不同,没有索引,不存储重复元素

在代码编写上和 ArrayList 完全一致

存储、取出数据都比较快

线程不安全,运行速度快

底层数据结构为哈希表(链表数组结合体)

public static void main(String[] args)

{

    //使用多态创建哈希表

    Set<String> S = new HashSet<>();

    S.add("abc");

    S.add("bcd");

    S.add("cde");

    //使用迭代器获取元素

    Iterator<String> it = S.iterator();

    while (it.hasNext())

    {

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

    }

    //使用增强获取元素

    for(String s : S)

    {

        System.out.println(s);

    }

}

2、HashSet 集合存储数据的结构(哈希表)

哈希表介绍:

哈希表底层使用的是数组机制,数组中也存放对象,而这些对象往数组中存放时的位置比较特殊,当需要把对象在这些数组中存放时,会根据这些对象特有的数据来结合相应的算法,计算出这个对象在数组中的位置,然后把这个对象存放在数组中。这样的数组就称为哈希数组,即哈希表。

在哈希表存储数组时,会先记录第一个元素的地址,继续存储时,会让先来的元素记录后来的地址,在这里有一个“桶”和“加载因子”的概念,桶:数组的初始容量,初始容量为16;加载因子:数组的长度百分比,默认为0.75。数组的长度:16*0.75 = 12;当存放的数据超出数组长度 12 时,数组就会进行扩容,即复制(这个过程很耗费资源),这个过程也称为数据的再哈希 rehash。

当向哈希表存放元素时,会根据元素的特有数据结合响应的算法,这个算法就是 Object 类中的 hashCode 方法。由于任何对象都是 Object 类的子类,所以任何对象都有这个方法,即:在哈希表中存放对象时,会调用对象的 hashCode 方法,算出对象在表中的位置,需要注意的是,如果两个对象 hashCode 方法算出结果一样,称为哈希冲突,这样会调用对象 equals 方法来比较两个对象是不是同一个对象,如果返回 true,则把第一个对象存放在哈希表中,如果返回 false,就会把这两个值都存放在哈希表中。

总结:保证 HashSet 集合元素的唯一,其实就是根据对象 hashCode 和 equals 方法来决定的。如果往集合中存放自定义对象,为了保证唯一性,就必须重写 hashCode 和 equals 方法建立属于当前对象的比较方法。

3、String 类的哈希值

哈希值表示普通的十进制整数, 是父类 Object 方法 public int hashCode() 的计算结果,String 类继承了Object,重写了 hashCode 方法。String 类中 hashCode 源码:

public int hashCode() {

    int h = hash;    //一开始变量 hash 为 0

    if (h == 0 && value.length > 0) { 

        char val[] = value;

        //返回字符串ASCII经过计算的和

        for (int i = 0; i < value.length; i++) {

            h = 31 * h + val[i];

        }

        hash = h;

    }

    return h;

}

因此,当使用String类定义两个对象:String S1 = new String("abc"); String S2 = new String("abc"); 对象S1和S2哈希值是相同的,然后集合会让后来的对象调用 equals 方法,如果返回 true,则集合判定元素重复,将其去除。

4、自定义对象重写hashCode和equals

给HashSet中存放自定义类型元素时,需要重写对象中的hashCode和equals方法,建立自己的比较方式,才能保证HashSet集合中的对象唯一。

创建Person类,在类中重写 hashCode 方法和 equals 方法

public class Person {

    private String name;

    private int age;

    public Person(String name,int age)

    {

        this.name = name;

        this.age = age;

    }

    public void setName(String name)

    {

        this.name = name;

    }

    public void setAge(int age)

    {

        this.age = age;

    }

    public String getName()

    {

        return name;

    }

    public int getAge()

    {

        return age;

    }

    public String toString() {

        return name + age;

    }

    //重写hashCode方法

    public int hashCode()

    {

        return name.hashCode() + age;

    }

    //重写equals方法

    public boolean equals(Object obj)

    {

        if(this == obj)

            return true;

        if(obj == null)

            return false;

        if(obj instanceof Person)

        {

            Person P = (Person)obj;

            return name.equals(obj.name) && age == P.age;

        }

        return false;

    }

}

在main中调用,由于重写了 hashCode 和 equals 方法,所以相同类型元素将不会打印出

public static void main(String[] args)

{

    //创建存储Person类的哈希表

    HashSet<Person> H = new HashSet<>();

    H.add(new Person("a",18));

    H.add(new Person("a",18));

    H.add(new Person("b",19));

    H.add(new Person("c",20));

    System.out.println(H);

}

5、LinkedHashSet集合

LinkedHashSet 类是基于链表的哈希表的实现,继承自 HashSet,是 Set 接口的实现,此实现与 HashSet 的不同之外在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,即按照将元素插入到 set 中的顺序(插入顺序)进行迭代。

LinkedHashSet  特点:具有顺序,存储和取出元素顺序相同

public class LinkedHashSetDemo {


  public static void main(String[] args) {

LinkedHashSet<Integer> link = new LinkedHashSet<Integer>();

link.add(123);

link.add(44);

link.add(33);

link.add(33);

link.add(66);

link.add(11);

System.out.println(link);

  }

}

hashCode 和 equals 方法的面试题

(1) 两个对象 Person P1 P2,如果两个对象的哈希值相同,则两个对象的 equals 一定返回 true 吗?

不一定为 true

(2) 两个对象 Person P1 P2,如果两个对象的 equals 方法返回 true,则两个对象的哈希值一定相同吗?

一定相同

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,864评论 6 494
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,175评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,401评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,170评论 1 286
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,276评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,364评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,401评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,179评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,604评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,902评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,070评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,751评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,380评论 3 319
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,077评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,312评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,924评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,957评论 2 351

推荐阅读更多精彩内容