分类
商品
商品
店铺
资讯
分类
商品
商品
店铺
资讯

java中的数据结构

  • 时间:2018-10-12 23:16 作者:neko_nia 来源:neko_nia 阅读:176
  • 扫一扫,手机访问
摘要:前言之前遇到一个问题,具体是说: 当我们用HashMap的时候,是怎么考虑优化其性能的呢?当时就一脸懵逼,原来是由于hashmap的自动扩容影响了性能,后面查资料才知道,可以通过设置hashmap的正当的初始容量或者者加载因子来优化。 工作了一段时间了,连这个都不知道表示很羞愧。而后就去查看了少量关于

前言

之前遇到一个问题,具体是说: 当我们用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中的应用。
尝试整理文章,每天进步一丢丢,嘻嘻。

  • 全部评论(0)
最新发布的资讯信息
【系统环境|】极客时间-数据分析实战45讲【完结】(2021-09-02 16:26)
【系统环境|windows】字节跳动前台面试题解析:盛最多水的容器(2021-03-20 21:27)
【系统环境|windows】DevOps敏捷60问,肯定有你想理解的问题(2021-03-20 21:27)
【系统环境|windows】字节跳动最爱考的前台面试题:JavaScript 基础(2021-03-20 21:27)
【系统环境|windows】JavaScript 的 switch 条件语句(2021-03-20 21:27)
【系统环境|windows】解决 XML 数据应用实践(2021-03-20 21:26)
【系统环境|windows】20个编写现代CSS代码的建议(2021-03-20 21:26)
【系统环境|windows】《vue 3.0探险记》- 运行报错:Error:To install them, you can run: npm install --save core-js/modules/es.arra...(2021-03-20 21:24)
【系统环境|windows】浅谈前台可视化编辑器的实现(2021-03-20 21:24)
【系统环境|windows】产品经理入门迁移学习指南(2021-03-20 21:23)
手机二维码手机访问领取大礼包
返回顶部