来源：ImportNew-朱伟杰JavaCollectionFramework（比如基础数据结构）包含了最常见的Java常见面试题。很好地理解集合框架可以帮助您理解和利用Java的一些高级特性。下面是一些非常实用的面试Java核心技术的问题。Q：最常见的数据结构有哪些，应用于哪些场景？A.大多数人会错过树和图这两种数据结构。树和图都是有用的数据结构。如果你在回答中提到它们，面试官可能会对你进行进一步的评估。Q：你是如何自己实现List、Set、Map的？A：虽然Java已经提供了这些接口的经过验证和测试的实现，但是面试官还是喜欢问这个问题来测试你对数据结构的理解。我的书《Core Java Career Essentials》用插图和代码详细解释了这些。常用数据结构数组是最常用的数据结构。数组的特点是长度固定，可以通过下标进行索引，所有元素的类型相同。数组的常见场景包括：从数据库中读取员工信息存储为EmployeeDetail[]，将字符串转换存储为字节数组以便于操作和处理等。尽量把数组封装在一个类中，防止数据被错误的操作弄乱。此外，这也适用于其他数据结构。列表类似于数组，只是它的大小可以改变。列表通常实现为固定大小的数组，在需要时会自动调整大小。列表可以包含重复的元素。常见的场景包括在订单列表中添加新的一行商品，从商品列表中移除所有过期的商品等等。通常，将列表初始化为适当的大小以减少调整大小的次数。集合类似于列表，只是它们不能包含重复的元素。当您需要存储不同的元素时，您可以使用集合。堆栈只允许对最后插入的元素进行操作（即后进先出-LIFO）。如果移除栈顶元素，则可以对倒数第二个元素进行操作，依此类推。这种后进先出的方法是通过仅对peek()、push()和pop()方法进行强制约束来实现的。这种结构在很多场景下都非常有用，比如解析像(4+2)*3这样的数学表达式，将源代码中的方法和异常按照出现的顺序放在栈上，检查你的代码看是否做圆括号和花括号match等。这种用栈实现的后进先出（LIFO）机制在很多地方都非常实用。例如，表达式求值和语法解析、验证和解析XML、文本编辑器中的撤消操作、浏览器中的浏览历史等。这里有一些关于堆栈的Java面试问题。队列有点类似于栈，只是队列中第一个插入的元素也是第一个被移除的元素（即先进先出）。这种先进先出结构是通过仅提供peek()、offer()和poll()方法来限制对数据的访问来实现的。比如排队等公交车，去银行或者超市排队等等，都可以用队列来表示。链表是由多个节点组成的数据结构，每个节点包含数据和对下一个节点的引用。在双向链表中，还有对前一个节点的引用。比如栈和队列可以用单向链表和双向链表来实现，因为链表的两端都可以插入和删除。当然，也会有链表中间频繁插入和删除节点的场景。Apache的类库提供了TreeList的实现，它是链表的一个很好的替代品，因为它只占用多一点内存，但性能却比链表好很多。也就是说，从这个角度来看，链表其实并不是一个好的选择。ArrayList是列表的一个很好的实现。ArrayList与TreeList相比，除了在列表中间插入或删除元素外，ArrayList比TreeList快很多。TreeList的实现内部使用了树结构，保证了所有插入和删除动作的复杂度为O(logn)。这种实现使得TreeList在频繁插入和删除元素时的性能远高于ArrayList和LinkedList。类链接{私人intid;//数据私有字符串名称；//下一个数据私有链接；//参考下一个链接}HashMap的访问时间接近稳定，是一个键值对映射的数据结构。这个数据结构是通过一个数组来实现的。它使用散列函数来定位元素，并使用碰撞检测算法来处理散列到同一位置的值。例如可以将员工的id作为key保存员工信息，从properties文件中读取的attribute-attribute值可以用key/value对保存等等。HashMap在初始化时，给定一个合适的大小可以减少调整大小的次数。树是由节点组成的数据结构，每个节点包含数据元素，并有一个或多个子节点，每个子节点指向一个父节点（译者注：根节点除外）可以表示层次关系或数据元素序列关系.常用的场景有表示组织中员工的层级关系、XML元素的层级关系等。如果树的每个子节点最多有两个叶节点，那么这样的树就称为二叉树。二叉树是一种非常常用的树结构，因为它的结构使得节点的插入和删除非常高效。树的边代表从一个节点到另一个节点的捷径。Java并没有直接提供树的实现，但是通过下面的方式很容易实现。您只需要创建一个Node对象，其中包含一个指向叶节点的ArrayList。包bigo；导入java.util.ArrayList；导入java.util.List；公共类节点{私有字符串名称；privateListchildren=newArrayList();私有节点父节点；publicNodegetParent(){返回父节点；}publicvoidsetParent(Nodeparent){this.parent=parent;}publicNode(Stringname){this.name=name;}publicvoidaddChild(Nodechild){children.add(child);voidremoveChild(Nodechild){children.remove(child);}publicStringtoString(){返回名称；}}只要数据元素之间的关系可以表示为节点和边的网络结构，就可以用图来表示。树是一种特殊的图，其中所有节点都可以只有一个父节点。与树不同，图的形状由实际问题或问题的抽象决定。例如，图中的节点（或顶点）可以代表不同的城市，图中的边可以代表两个城市之间的航线。要用Java构建图，需要解决数据如何存储和访问的问题。图中也使用了上面提到的数据结构。JavaAPI中没有提供图形实现。不过第三方库很多，比如JUNG、JGraphT、JDSL（不过好像不支持泛型）。《Core Java Career Essential》这本书包含用Java实现的可用示例。问：你对大O表示法了解多少？你能举一些基于不同数据结构的例子吗？A：大O表示法可以表示一个算法的效率，也可以用来描述当数据元素数量增加时算法在最坏情况下的性能。大O表示法也可以用来衡量内存消耗等性能。有时您可能会选择较慢的算法以减少内存使用。大O表示法可以表示程序在大量数据情况下的性能。然而，在大量数据下衡量程序性能的唯一实用方法是使用更大的数据集进行性能基准测试，其中可以包括一些在大O复杂度分析中没有考虑的情况。进去，比如当虚拟内存使用多了，系统就会换页。虽然基准测试比结果的大O符号更现实，但在设计阶段并不适用，因此大O复杂性分析是此时最合适的选择。各种数据结构在查找、插入和删除算法中的性能可以用以下方式表示：常量复杂度O(1)、线性复杂度O(n)、对数复杂度O(logn)、指数复杂度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(logn)。在链表中查询节点的复杂度一般为O(n)。相对于数组链表和数组的O(logn)性能，随着元素数量的增长，链表的O(n)复杂度性能相对较差。对数时间复杂度是，如果10个元素需要x个时间单位，100个元素最多需要2x个时间单位，10000个元素最多需要4x个时间单位。如果在平面坐标上画图，你会发现时间的增长没有n（元素个数）快。Q：HashMap和TreeMap的性能区别是什么？您更喜欢使用哪一个？A：平衡树的性能是O(logn)。Java中的TreeMap使用红黑树来保证key/value的顺序。红黑树是平衡二叉树。保证二叉树的平衡，使得插入、删除和查找更快，时间复杂度为O(logn)。但是，它没有HashMap快，而且HashMap的时间复杂度是O(1)，但是TreeMap的优点是里面的key和value是排序的，提供了一些其他有用的功能。Q：如何选择使用哪一个？A：使用无序的HashSet和HashMap，还是使用有序的TreeSet和TreeMap，主要看你的实际使用场景，一定程度上也和数据的大小、运行环境有关。一个更实际的原因是，如果插入和更新都很频繁，保持元素有序可以提高快速和频繁查找的性能。如果排序操作的需求（比如生成报表伙伴运行批处理程序）不是很频繁，那么就把数据无序存储，需要排序的时候再用Collections.sort(…)排序，可能比以有序的方式存储它们更有效。这只是一种可选的方式，没有人能给你一个肯定的答案。即使是复杂度理论，如O(n)，也只有当n足够大时才成立。只要n足够小，即使是O(n)算法也可能比O(logn)算法更有效。此外，算法在AMD处理器上可能比在Intel处理器上更快。如果你的系统有交换区，那么你还需要考虑磁盘的性能。确保性能测试的唯一方法是使用适当大小的数据测试和测量程序的性能和内存使用情况。Java培训是在您选择的硬件上测试这两个指标最合适的方法。Q：如何权衡是使用无序数组还是有序数组？A：有序数组最大的优点是当n比较大时，查找元素的时间O(logn)远小于无序元素组所需的时间O(n)。有序数组的缺点是插入时间比较长（通常是O(n)），因为所有大于插入元素的值都得往回移。无序数组的插入时间开销是常量时间，即插入速度与元素个数无关。以下代码片段演示了将元素插入已排序和未排序的数组中。插入元元素到一个无序的数组packagebigo;importjava.util.Arrays;publicclassInsertingElementsToArray{publicstaticvoidinsertUnsortedArray(StringtoInsert){String[]unsortedArray={"A","D","C"};String[]newUnsortedArray=newString[unsortedArray.length+1];System.arraycopy(unsortedArray,0,newUnsortedArray,0,3);newUnsortedArray[newUnsortedArray.length-1]=toInsert;System.out.println(Arrays.toString(newUnsortedArray));}publicstaticvoidmain(String[]args){insertUnsortedArray("B");}}插入元元素到一个有顺序的数组packagebigo;importjava.util.Arrays;publicclassInsertingElementsToArray{publicstaticvoidinsertSortedArray(StringtoInsert){String[]sortedArray={"A","C","D"};/**二分搜索返回搜索项的索引*如果找到，否则返回减号插入点。这个例子*返回index=-2，这意味着元素是未找到，需要*作为第二个元素插入。*/intindex=Arrays.binarySearch(sortedArray,toInsert);if(index<0){//没有找到。//数组索引从零开始。-2索引表示插入点//-(-2)-1=1，所以insertIndex=1intinsertIndex=-index-1;String[]newSortedArray=newString[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));}}publicstaticvoidmain(String[]args){insertSortedArray("B");所以，如何选择取决于实际使用情况，需要考虑以下问题。你的程序有很多插入/删除操作，或者很多查找操作吗？数组中最多可以存储多少个元素？它多久排序一次？您的性能基准测试结果是什么？Q：如何实现不可变集合？A：这个功能是在Collections类中实现的，通过装饰方式实现对通用集合的封装。publicclassReadOnlyExample{publicstaticvoidmain(Stringargs[]){Setset=newHashSet();set.add("Java");set.add("JEE");set.add("弹簧");set.add("休眠");set=Collections.unmodifiableSet(set);set.add("Ajax");//不允许。}}问：下面代码的作用是什么？LinkedHashSet可以用HashSet代替吗？importjava.util.ArrayList;importjava.util.LinkedHashSet;importjava.util.List;publicclassCollectionFunction{publicListfunction(Listlist){returnnewArrayList(newLinkedHashSet(列表));}}A：上面的代码通过将原始列表传递给LinkedHashSet来删除重复元素。在这种情况下，LinkedHashSet可以保持元素的原始顺序。如果不需要这个顺序，那么上面的LinkedHashSet可以用HashSet代替。问：Java集合框架的最佳实践是什么？A：根据实际使用情况选择合适的数据结构，比如固定大小还是需要增加大小，是否有重复元素，是否需要保持顺序，是正向遍历还是双向遍历，以及插入isin是在末尾还是在任何地方，插入多还是读多，是否需要并行访问，是否允许修改，元素类型相同还是不同等。另外还有多线程、原子性、内存占用等因素，并且需要尽早考虑性能。不要假设你的集合中的元素数量总是很少，它也会随着时间的推移而增加。因此，最好为您的收藏提供合适的尺寸。针对接口编程比针对实现编程更好。例如，可能存在LinkedList是最佳选择的情况，但出于性能原因，ArrayList可能变得更合适。坏方法：ArrayListlist=newArrayList(100);好的方法：//编程到接口以便实现可以更改如果结果为空，最好返回一个长度为0的集合或数组，而不是返回null。因为，返回null可能会导致程序错误。调用您的方法的开发人员可能会忘记处理空返回。封装集合：一般来说，集合是不可变的对象。所以尽量不要把集合的成员变量暴露给调用者。因为他们的操作一般不会进行必要的检查。
