AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

集合常见几个问题总结

2022-11-02 107
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《基础系列》

Map的实现类中，哪些是有序的，哪些是无序的，有序的是如何保证其有序性，你觉得哪个有序性性能更高，你有没有更好或者更高效的实现方式？

答：1. Map的实现类有HashMap,LinkedHashMap,TreeMap

2. HashMap是有无序的，LinkedHashMap和TreeMap都是有序的（LinkedHashMap记录了添加数据的顺序；TreeMap默认是自然升序）

3. LinkedHashMap底层存储结构是哈希表+链表，链表记录了添加数据的顺序

4. TreeMap底层存储结构是二叉树，二叉树的中序遍历保证了数据的有序性

5. LinkedHashMap有序性能比较高，因为底层数据存储结构采用的哈希表


下面的代码在绝大部分时间内都运行得很正常，请问什么情况下会出现问题？根源在哪里？

packagecom.bjsxt;

importjava.util.LinkedList;

publicclassStack {

LinkedList list = newLinkedList();

publicsynchronizedvoidpush(Object x) {

synchronized(list) {

list.addLast(x);

notify();

}

}

publicsynchronizedObject pop() throwsException{

synchronized(list){

if(list.size()<=0){

wait();

}

returnlist.removeLast( );

}

}

}

答：将if( list.size() <= 0 )改成：while( list.size() <= 0 )


TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort（）方法如何比较元素？

答：TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会 回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections 工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是是通过接口注入比较元素大小的算法，也是对回调模式的应用。


List里面如何剔除相同的对象？请简单用代码实现一种方法

publicclassTest {

publicstaticvoidmain(String[] args) {

  List<String> li1 = newArrayList<String>();

  li1.add("8");

  li1.add("8");

  li1.add("9");

  li1.add("9");

  li1.add("0");

  System.out.println(li1);

  //方法:将List中数据取出来来存到Set中

  HashSet<String> set = newHashSet<String>();

  for(inti=0;i<li1.size();i++){

  set.add(li1.get(i));

  }

  System.out.println(set);

}

}


Java.util.Map的实现类有

分析：Java中的java.util.Map的实现类

1、HashMap

2、Hashtable

3、LinkedHashMap

4、TreeMap


下列叙述中正确的是（）

A. 循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B. 在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C. 在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D. 在循环队列中元素的个数是由队头指针和队尾指针共同决定的

答案：D

分析：循环队列中元素的个数是由队首指针和队尾指针共同决定的，元素的动态变化也是通过队首指针和队尾指针来反映的，当队首等于队尾时，队列为空。


List、Set、Map 是否继承自Collection 接口？

答：List、Set 的父接口是Collection，Map 不是其子接口，而是与Collection接口是平行关系，互不包含。

9.png

Map是键值对映射容器，与List和Set有明显的区别，而Set存储的零散的元素且不允许有重复元素（数学中的集合也是如此），List是线性结构的容器，适用于按数值索引访问元素的情形。

220.说出ArrayList、Vector、LinkedList 的存储性能和特性？

答：ArrayList 和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，Vector由于使用了synchronized 方法（线程安全），通常性能上较ArrayList 差，而LinkedList 使用双向链表实现存储（将内存中零散的内存单元通过附加的引用关联起来，形成一个可以按序号索引的线性结构，这种链式存储方式与数组的连续存储方式相比，其实对内存的利用率更高），按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。Vector属于遗留容器（早期的JDK中使用的容器，除此之外Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器），现在已经不推荐使用，但是由于ArrayList和LinkedListed都是非线程安全的，如果需要多个线程操作同一个容器，那么可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器后再使用（这其实是装潢模式最好的例子，将已有对象传入另一个类的构造器中创建新的对象来增加新功能）。

补充：遗留容器中的Properties类和Stack类在设计上有严重的问题，Properties是一个键和值都是字符串的特殊的键值对映射，在设计上应该是关联一个Hashtable并将其两个泛型参数设置为String类型，但是Java API中的Properties直接继承了Hashtable，这很明显是对继承的滥用。这里复用代码的方式应该是HAS-A关系而不是IS-A关系，另一方面容器都属于工具类，继承工具类本身就是一个错误的做法，使用工具类最好的方式是HAS-A关系（关联）或USE-A关系（依赖） 。同理，Stack类继承Vector也是不正确的。

221.List、Map、Set 三个接口，存取元素时，各有什么特点？

答：List以特定索引来存取元素，可有重复元素。

Set不能存放重复元素（用对象的equals()方法来区分元素是否重复） 。Map保存键值对（key-value pair）映射，映射关系可以是一对一或多对一。Set和Map容器都有基于哈希存储和排序树（红黑树）的两种实现版本，基于哈希存储的版本理论存取时间复杂度为O(1)，而基于排序树版本的实现在插入或删除元素时会按照元素或元素的键（key）构成排序树从而达到排序和去重的效果。


TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

答：TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。

TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。

Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型 （需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是是通过接口注入比较元素大小的算法，也是对回调模式的应用。

例子1：

Student.java

packagecom.bjsxt;

 

publicclassStudent implementsComparable<Student> {

    privateString name;        // 姓名

    privateintage;            // 年龄

    publicStudent(String name, intage) {

        this.name = name;

        this.age = age;

    }

    @Override

    publicString toString() {

        return"Student [name="+ name + ", age="+ age + "]";

    }

    @Override

    publicintcompareTo(Student o) {

        returnthis.age - o.age; // 比较年龄(年龄的升序)

    }

  }

Test01.java

packagecom.bjsxt;

importjava.util.Set;

importjava.util.TreeSet;

 

classTest01 {

  publicstaticvoidmain(String[] args) {

        Set<Student> set = newTreeSet<>();     // Java 7的钻石语法(构造器后面的尖括号中不需要写类型)

        set.add(newStudent("Hao LUO", 33));

        set.add(newStudent("XJ WANG", 32));

        set.add(newStudent("Bruce LEE", 60));

        set.add(newStudent("Bob YANG", 22));

          for(Student stu : set) {

            System.out.println(stu);

        }

//      输出结果:

//      Student [name=Bob YANG, age=22]

//      Student [name=XJ WANG, age=32]

//      Student [name=Hao LUO, age=33]

//      Student [name=Bruce LEE, age=60]

    }

}

例子2：

Student.java

packagecom.bjsxt;

 

publicclassStudent {

    privateString name;    // 姓名

    privateintage;        // 年龄

    publicStudent(String name, intage) {

        this.name = name;

        this.age = age;

    }

    /**

     * 获取学生姓名

     */

    publicString getName() {

        returnname;

    }

    /**

     * 获取学生年龄

     */

    publicintgetAge() {

        returnage;

    }

    @Override

    publicString toString() {

        return"Student [name="+ name + ", age="+ age + "]";

    }

  }

Test02.java

packagecom.bjsxt;

importjava.util.ArrayList;

importjava.util.Collections;

importjava.util.Comparator;

importjava.util.List;

 

  classTest02 {

   publicstaticvoidmain(String[] args) {

        List<Student> list = newArrayList<>();     // Java 7的钻石语法(构造器后面的尖括号中不需要写类型)

        list.add(newStudent("Hao LUO", 33));

        list.add(newStudent("XJ WANG", 32));

        list.add(newStudent("Bruce LEE", 60));

        list.add(newStudent("Bob YANG", 22));

 

        // 通过sort方法的第二个参数传入一个Comparator接口对象

        // 相当于是传入一个比较对象大小的算法到sort方法中

        // 由于Java中没有函数指针、仿函数、委托这样的概念

        // 因此要将一个算法传入一个方法中唯一的选择就是通过接口回调

        Collections.sort(list, newComparator<Student> () {

         @Override

            publicintcompare(Student o1, Student o2) {

                returno1.getName().compareTo(o2.getName());    // 比较学生姓名

            }

        });

 

        for(Student stu : list) {

            System.out.println(stu);

        }

//      输出结果:

//      Student [name=Bob YANG, age=22]

//      Student [name=Bruce LEE, age=60]

//      Student [name=Hao LUO, age=33]

//      Student [name=XJ WANG, age=32]

    }

}
文章标签：
Java
容器
索引
安全
API
算法
存储
龙哥手记
目录
相关文章
吵醒邻居
|
6月前
|
存储 Java 索引
JAVASet集合
JAVASet集合
吵醒邻居
54 0
西柚与蓝莓
|
4月前
|
存储 算法 C++
C++中集合的使用
C++中集合的使用
西柚与蓝莓
46 1
Leader_TBlog
|
存储 Java 容器
集合
集合
Leader_TBlog
70 0
yanyingbai
|
设计模式 安全
集合
集合
yanyingbai
68 0
大汉学友
|
索引
集合理解
集合的个人理解笔记 与二叉查找树规律
大汉学友
71 0
豆约翰
|
存储
16 集合（上）
16 集合
豆约翰
130 0
豆约翰
16 集合（下）
16 集合（下）
豆约翰
99 0
神奇的程序员
|
存储 JavaScript 前端开发
集合的实现
集合的实现
神奇的程序员
131 0
集合的实现
公主的心上人
|
存储 Java 容器
集合1
集合
公主的心上人
101 0
集合1
antony王中阳
不会用集合你就out了
不会用集合你就out了
antony王中阳
103 0

热门文章

最新文章

  • 1
    Flutter之禅 内存优化篇
  • 2
    《Cadence 16.6电路设计与仿真从入门到精通》——2.4 Design Entry CIS原理图图形界面　
  • 3
    记一次对网络抖动经典案例的分析
  • 4
    国外成人网站xHamster大量用户信息黑市变卖，部分账号涉及英美政府官员
  • 5
    用户密码以BCrypt加密的方式来防范被破解
  • 6
    带你理清CPU，cache和存储器之间的逻辑运作
  • 7
    Git设置代理服务器
  • 8
    【DSW Gallery】PAI-DSW开通及授权
  • 9
    吐血整理：机器学习的30个基本概念，都在这里了（手绘图解）
  • 10
    MOSS站点的迁移(备份还原)
  • 1
    设计模式之 5 大创建型模式，万字长文深剖 ，近 30 张图解！
    46
  • 2
    《C++新特性：为多线程数据竞争检测与预防保驾护航》
    40
  • 3
    Kotlin - 区间与数组
    40
  • 4
    Kotlin - 参数与异常
    39
  • 5
    Kotlin - 运算符与中缀表达式
    34
  • 6
    Kotlin - 函数与Lambda表达式
    22
  • 7
    Kotlin - 分支与循环
    18
  • 8
    天气预报1天-中国气象局-地址查询版免费API接口教程
    20
  • 9
    《C++智能合约与区块链底层交互全解析：构建坚实的去中心化应用桥梁》
    19

    • 相关课程

    更多
  • Python语言基础 - 列表、元组、字典、集合

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册

    • 相关实验场景

    更多
  • 常见类型-3：数组元组的方法
  • 常见类型-2：数组和元组
    • 下一篇
    阿里云OSS设置跨域访问