java中各种算法和数据结构的使用场景
一。通用数据结构：数组，链表，树，哈希表
通用数据结构通过关键字的值来存储并查找数据，如报表，合同，记录，业绩等数据。通用数据结构可以用速度的快慢来分类，数组和链表是最慢的，树相对较快，哈希表是最快的。请注意，并不是最快的就一定是最好的，因为最快的结构的程序在不同程度上比数组和链表的复杂，而且哈希表要求预先要知道存储多少数据，数据对存储空间的利用率也不是非常高。普通的二叉树对顺序的数据来说，会变成缓慢的O(N)级操作，平衡树虽然避免了这个问题，但程序编写却比较困难。
通过数据结构的关系可以用这个图来表示：
随着计算机硬件性能的不断提升，CPU的计算速度也越来越快，所以首选简单数据结构，除非他们真的表现太慢，否则不要采用复杂的数据结构，只要运行结果在可接受范围内，没人会在乎你用了什么数据结构的。
在操作对象的速度上，java比其他语言有优势，对于大多数数据结构来说，java只存储引用而不是实际的对象。在分析算法时，不是从对象的真实存储空间出发，因而移动对象的速度也不依赖于对象的大小，只是考虑对象引用的移动，而对象本身的大小就不重要了。在编程语言中，类库会封装一些数据结构和算法，所以在选择类库时要确保这个类能真正适应特定的业务场景。
1.数组
存储和操作数据时，大多数情况下，数组是首选的，数组最有用的情况是数据量较小和数据量的大小事先可预测。数组元素的删除总是很慢，因为为了填充空出来的单元，平均半数以上的数组元素要被移动。在有序数组中的遍历是很快的。向量是一种当数据太满时可以自己扩充空间的数组，向量可以应用于数据量不可预知的情况下，但是向量在扩充时，要将旧的数据拷贝到一个新的空间，这个过程会造成程序的周期性暂停。
2，链表
如果需要存储的数据量不能预知或需要频繁的插入删除数据元素，考虑使用链表。当有新的元素加入时，链表就开辟新的空间，它甚至可以占满所有可用空间，在删除过程中不会像数组那样填补空缺。在一个无序链表中，插入很快，查找和删除却很慢，因此，与数组一样，链表最好也应用于数据量较小的场景。相比之下，链表比数组复杂，但比树和哈希表简单。
3.二叉搜索树
当确认数组和链表过慢时，最先考虑的是二叉树，树可以提供快速的O(logN)级的插入，查找，删除，遍历的时间复杂度是O(N)级的，对于遍历一定范围内的数据可以很快得到访问数据的最大值和最小值。对于程序，不平衡的二叉树要比平衡二叉树简单的多，但是有序数据能将它的性能降低到O(N)级，并不比链表好。如果能保证数据是随机的，就不需要用平衡二叉树。
4.平衡树
红黑树和多叉树都是平衡树，无论数据是否有序，都能保证性能是O(logN)。对于编程来说，最难的是红黑树（应用最广泛）。它们也因用了附加存储而产生额外耗费，这对系统多少都有些影响。利用树的类库可以降低编程困难度，某些情况下，选择哈希表比平衡树要好。
5.哈希表
哈希表在数据存储结构中速度最快，哈希表通常用于拼写检查器和作为计算机编程语言中的编译器的符号表。哈希表对数据插入的顺序并不敏感，因此可以取代平衡树，而且哈希表的编程比平衡树简单多了。哈希表需要有额外的存储空间，因为哈希表用数组作为基本结构，所以预先必须精确的知道待存储的数据量。用链地址法处理冲突的哈希表是最好的实现方法。
哈希表并不能提供任何形式的有序遍历，或对最大最小值元素进行存取，实现这些功能使用二叉搜索树更好一些。
二。专用数据结构：栈，队列，优先级队列
这些结构不是为了用户可访问的数据库而建立的，通常用它们在程序中辅助实现一些算法。这些结构都不支持查找或遍历。
栈，队列，优先级队列都是抽象数据类型（ADT），它们由一些更加基础的结构如数组，链表，堆组成。这些ADT只提供给用户简单的接口，一般只允许用户插入和访问或删除一个数据项（栈：最后被插入的数据；队列：最先被插入的数据；优先级队列：具有最高优先级的数据）。
1.栈
是一个后进先出的结构，往往通过数组或链表实现，因为最后被插入的数据总是在数组的最后，这个位置的数据很容易被删除。栈的溢出有可能会出现，通过合理规划数组的大小可以避免，而且栈很少会拥有大量的数据。如果栈拥有大量的数据，并且数量不可精确预测（用栈实现递归时），用链表比数组更好一些，因为从表头的位置删除或插入一个元素很方便，除非整个内存满了。链表比数组稍慢一些，因为对于插入一个新链接必须分配内存，从表中某个链接点上删除元素后回收分配内存也是必需的。
2，队列
是一个先进先出的结构，同样可以通过数组和链表实现，数组需要附加的程序来处理队列在数组尾部回绕的情况。链表必须是双端的，这样才能从一段插入从另一端删除。如果知道数据量的多少就可以用数组，否则用链表。
3.优先级队列
优先级队列用在只对访问最高优先级数据项访问的时候，最高优先级数据项就是含有最大或最小的关键字的项。
可以用有序数组或堆来实现。向有序数组中插入是很慢的，但删除很快。使用堆来实现优先级队列，插入和删除的时间复杂度都是O(logN)级。当插入速度不重要时，可以使用数组或双端链表，数据量可以被预测时，使用数组，数据量未知时使用链表，如果速度很重要的话，选择堆更好。
三。排序：插入排序，希尔排序，快速排序，归并排序，堆排序
随着计算机的处理能力越来越快，在实际中，选择数据结构时，可以先尝试选择一种较慢但简单的排序，如插入排序（这里指数据量小于1000的数据），插入排序如果没有太多的元素处于乱序的位置，操作的时间复杂度约为O(N)级，通常是在往一个已经排好序的文件中插入一些新的数据元素的场景下。如果插入排序显得太慢，可以尝试希尔排序，根据经验，数据量在5000以下时很有用。只有当希尔排序变得很慢时，才应该考虑复杂的算法，如归并排序，堆排序，快速排序。归并排序需要辅助存储空间，堆排序需要有一个堆的数据结构，在某些程度上这两种都比快速排序慢，所以经常会优先选择快速排序。但是快速排序在处理非随机性数据时性能不太好。如果有可能是非随机性数据，堆排序更好。
四。图：邻接矩阵，邻接表
图并不存储通用数据，也不会在其他算法中成为程序员的工具，它们直接模拟现实世界的情况，图的形状直接反映了问题的结构。没有其他数据结构可以取代图的使用。根据图的疏密程度，稠密的图选择邻接矩阵，稀疏的图用邻接表。邻接矩阵表示的图的深度优先搜索和广度优先搜索时间复杂度为O(V*V)级，V是顶点的个数。邻接表表示的图的两种操作时间复杂度是O(V+E)级，E是边的条数。使用前，先估计图中的V和E，然后计算哪种表示方法更合适。
五。外部存储：顺序存储，索引文件，B-树，哈希方法
如果数据量大到内存容不下时，只能被存储到外部存储空间，一般是磁盘文件。存在磁盘文件中具有固定大小单元的数据称为块，每个块都存储一定数量的记录（磁盘文件中的记录拥有与主存中对象相同的数据类型）。与对象一样，每条记录都有一个关键字值，通过它可以访问到这条记录。假设读写操作总是在一个单一的块中进行，这些读写操作比对主存中的数据进行任何操作都要耗时的多，为了提高操作速度必须将磁盘的存取次数减到最小。
1.顺序存储
通过特定的关键字进行搜索的最简单的方法是随机存储记录然后顺序读取，新的记录可以被简单的插入到文件的最后，已删除的记录可以标记为已删除或将记录移动，同数组中一样来填补空缺。
平均来看，查找和删除会涉及到读取半数的块，所以顺序存储并不快，时间复杂度为O(N)级，但是对于小量数据它仍然是可以选择的。
2.索引文件
使用索引文件时，速度会明显的提高。在这种方法中，关键字的索引和相应块的号数被存放在内存中，通过一个特殊的关键字访问一条记录时，程序会先向索引询问，索引提供这个关键字的块号数，然后只需要读取这一个块，仅耗费了O(1)级的时间。可以使用不同种类的关键字来做多种索引，只要索引数量能在内存的存储范围之内。通常，索引文件存储在磁盘上，只有在需要时才复制进内存中。
索引文件的缺点是必需先创建索引，这有可能会对磁盘上的文件进行顺序读取，所以创建索引是很慢的。当记录被加入到文件中时，索引还需要更新。
3.B-树
B-树是多叉树，通常用于外部存储，树中的节点对应于磁盘中的块。跟其他树一样，根据算法来遍历树，在每一层上读取一个块。B-树可以在O(logN)级的时间内进行查找，插入和删除，这样很快，并且对大文件也很有效。但是编程很麻烦。
4.哈希方法
外部哈希同索引文件有相同的存取时间O(1)，但它可以对更大的文件进行操作，如图选择外部存储结构：
5.虚拟内存
有时可以不需要编程，通过操作系统的虚拟内存来解决磁盘存取问题，如果读取一个大小超过主存的文件，虚拟内存系统会读取合适主存大小的部分并将其存储在磁盘上。当访问文件的不同部分时，它们会自动从磁盘读入并放置在内存中。可以对整个文件使用内部存储的算法，使它们好像同时都在内存中一样，如果文件的哪个部分不在内存中，也让操作系统去读取它们。当然，这个操作比整个文件在内存中的操作要慢的多，但是通过外部存储算法一块一块的处理文件的话，速度也是一样的慢。不要在乎文件的大小适合放在内存中，在虚拟内存的帮助下验证算法的好坏尤其是对那些比可用内存大不了多少的文件来说，这个解决方案更简单。