起源：ImportNew - 朱伟杰

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，文本编辑器里的撤销动作，浏览器里的浏览记录，等等。这里是一些对于堆栈的一些Java面试题。

队列和堆栈有些类似，不同之处在于在队列里第一个插入的元素也是第一个被删除的元素（即是先进先出）。这种先进先出的构造是通过只提供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处理器上快。如果你的零碎有替换区的话，那么你还要思考磁盘的性能。惟一能够确定的性能测试路径是用大小适合的数据来测试和掂量程序的性能和内存使用量。java培训在你所抉择的硬件上来测试这两种指标，是最合适的办法。

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 changeList list = new ArrayList(100);List list2 = new LinkedList(100);List emptyList = Collections.emptyList( );Set emptySet = Collections.emptySet( );

在获得列表的时候，如果返回的后果是空的话，最好返回一个长度为0的汇合或者数组，而不要返回null。因为，返回null的话可能能会导致程序谬误。调用你的办法的开发人员可能会遗记对返回为null的状况进行解决。

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