`

常见Java面试题(五):集合

阅读更多

Java集合框架(例如基本的数据结构)里包含了最常见的Java常见面试问题。很好地理解集合框架,可以帮助你理解和利用Java的一些高级特性。下面是面试Java核心技术的一些很实用的问题。

Q:最常见的数据结构有哪些,在哪些场景下应用它们?

A. 大部分人都会遗漏树和图这两种数据结构。树和图都是很有用的数据结构。如果你在回答中提及到它们的话,面试者可能会对你进行进一步进行的考核。

Q:你如何自己实现List,Set和Map?

A:虽然Java已经提供了这些接口的经过实践证明和测试过的实现,但是面试者还是喜欢这样问,来测试你对数据结构的理解。《Core Java Career Essentials》一书中通过图例和代码详细地讲解了这些内容。

常见的数据结构

数组是最常用的数据结构。数组的特点是长度固定,可以用下标索引,并且所有的元素的类型都是一致的。数组常用的场景有把:从数据库里读取雇员的信息存储为EmployeeDetail[],把一个字符串转换并存储到一个字节数组中便于操作和处理,等等。尽量把数组封装在一个类里,防止数据被错误的操作弄乱。另外,这一点也适合其他的数据结构。

列表和数组很相似,只不过它的大小可以改变。列表一般都是通过一个固定大小的数组来实现的,并且会在需要的时候自动调整大小。列表里可以包含重复的元素。常用的场景有,添加一行新的项到订单列表里,把所有过期的商品移出商品列表,等等。一般会把列表初始化成一个合适的大小,以减少调整大小的次数。

集合和列表很相似,不过它不能放重复的元素。当你需要存储不同的元素时,你可以使用集合。

堆栈只允许对最后插入的元素进行操作(也就是后进先出,Last In First Out – LIFO)。如果你移除了栈顶的元素,那么你可以操作倒数第二个元素,依次类推。这种后进先出的方式是通过仅有的peek(),push()和pop()这几个方法的强制性限制达到的。这种结构在很多场景下都非常实用,例如解析像(4+2)*3这样的数学表达式,把源码中的方法和异常按照他们出现的顺序放到堆栈中,检查你的代码看看小括号和花括号是不是匹配的,等等。

这种用堆栈来实现的后进先出(LIFO)的机制在很多地方都非常实用。例如,表达式求值和语法解析,校验和解析XML,文本编辑器里的撤销动作,浏览器里的浏览记录,等等。

队列和堆栈有些相似,不同之处在于在队列里第一个插入的元素也是第一个被删除的元素(即是先进先出)。这种先进先出的结构是通过只提供peek(),offer()和poll()这几个方法来访问数据进行限制来达到的。例如,排队等待公交车,银行或者超市里的等待列队等等,都是可以用队列来表示。

 

链表是一种由多个节点组成的数据结构,并且每个节点包含有数据以及指向下一个节点的引用,在双向链表里,还会有一个指向前一个节点的引用。例如,可以用单向链表和双向链表来实现堆栈和队列,因为链表的两端都是可以进行插入和删除的动作的。当然,也会有在链表的中间频繁插入和删除节点的场景。Apache的类库里提供了一个TreeList的实现,它是链表的一个很好的替代,因为它只多占用了一点内存,但是性能比链表好很多。也就是说,从这点来看链表其实不是一个很好的选择。

ArrayList是列表的一个很好的实现。相比较TreeList而言,ArrayList在除了在列表中间插入或者删除元素的情况,其他操作都比TreeList快很多。TreeList的实现是在内部使用了一个树形的结构来保证所有的插入和删除动作的复杂度都是O(log n)的。这种实现方式使得TreeList在频繁插入和删除元素的时候的性能远远高于ArrayList和LinkedList。



 

 

class Link {
   private int id;                    // data
   private String name;               // data
   private Link next;                 // reference to next link
}

 

 

HashMap的访问时间接近稳定,它是一种键值对映射的数据结构。这个数据结构是通过数组来实现的。它通过hash函数来给元素定位,并且用冲突检测算法来处理被hash到同一位置的值。例如,保存雇员的信息可以用雇员的id来作为key,对从properties文件里读入的属性-属性值可以用key/value对来保存,等等。HashMap在初始化的时候,给定一个合适的大小可以减少调整大小的次数。

是一种由节点组成的数据结构,每个节点都包含数据元素,并且有一个或多个子节点,每个子节点指向一个父节点(译者注:除了根节点)可以表示层级关系或者数据元素的顺序关系。常用的场景有表示一个组织里的雇员层级关系,XML元素的层级关系,等等。如果树的每个子节点最多有两个叶子节点,那么这种树被称为二叉树。二叉树是一种非常常用的树形结构, 因为它的这种结构使得节点的插入和删除都非常高效。树的边表示从一个节点到另外一个节点的快捷路径。



 

Java里面没有直接提供树的实现,但是它很容易通过下面的方式来实现。只需要创建一个Node对象,里面包含一个指向叶子节点的ArrayList。

 

package bigo;

import java.util.ArrayList;
import java.util.List;

public class Node {
    private String name;
    private List<node> children = new ArrayList<node>( );
    private Node parent;

    public Node getParent( ) {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node(String name) {
        this.name = name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public void removeChild(Node child) {
        children.remove(child);
    }

    public String toString( ) {
        return name;
    }
 }

 

 

只要数据元素的关系可以表示成节点和边的网状结构的话,就可以用来表示。树是一种特殊的图,它的所有节点都只能有一个父节点。和树不同的是,图的形状是由实际问题或者问题的抽象来决定的。例如,图中节点(或者顶点)可以表示不同的城市,而图的边则可以表示两个城市之间的航线。



 

在Java里构造一个图,你需要解决数据通过什么方式保存和访问的问题。在图里面也会用到上面提到的数据结构。Java的API里没有提供图的实现。不过有很多第三方库里提供了,例如JUNG,JGraphT,以及JDSL(不过好像不支持泛型)。《Core Java Career Essential》一书包含了用Java实现的可用示例。

Q:你对大O这个符号有什么了解呢,你是否可以根据不同的数据结构举出一些列子来?

A:大O符号可以表示一个算法的效率,也可以用来描述当数据元素增加时,最坏情况下的算法的性能。大O符号也可以用来衡量的性能,例如内存消耗量。有时候你可能会为了减少内存使用量而选择一个比较慢的算法。大O符号可以表示在大量数据的情况下程序的性能。不过,对于程序在大量数据量下的性能的测量,唯一比较实际的方式是行用较大的数据集来进行性能基准测试,这样可以把一些在大O复杂度分析里没有考虑到的情况包含进去,例如在虚拟内存使用比较多的时候系统会发生换页的情况。虽然基准测试比大O符号表示的结果更加实际,但是它不适用于设计阶段,所以在这个这时候大O复杂度分析是最合适的选择。

各种数据结构在搜索,插入和删除算法上的性能都可以用下面方式表示:常量复杂度O(1),线性复杂度O(n),对数复杂度O(log n),指数复杂度O(c^n),多项式复杂度O(n^c),平方复杂度O(n^2)以及阶乘复杂度O(n!),这里面的n都指的是数据结构里的元素的数量。性能和内存占用是可以相互权衡的。下面是一些示例。

示例1:在HashMap里查找一个元素的的时间复杂度是常量的,也即是O(1)。这是因为查找元素使用的是哈希函数,并且计算一个哈希值的时间是不受HashMap里的元素的个数的影响的。

示例2:线性搜索一个数组,列表以及链表都是的复杂度线性的,也即是O(n),这是查找的时候需要遍历整个列表。也就是说,如果一个列表的长度是原来的两倍,那么搜索所花的时间也是原来的两倍。

示例3:一个需要比较数组里的所有元素的排序算法的复杂度是多项式的,即是O(n^2)。这是因为一个嵌套的for循环的复杂度是O(n^2)。在搜素算法里有这样的例子。

示例4:二分搜索一个数组或者数组列表的复杂度是对数的,即是O(log n)。在链表里查询一个节点的复杂度一般是O(n)。相比较数组链表和数组的O(log n)的性能而言,随着元素数量的增长,链表的O(n)的复杂度的性能就比较差了。对数的时间复杂度就是如果10个元素花费的时间是x单位的话,100个元素最多花费2x单位的时间,而10000个元素最多花费4x个单位的时间。如果你在一个平面坐标上画出图形的话,你会发现时间的增长没有n(元素的个数)快。

 

Q:HashMap和TreeMap在性能上有什么样的差别呢?你比较倾向于使用哪一个?

A:一个平衡树的性能是O(logn)。Java里的TreeMap用一个红黑树来保证key/value的排序。红黑树是平衡二叉树。保证二叉树的平衡性,使得插入,删除和查找都比较快,时间复杂度都是O(log n)。不过它没有HashMap快,HashMap的时间复杂度是O(1),但是TreeMap的优点在于它里面键值是排过序的,这样就提供了一些其他的很有用的功能。



 

Q:怎么去选择该使用哪一个呢?

A:使用无序的HashSet和HashMap,还是使用有序的TreeSet和TreeMap,主要取决于你的实际使用场景,一定程度上还和数据的大小以及运行环境有关。比较实际的一个原因是,如果插入和更新都比较频繁的话,那么保证元素的有序可以提高快速和频繁查找的性能。如果对于排序操作(例如产生一个报表合作者运行一个批处理程序)的要求不是很频繁的话,那么把数据以无序的方式存储,然后在需要排序的时候用Collections.sort(…)来进行排序,会比用有序的方式来存储可能会更加高效。这个只是一种可选的方式,没人能给你一个确切的答案。即使是复杂度的理论,例如O(n),成立的前提也是在n足够大的情况下。只要在n足够小的情况下,就算是O(n)的算法也可能会比O(log n)的算法更加高效。另外,一个算法可能在AMD处理器上的速度比在Intel处理器上快。如果你的系统有交换区的话,那么你还要考虑磁盘的性能。唯一可以确定的性能测试途径是用大小合适的数据来测试和衡量程序的性能和内存使用量。在你所选择的硬件上来测试这两种指标,是最合适的方法。

 

Q:如何权衡是用无序的数组还是有序的数组呢?

A:有序数组最大的优点在于n比较大的时候,搜索元素所花的时间O(log n)比无序素组所需要的时间O(n)要少很多。有序数组的缺点在于插入的时间开销比较大(一般是O(n)),因为所有比插入元素大的值都要往后移动。而无序数组的插入时间开销是常量时间,也就是说,插入的速度和元素的数量无关。下面的代码片段展示了向有序数组和无序数组插入元素。

插入元素到一个无序的数组里

 

package bigo;

import java.util.Arrays;

public class InsertingElementsToArray {

    public static void insertUnsortedArray(String toInsert) {

        String[ ] unsortedArray = { "A", "D", "C" };

        String[ ] newUnsortedArray = new String[unsortedArray.length + 1];
        System.arraycopy(unsortedArray, 0, newUnsortedArray, 0, 3);
        newUnsortedArray[newUnsortedArray.length - 1] = toInsert;
        System.out.println(Arrays.toString(newUnsortedArray));
    }

    public static void main(String[ ] args) {
        insertUnsortedArray("B");
    }
}

 

 

 

插入元素到一个有序数组

 

package bigo;

import java.util.Arrays;

public class InsertingElementsToArray {

    public static void insertSortedArray(String toInsert) {

        String[ ] sortedArray = { "A", "C", "D" };

        /*
         * Binary search returns the index of the search item
         * if found, otherwise returns the minus insertion point. This example
         * returns index = -2, which means the elemnt is not found and needs to
         * be inserted as a second element.
         */
        int index = Arrays.binarySearch(sortedArray, toInsert);

        if (index < 0) {                                   // not found.

            // array indices are zero based. -2 index means insertion point of
            // -(-2)-1 = 1,  so insertIndex = 1
            int insertIndex = -index - 1;

            String[ ] newSortedArray = new String[sortedArray.length + 1];
            System.arraycopy(sortedArray, 0, newSortedArray, 0,  insertIndex); 
            System.arraycopy(sortedArray, insertIndex,
                    newSortedArray, insertIndex + 1,  sortedArray.length - insertIndex);
            newSortedArray[insertIndex] = toInsert;
            System.out.println(Arrays.toString(newSortedArray));
        }
    }

    public static void main(String[ ] args) {
        insertSortedArray("B");
    }
}

 

 

 

所以,如何去选择还是取决于实际的使用情况。你需要考虑下面几个问题。你的程序是插入/删除的操作多,还是查找的操作多?数组里最多可能存储多少元素?排序的频率是多少?以及你的性能基准测试的结果是怎样的?

 

Q:怎么实现一个不可变集合?

A:这个功能在Collections类里实现了,它通过装饰模式实现了对一般集合的封装。

 

public class ReadOnlyExample {
    public static void main(String args[ ]) {
        Set<string> set = new HashSet<string>( );
        set.add("Java");
        set.add("JEE");
        set.add("Spring");
        set.add("Hibernate");
        set = Collections.unmodifiableSet(set);
        set.add("Ajax");                                           // not allowed.
  }
}
 

 

Q:下面的代码的功能是什么呢?其中的LinkedHashSet能用HashSet来取代吗?

 

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;

public class CollectionFunction {
    public <e> List<e> function (List <e> list) {
          return new ArrayList<e>(new LinkedHashSet<e>(list));
    }
}
 

 

A:上面的代码代码通过把原有列表传入一个LinkedHashSet来去除重复的元素。在这个情况里,LinkedHashSet可以保持元素原来的顺序。如果这个顺序是不需要的话,那么上面的LinkedHashSet可以用HashSet来替换。

 

Q:Java集合框架都有哪些最佳实践呢?

A:根据实际的使用情况选择合适的数据结构,例如固定大小的还是需要增加大小的,有重复元素的还是没有的,需要保持有序还是不需要,遍历是正向的还是双向的,插入是在末尾的还是任意位置的,更多的插入还是更多的读取,是否需要并行访问,是否允许修改,元素类型是相同的还是不同的,等等。另外,还需要尽早考虑多线程,原子性,内存使用量以及性能等因素。

不要假设你的集合里元素的数量一直会保持较小,它也有可能随着时间增长。所以,你的集合最好能够给定一个合适的大小。

针对接口编程优于针对实现编程。例如,可能在某些情况下,LinkedList是最佳的选择,但是后来ArrayList可能因为性能的原因变得更加合适

不好的方式:

 

ArrayList list = new ArrayList(100);

 

好的方式:

 

// program to interface so that the implementation can change
List list = new ArrayList(100);
List list2 = new LinkedList(100);

List emptyList = Collections.emptyList( );
Set emptySet = Collections.emptySet( );
 

 

在取得列表的时候,如果返回的结果是空的话,最好返回一个长度为0的集合或者数组,而不要返回null。因为,返回null的话可能能会导致程序错误。调用你的方法的开发人员可能会忘记对返回为null的情况进行处理。

封装好集合:一般来说,集合都是不可变的对象。所以尽量不要把集合的成员变量暴露给调用者。因为他们的操作一般都不会进行必要的校验。

原文:http://www.importnew.com/871.html

  • 大小: 13 KB
  • 大小: 13.6 KB
  • 大小: 19.3 KB
  • 大小: 15.5 KB
分享到:
评论

相关推荐

    java面试题,J2EE面试题 笔试题

    最全的j2EE面试题,题量...8、java面试题及答案 9、java面试题编程篇 10、Oracle面试题 11、Oracle企业面试题集锦 12、Spring面试题 13、SSH面试题 14、Strut+Spring+Hibernate面试题 15、张孝祥整理Java就业面试题大全

    常见的java,android面试题整理

    Java和Android面试题涵盖了许多核心概念,以下是这些知识点的详细说明: 1. **面向对象** (Object-Oriented Analysis and Design Principle, OOADP): 面向对象编程是Java和Android开发的基础,它涉及类、对象、继承...

    java常见面试题(史上最全最经典-希望对你有用)

    在这里,我们总结了Java常见的面试题,涵盖了Java的基础部分,包括基本语法、类相关的语法、内部类的语法、继承相关的语法、异常的语法、线程的语法、集合的语法、IO的语法、虚拟机方面的语法等。 1. Java基础部分 ...

    Java 最常见 200+ 面试题全解析:面试必备208题

    Java作为一门广泛使用的编程语言,其面试题涵盖了众多的知识领域,包括基础语法、面向对象、集合框架、多线程、网络编程、IO流、异常处理、JVM内存模型、设计模式、数据库操作、Spring框架等。以下是对这些知识点的...

    JAVA面试题总汇:j2ee面试知识.pdf

    因此,我将以标题中的“JAVA面试题总汇:j2ee面试知识”为基础,结合描述中的“安全”标签,对Java相关的面试知识点以及J2EE安全机制方面进行详细阐述。 ### Java面试题总汇:J2EE面试知识 #### 1. Java基础知识点...

    最新各大公司企业真实面试题-Java面试题

    本压缩包包含了一系列由IT资深专家单兴华整理的最新各大公司企业的真实Java面试题,旨在帮助求职者提升自己的技术水平和面试准备。 首先,我们来看"java练习题2.doc",这可能是针对基础语法和编程技巧的练习,涵盖...

    2017java面试题

    "2017java面试题"这个压缩包文件提供了丰富的资源,帮助Java开发者准备面试,深化对Java开发的理解。 文档"Java面试宝典2017.doc"可能包含了以下核心Java知识点: 1. **基础语法**:这包括变量、数据类型、运算符...

    JAVA面试题大集合

    Java面试题大集合是针对Java开发者的一份综合性的面试资源,涵盖了广泛的Java编程和技术知识。这份集合可能包括了从基础到高级的各种问题,旨在帮助Java程序员准备面试,提升技术理解和应用能力。以下是一些可能包含...

    200+最常见Java面试题参考答案(嗯嗯).pdf

    标题《200+最常见Java面试题参考答案(嗯嗯).pdf》说明这是一份包含了200多道最常见Java面试问题及其参考答案的PDF文档。Java作为一门编程语言,在全球范围内被广泛使用,尤其在企业级应用和安卓开发方面表现出色。...

    java常见的面试题汇总

    java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合java常见面试题集合...

    java面试题集合java面试题集合java面试题集合

    Java作为一门广泛使用...通过阅读《Java面试题笔试题大全》、《Java程序员上班那点事儿》、《Java程序员面试宝典》、《Java企业面试题》以及《华为_中软等大公司JAVA面试试题》等资料,可以系统地复习和巩固这些知识。

    java面试笔试题库java软件设计java笔试题大集合及答案文档资料合集300MB.zip

    Java面试题以及答案(小生).pdf java面试题(题库全).doc JS 数据库答案.doc Land.the.Tech.Job.You.Love-人人都有好工作—IT行业求职面试必读.pdf Linux命令大全完整版.doc sql查询语句练习.doc Web服务器的工作...

    java面试题总结资料

    这份"java面试题总结资料"涵盖了多个Java核心领域的关键知识点,包括但不限于: 1. **基础语法**:理解基本的数据类型(如整型、浮点型、字符型和布尔型),变量的声明与使用,以及运算符的优先级。同时,要熟悉...

    Java面试题以及答案整理.pdf

    为了在Java面试中脱颖而出,了解和掌握常见的面试题及答案至关重要。以下是一些关键知识点的详细解析: 1. **super()与 this()的区别** `super()`用于调用父类的构造器,确保子类实例化时父类的初始化;`this()`则...

    Java面试题2022

    以上是Java面试中常见的知识点,掌握并能深入解释这些内容,将大大增加你成功通过面试的可能性。同时,面试不仅仅是对技术的考察,还包括问题解决能力、团队合作精神以及项目经验等软技能,全面展现自己才能赢得理想...

    JAVA面试题2019

    以上是对“JAVA面试题2019”中提及的一些核心知识点的总结,涵盖了项目介绍、Java基础知识、并发编程、Spring框架、Netty框架以及分布式系统等方面的知识点。这些知识点不仅对于准备Java面试至关重要,同时也是Java...

    Java面试常见面试题

    Java作为一门广泛使用的编程语言,其面试题涵盖了多个核心领域,包括基础语法、高级特性、容器、并发编程、SSM框架、JVM优化、数据库管理、服务器配置以及分布式技术。以下将详细介绍这些知识点: 1. **Java基础**...

    java面试题总结

    在Java面试中,面试官通常会考察应聘者的语法基础、数据结构与算法、多线程、集合框架、异常处理、IO流、网络编程、设计模式等多个方面的能力。以下是对这些关键知识点的详细阐述: 1. **Java语法基础**:Java的...

    java面试题集合,包含各种java常见面试题型,一些是chm格式

    这份压缩包文件“java面试题”显然是一个集大成者,包含了各种Java面试中可能遇到的问题,旨在帮助求职者充分准备,提高面试通过率。 1. **基础语法**:Java的基础语法包括变量、数据类型、运算符、流程控制语句...

Global site tag (gtag.js) - Google Analytics