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中的应用。
尝试整理文章,每天进步一丢丢,嘻嘻。
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » java中的数据结构
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » java中的数据结构