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。
HashMap的访问时间接近稳定，它是一种键值对映射的数据结构。这个数据结构是通过数组来实现的。它通过hash函数来给元素定位，并且用冲突检测算法来处理被hash到同一位置的值。例如，保存雇员的信息可以用雇员的id来作为key，对从properties文件里读入的属性-属性值可以用key/value对来保存，等等。HashMap在初始化的时候，给定一个合适的大小可以减少调整大小的次数。
树是一种由节点组成的数据结构，每个节点都包含数据元素，并且有一个或多个子节点，每个子节点指向一个父节点(译者注：除了根节点)可以表示层级关系或者数据元素的顺序关系。常用的场景有表示一个组织里的雇员层级关系，XML元素的层级关系，等等。如果树的每个子节点最多有两个叶子节点，那么这种树被称为二叉树。二叉树是一种非常常用的树形结构， 因为它的这种结构使得节点的插入和删除都非常高效。树的边表示从一个节点到另外一个节点的快捷路径。
Q：HashMap和TreeMap在性能上有什么样的差别呢?你比较倾向于使用哪一个?
A：一个平衡树的性能是O(logn)。Java里的TreeMap用一个红黑树来保证key/value的排序。红黑树是平衡二叉树。保证二叉树的平衡性，使得插入，删除和查找都比较快，时间复杂度都是O(log n)。不过它没有HashMap快，HashMap的时间复杂度是O(1)，但是TreeMap的优点在于它里面键值是排过序的，这样就提供了一些其他的很有用的功能。
Q：如何权衡是用无序的数组还是有序的数组呢?
A：有序数组最大的优点在于n比较大的时候，搜索元素所花的时间O(log n)比无序素组所需要的时间O(n)要少很多。有序数组的缺点在于插入的时间开销比较大(一般是O(n))，因为所有比插入元素大的值都要往后移动。而无序数组的插入时间开销是常量时间，也就是说，插入的速度和元素的数量无关。 |
收藏
淘帖
踩
