最常见的Java常见面试题问答(3)_面试精选

最常见的Java常见面试题问答(3)

发表于：2013-01-24来源：ImportNew作者：不详点击数：标签：java

只要数据元素的关系可以表示成节点和边的网状结构的话，就可以用图来表示。树是一种特殊的图，它的所有节点都只能有一个父节点。和树不同的是，图

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

　　在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"); 

						    } 

						}

原文转自：http://www.importnew.com/871.html

软件测试 > 测试技术 > 软件测试工程师职业发展 > 面试精选 >