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的情况进行处理。
封装好集合:一般来说,集合都是不可变的对象。所以尽量不要把集合的成员变量暴露给调用者。因为他们的操作一般都不会进行必要的校验。
相关推荐
U盘量产工具FLASH量产工具SM3280&3281&3282-AvidiaV0209整合版
java课程期末考试
分布式消息中间件,参考kafka,未完成
修木工施工规范及流程.docx
内容概要:本文详细介绍了VECTOR提供的MICROSAR OBD协议栈解决方案,涵盖了OBD模块、ECU支持、监控功能和服务请求等方面的内容。此外,还讨论了OBD在不同国家和地区的技术标准与法规要求,以及MICROSAR OBD解决方案的优势,如适应不同项目的需求和高度集成于AUTOSAR 4平台。 适合人群:汽车电子工程师、软件开发者、汽车制造商及相关行业从业人员。 使用场景及目标:① 适用于车辆诊断系统的开发和维护;②帮助工程师理解和掌握OBD协议的具体实施方法和应用场景;③ 提供了一个成熟、可扩展的解决方案,用于满足OBD相关标准和法规的要求。 其他说明:本文不仅提供了技术层面的详细解析,还探讨了实际操作过程中可能遇到的问题和解决方案。同时强调了屏蔽信息过载的重要性,提醒工程师保持内心平静,专注做好本职工作。
适用于 Python 的 LINE 消息 API SDK适用于 Python 的 LINE Messaging API 的 SDK。介绍适用于 Python 的 LINE Messaging API SDK 可以轻松使用 LINE Messaging API 开发机器人,您可以在几分钟内创建一个示例机器人。文档请参阅官方 API 文档了解更多信息英语https //developers.line.biz/en/docs/messaging-api/overview/日语https://developers.line.biz/ja/docs/messaging-api/overview/要求Python >= 3.9安装$ pip 安装 line-bot-sdk概要用法from flask import Flask, request, abortfrom linebot.v3 import ( WebhookHandler)from linebot.v3.exceptions import ( InvalidSig
Java字节码工程工具包Javassist 版本 3版权所有 (C) 1999-2023 Shigeru Chiba,保留所有权利。Javassist(JAVA 编程助手)使 Java 字节码操作变得简单。它是一个用于编辑 Java 字节码的类库它使 Java 程序能够在运行时定义新类并在 JVM 加载类文件时对其进行修改。与其他类似的字节码编辑器不同,Javassist 提供两个级别的 API源代码级别和字节码级别。如果用户使用源代码级别 API,他们可以编辑类文件而无需了解 Java 字节码的规范。整个 API 仅使用 Java 语言的词汇表进行设计。您甚至可以以源文本的形式指定插入的字节码Javassist 会即时编译它。另一方面,字节码级别 API 允许用户像其他编辑器一样直接编辑类文件。该软件根据 Mozilla 公共许可证版本 1.1、GNU 宽通用公共许可证版本 2.1 或更高版本或 Apache 许可证版本 2.0 分发。文件README.md 此自述文件。Changes.md 发行说明。License.html 许可证文件。tuto
本项目是基于Python语言开发的西西家居全屋定制系统,旨在为家居行业提供一个高效、智能的定制解决方案。项目涵盖了从客户需求分析、设计方案生成、材料选购到最终订单生成的全过程,力求实现家居定制的数字化和智能化。 在主要功能方面,系统具备强大的客户管理模块,能够详细记录和分析客户的定制需求。设计模块则采用先进的三维建模技术,为客户提供直观、真实的家居设计方案预览。此外,系统还整合了丰富的材料数据库,方便客户根据自身喜好和预算进行材料选择。 框架方面,项目采用了B/S架构,确保了系统的稳定性和可扩展性。后端使用Python的Django框架,前端则结合了HTML、CSS和JavaScript等技术,实现了用户界面的友好和响应速度。 开发此项目的目的,不仅是为了满足家居行业对个性化定制的需求,也为计算机相关专业的学生提供了一个实践和学习的平台,有助于提升他们的实际开发能力。
Javascript 是数字化创新的起点,是语言的基础,也是基本概念。Basecamp JavascriptJavascript 是数字化创新的起点,是语言的基础,也是基本概念。嵌套存储库,可作为启动项下待办事项的实践活动。
已弃用 — Coinbase Python APICoinbase Coinbase API V2的官方 Python 库。重要提示此库当前针对的是 API V2,而 OAuth 客户端需要 V2 权限(即wallet:accounts:read)。如果您仍在使用 API V1,请使用此库的旧版本。特征接近 100% 的测试覆盖率。支持API Key + Secret和OAuth 2身份验证。调用 API 的便捷方法 - 为您打包 JSON!自动将 API 响应解析为相关的 Python 对象。使用IPython时,所有对象都具有可制表完成的方法和属性。安装coinbase可以在PYPI上使用。使用以下命令安装pippip install coinbase或者easy_installeasy_install coinbase该库目前针对 Python 版本 2.7 和 3.4+ 进行了测试。注意此软件包名称过去是指George Sibble维护的非官方 coinbase_python 库。George 慷慨地允许我们使用此软件包
基于RBAC权限控制的基础后台
本项目是基于Python爬虫的网络小说数据分析系统的设计与实现,旨在为计算机相关专业的大学生提供一个实践平台,特别是在毕业设计和项目实战练习方面。项目通过Python强大的网络爬虫技术,从流行的网络小说网站自动抓取数据,包括书籍信息、章节内容、用户评论等。 主要功能涵盖数据采集、数据清洗、数据存储和数据分析。数据采集模块利用Scrapy等爬虫框架高效抓取网页内容;数据清洗模块确保数据的准确性和一致性;数据存储则采用MySQL等数据库系统,便于数据管理和查询;数据分析模块通过Pandas、NumPy等工具进行数据处理和分析,生成多维度的统计报告和可视化图表。 此项目不仅帮助学生掌握Python编程和网络爬虫技术,还能让他们深入了解数据分析的全过程,提升解决实际问题的能力。同时,系统的实现和应用也反映了现代信息技术在文学创作和消费领域的应用价值和潜力。
本项目是一个基于Java的在线日语培训平台的设计与实现,采用SSM框架(Spring+SpringMVC+MyBatis)进行开发,旨在为计算机相关专业的学生提供一个实践和学习的平台,同时也为日语学习者提供一个在线学习的空间。项目中主要功能涵盖了用户管理、课程管理、学习资源上传下载、在线测试与反馈等多个方面。通过该平台,教师能够轻松管理课程内容和学生信息,学生则可以随时随地访问学习资源,参与在线课程和测试,从而提高学习效率和兴趣。 在开发此项目的过程中,我们重点关注了系统的可维护性和可扩展性,确保代码结构清晰,便于后续的功能迭代和优化。此外,通过使用SSM框架,实现了前后端的分离,提高了开发效率和系统的响应速度。该项目不仅能够满足毕设的需求,还能作为Java学习者提升编程能力和实践经验的实用工具。
基于java的机票管理系统设计与实现.docx
该项目为《基于Java实现的数据结构设计源码》,共包含51个文件,主要由46个Java源文件构成,辅以2个文本文件、1个Git忽略文件、1个许可证文件以及1个XML文件,全面涵盖了数据结构设计的核心内容。
绿色食品 水稻生产操作规程.docx
他妈的 Fuck是一款出色的应用程序,其灵感来自@liamosaur 的 推文,它可以纠正以前控制台命令中的错误。The Fuck太慢了吗?试试实验性的即时模式!更多示例➜ apt-get install vimE: Could not open lock file /var/lib/dpkg/lock - open (13: Permission denied)E: Unable to lock the administration directory (/var/lib/dpkg/), are you root?➜ fucksudo apt-get install vim [enter/↑/↓/ctrl+c][sudo] password for nvbn:Reading package lists... Done...➜ git pushfatal: The current branch master has no upstream branch.To push the current branch and set the remote
全国大学生FPGA创新设计竞赛作品 “泡罩包装药品质量在线检测平台“.zip
桃苗木质量基本要求表.docx
使用 Python 漂亮地打印表格数据,这是一个库和一个命令行实用程序。存储库从 bitbucket.org/astanin/python-tabulate 迁移而来。python-tabulate使用 Python、库和命令行实用程序漂亮地打印表格数据。该库的主要用例是轻松打印小表格只需一个函数调用,格式由数据本身引导为轻量级纯文本标记创作表格数据多种输出格式适合进一步编辑或转换混合文本和数字数据的可读表示智能列对齐、可配置数字格式、小数点对齐安装要安装 Python 库和命令行实用程序,请运行pip install tabulate命令行实用程序将在 Linux 上安装为(例如tabulate)或者在 Windows 上的 Python 安装中安装为(例如)。bin/usr/bintabulate.exeScriptsC:\Python39\Scripts\tabulate.exe您可以考虑仅为当前用户安装该库pip install tabulate --user在这种情况下,命令行实用程序将安装到 ~/.local/bin/tabula