java中的数据结构

前言

之前遇到一个问题，具体是说： 当我们用HashMap的时候，是怎样考虑优化其性能的呢？当时就一脸懵逼，原来是因为hashmap的自动扩容影响了性能，后面查资料才知道，可以通过设置hashmap的合理的初始容量或者加载因子来优化。 工作了一段时间了，连这个都不知道表示很羞愧。然后就去查看了一些关于数据结构的知识。其实也常常听说数据结构包括链表，队列，栈，树和二叉树，图等。但是在java中具体的应用有哪些呢？抱着一种好奇的心态去整列了一下java中的数据结构。

大概整理如下图

大概结构图

我在开发过程中用的最多的就属hashmap和arrayList。树和二叉树看了很久还是不明所以，后面再逐步修改吧。

线性表

• linkedList 就是基于双向链表的结构其插入，删除，新增的性能强于arrayList。因为arrayList本质就是数组,其需要的内存空间必须是连续的，所以当需要插入一条数据时，若在末端增加数据，其性能消耗也还好，但是若在任意位置插入就需移动数据的位置。linkedList 需要的内存空间可以不连续，插入数据时只需要改变节点的prev和next的指向就行了。
• linkedList 随机访问get和set就没有arrayList快了。linkedList需要移动指针。
• 栈 先进后出，java中vector 是栈的应用，其线程安全，性能差。其实现类是stack类
• 队列 先进先出，java中的Queue是和List一样继承于collection。上图用链表实现队列的方法是用C语言实现，队列最常见的应用就是异步消息，日志等，如Android中的handler的messageQueue。

hash表（散列表）

java中的Map。其中的实线类有 HashTable，HashMap，WeakHashMap.其中weakhashMap是一种对key 弱引用map。写到这里就想起了hashmap的原理以及hashmap与hashset的区别等，然后可以参看hashmap的原理

• hashTable 不允许null key和null value，线程安全，单线程操作性能差。 通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。
• hashmap 允许null key和null value 但是是异步的，所以线程不安全。将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。

树和二叉树

树是一种非线性结构，二叉树为度为2的树形结构，分为左子树和右子树。
二叉树概念以及存储结构--51CTO

• 叶结点（Leaf）：度为0的结点；
• 路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，...，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度；
• 结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1
• 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度；

图

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。在图中的数据元素，我们称之为顶点（Vertex），顶点集合有穷非空。在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。图的详解

树和图都没有接触过，目前还不知道java中的应用。
尝试整理文章，每天进步一丢丢，嘻嘻。