【动态图】教你捋清Java常用数据结构及其设计原理 原创 JAVA少女 2019-01-07 16:18:37 ©著作权 文章标签 JAVA 编程 数据结构 设计原理 架构 文章分类 Java 后端开发 ©著作权归作者所有:来自51CTO博客作者JAVA少女的原创作品,请联系作者获取转载授权,否则将追究法律责任 最近在整理数据结构方面的知识, 系统化看了下Java中常用数据结构, 突发奇想用动画来绘制数据流转过程。主要基于jdk8, 可能会有些特性与jdk7之前不相同, 例如LinkedList LinkedHashMap中的双向列表不再是回环的。HashMap中的单链表是尾插, 而不是头插入等等, 后文不再赘叙这些差异, 本文目录结构如下。 LinkedList经典的双链表结构, 适用于乱序插入, 删除. 指定序列操作则性能不如ArrayList, 这也是其数据结构决定的.add(E) / addLast(E)add(index, E)这边有个小的优化, 他会先判断index是靠近队头还是队尾, 来确定从哪个方向遍历链入.1 if (index < (size >> 1)) {2 Node<E> x = first;3 for (int i = 0; i < index; i++)4 x = x.next;5 return x;6 } else {7 Node<E> x = last;8 for (int i = size - 1; i > index; i--)9 x = x.prev;10 return x;11 }靠队尾get(index)也是会先判断index, 不过性能依然不好, 这也是为什么不推荐用for(int i = 0; i < lengh; i++)的方式遍历linkedlist, 而是使用iterator的方式遍历.remove(E)ArrayList底层就是一个数组, 因此按序查找快, 乱序插入, 删除因为涉及到后面元素移位所以性能慢.add(index, E)扩容一般默认容量是10, 扩容后, 会length*1.5.remove(E)循环遍历数组, 判断E是否equals当前元素, 删除性能不如LinkedList.Stack经典的数据结构, 底层也是数组, 继承自Vector, 先进后出FILO, 默认new Stack()容量为10, 超出自动扩容.push(E)pop()后缀表达式Stack的一个典型应用就是计算表达式如 9 + (3 - 1) * 3 + 10 / 2, 计算机将中缀表达式转为后缀表达式, 再对后缀表达式进行计算.中缀转后缀数字直接输出栈为空时,遇到运算符,直接入栈遇到左括号, 将其入栈遇到右括号, 执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。遇到运算符(加减乘除):弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈最终将栈中的元素依次出栈,输出。计算后缀表达遇到数字时,将数字压入堆栈遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算, 并将结果入栈重复上述过程直到表达式最右端运算得出的值即为表达式的结果队列与Stack的区别在于, Stack的删除与添加都在队尾进行, 而Queue删除在队头, 添加在队尾.ArrayBlockingQueue生产消费者中常用的阻塞有界队列, FIFO.put(E)put(E) 队列满了1 final ReentrantLock lock = this.lock;2 lock.lockInterruptibly();3 try {4 while (count == items.length)5 notFull.await();6 enqueue(e);7 } finally {8 lock.unlock();9 }take()当元素被取出后, 并没有对数组后面的元素位移, 而是更新takeIndex来指向下一个元素.takeIndex是一个环形的增长, 当移动到队列尾部时, 会指向0, 再次循环.1 private E dequeue() {2 // assert lock.getHoldCount() == 1;3 // assert items[takeIndex] != null;4 final Object[] items = this.items;5 @SuppressWarnings("unchecked")6 E x = (E) items[takeIndex];7 items[takeIndex] = null;8 if (++takeIndex == items.length)9 takeIndex = 0;10 count--;11 if (itrs != null)12 itrs.elementDequeued();13 notFull.signal();14 return x;15 }HashMap最常用的哈希表, 面试的童鞋必备知识了, 内部通过数组 + 单链表的方式实现. jdk8中引入了红黑树对长度 > 8的链表进行优化, 我们另外篇幅再讲.put(K, V)put(K, V) 相同hash值resize 动态扩容当map中元素超出设定的阈值后, 会进行resize (length * 2)操作, 扩容过程中对元素一通操作, 并放置到新的位置.具体操作如下:在jdk7中对所有元素直接rehash, 并放到新的位置.在jdk8中判断元素原hash值新增的bit位是0还是1, 0则索引不变, 1则索引变成"原索引 + oldTable.length".1 //定义两条链2 //原来的hash值新增的bit为0的链,头部和尾部3 Node<K,V> loHead = null, loTail = null;4 //原来的hash值新增的bit为1的链,头部和尾部5 Node<K,V> hiHead = null, hiTail = null;6 Node<K,V> next;7 //循环遍历出链条链8 do {9 next = e.next;10 if ((e.hash & oldCap) == 0) {11 if (loTail == null)12 loHead = e;13 else14 loTail.next = e;15 loTail = e;16 }17 else {18 if (hiTail == null)19 hiHead = e;20 else21 hiTail.next = e;22 hiTail = e;23 }24 } while ((e = next) != null);25 //扩容前后位置不变的链26 if (loTail != null) {27 loTail.next = null;28 newTab[j] = loHead;29 }30 //扩容后位置加上原数组长度的链31 if (hiTail != null) {32 hiTail.next = null;33 newTab[j + oldCap] = hiHead;34 }LinkedHashMap继承自HashMap, 底层额外维护了一个双向链表来维持数据有序. 可以通过设置accessOrder来实现FIFO(插入有序)或者LRU(访问有序)缓存.put(K, V)get(K)accessOrder为false的时候, 直接返回元素就行了, 不需要调整位置. accessOrder为true的时候, 需要将最近访问的元素, 放置到队尾.removeEldestEntry 删除最老的元素 赞 收藏 评论 分享 举报 上一篇:【动态图】教你捋清Java常用数据结构及其设计原理 下一篇:如何理解java里的Comparator和Comparable 提问和评论都可以,用心的回复会被更多人看到 评论 发布评论 全部评论 () 最热 最新 相关文章 速学数据结构 | 手把手教你会单链表的构建方式 C语言做为我们入门的第一门语言,用来快速上手数据结构是自噩耗不过了。本篇文章用最精华的语言教你快速上手单链表! 链表 数据结构 Redis 底层数据结构 我们知道,可以通过 redisObject 对象的 type 和 encoding 属性。可以决定Redis 主要的底层数据结构:SDS、QuickList、ZipList、HashTable、IntSet、ZskipList redis 数据结构 Redis对象机制 分析git 的数据结构 Git 的数据结构主要包括以下四种对象:Blob对象:每个 Blob 对象代表一个文件的数据,它只包含文件的数据,不包含文件的元数据(如文件名、路径、格式等)。Tree对象:每个 Tree 对象代表一个目录的信息,它包含了此目录下的 Blob 对象和子 Tree 对象(对应于子目录),以及其他元数据,如文件名、路径等。对于有子目录的目录,Git 相当于存储了嵌套的 Tree 对象。Comm git 文件名 数据结构 【动态图】教你捋清Java常用数据结构及其设计原理 最近在整理数据结构方面的知识, 系统化看了下Java中常用数据结构, 突发奇想用动画来绘制数据流转过程。主要基于jdk8, 可能会有些特性与jdk7之前不相同, 例如LinkedList LinkedHashMap中的双向列表不再是回环的。HashMap中的单链表是尾插, 而不是头插入等等, 后文不再赘叙这些差异, 本文目录结构如下。 LinkedList经典的双链表结构, 适用于乱序插 JAVA 数据结构 设计 编程 架构 几张动态图捋清Java常用数据结构及其设计原理 最近在整理数据结构方面的知识, 系统化看了下Java中常用数据结构, 突发奇想用动画来绘制数据流转过程.主要基于jdk8, 可能会有些特性与jdk7之前不相同, 例如LinkedList LinkedHashMap中的双向列表不再是回环的.HashMap中的单链表是尾插, 而不是头插入等等, 后文不再赘叙这些差异, 本文目录结构如下: LinkedList经典的双链表结构, 适用于乱序插入, 删除 Java 动态图展示Java常用数据结构的特点和基本操作 |作者:大道方圆|来源: 运算符 Stack 出栈 数据结构:图及其应用 问题:背景知识:图的存储、遍历及其应用,图的最短路径等。目的 实验内容:1.任务:设计一个城市交通咨询模拟系统,利用该系统实现至少两种最优决策:最短路程到达、最省时到达等线路规划。2.内容:用户驾车出行由于出行目的的不同对道路路线选择的要求也有不同。例如,有的希望在途中的路程尽可能短,有的则可能希望路程中时间最短。为了能满足广 算法 数据结构与算法——常用数据结构及其Java实现 数组数组是相同数据类型的元素按一定顺序排列的集合,是一块连续的内存空间。数组的优点是:get和set操作时间上都是O(1)的;缺点是:add和remove操作时间上都是O(N)的。Java中,Array就是数组,此外,ArrayList使用了数组Array作为其实现基础,它和一般的Array相比,最大的好处是,我们在添加元素时不必考虑越界,元素超出数组容量时,它会自动扩张保证容量。Vector和A 子树 结点 二叉树 【算法入门】动态图展示 6 个常用的数据结构,一目了然! 数据结构的确很枯燥,尤其是初学时候,不知道到底有啥用。不过随着编码年限的增长,我们越会发现它真的很有用,巧妙的数据结构是算法高效实现的助推剂。今天的文章不会用文字和静态图展现常用的数据结构,因为这种普遍的讲解在博客、书籍太多了,根本不需要我在这里啰里啰嗦。今天我们使用动态图,展现最最基本的、常用的数据结构,让我们起航吧!1 线型数组线型数组最好理解,就是逐个插入元素,逐个删除元素,有严格的顺序。2 数据结构 二分查找 动态图 常用数据结构的原理 不同的数据结构适用于不同的应用场景,因此了解各种数据结构的原理对于编写高效的程序至关重要。本文将介 数据结构 原力计划 Java 链表 Redis常用数据结构及其场景归纳 1 mset、mget、msetnx批量处理字符串更新、获取、加锁场景:文章的标题、内容、作者等多个key 批量发布和查看(对于这种可以直接用序列化反 redis 数据结构 场景 List 有序集合 Java 数据结构如何设计 java 数据结构 图 单链表写在前面:说起单链表大家可能都比较熟悉,有些人可能会说java或者其他的语言都将这些数据结构封装好了,你直接调用不就好啦,干嘛还要费劲的学这些东西,我想告诉大家的是,就算是现在的高级语言都将这些数据结构封装好了,我们还是要学习的,因为如果你不了解这些数据结构的基本含义的话,是无法熟练的应用那些已经封装好了的东西,所以我们如果不想仅仅变成一个只会搬砖的码农那就好好学习这些底层的东西,认真了解其 Java 数据结构如何设计 链表 数据结构 java 单链表 java业务数据动态图表 java动态图编程 此方法需要用到多线程进行绘图。 首先创建一个类,让其继承JPanl,并且实现Runnable。 在public void paint(Graphics arg0)函数中,可视化具体的物件。例如:画圆、画线等。 在public void run()函数中实现线程,写出可视化的动态绘图的改变。先提出改变,再用Thread.sleep()来实现隔几秒重画,调用this.repaint()实现重画。 下面 java业务数据动态图表 可视化 动态画图 Java ide 数据结构与算法——常用高级数据结构及其Java实现 前文 数据结构与算法——常用数据结构及其Java实现 总结了基本的数据结构,类似的,本文准备总结一下一些常见的高级的数据结构及其常见算法和对应的Java实现以及应用场景,务求理论与实践一步到位。 跳跃表 跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快 java经验集锦 通用实践 算法 学习提高 JDK 常用数据结构 java 常用数据结构类型 数据元素相互之间的关系称为结构。数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。有四类基本结构:集合、线性结构、树形结构、图状结构。1、集合结构:除了同属于一种类型外,别无其它关系。3、线性结构:元素之间存在一对一关系常见类型有: 数组,链表、队列、栈,它们之间在操作上有所区别。例如:链表可在任意位置插入或删除元素,而队列在队尾插入元素,队头删除元素,栈只 常用数据结构 java 数据结构 数据 数组 常用数据结构java实现 java 常用数据结构 一、基础数据类型:四类八种基本数据类型。1、 整型:byte,short,int,long。2、 浮点型:float,double。3、 逻辑型:true,false。4、 字符型:char 二、集合数据类型1、 数组:有顺序,同样类型的数据,有长度。2、 List:有顺序,不同类型的数据,没有长度。3、 常用数据结构java实现 数据结构与算法 java 数据 List 数据结构 图 java 数据结构 图结构实验 实验项目六 图结构基本操作的实现课程名称:数据结构实验项目名称:图结构基本操作的实现实验目的:1.掌握图的基本操作—遍历。实验要求:1、 分别用DFS和BFS的方法实现一个无向图的遍历。实验过程:1、 创建一个图(可用邻接矩阵或邻接表的方式进行存储);2、 输入 ci 邻接矩阵 #define Java怎么加载动态图 java加载动态库原理 相信很多做Java的朋友都有过用Java调用JNI实现调用C或C++方法的经历,那么Java Web中又如何实现DLL/SO文件的动态加载方法呢。今天就给大家带来一篇JAVA Web项目中DLL/SO文件动态加载方法的文章。在Java Web项目中,我们经常会用到通过JNI调用dll动态库文件来实现一些JAVA不能实现的功能,或者是一些第三方dll插件。通常的做法是将这些dll文件复制到 %JAV Java怎么加载动态图 java web 加载dll JAVA Java Web (4)java数据结构--集合类及其数据结构归纳-有大图 ---------大图可以 在新标签中打开图片 看到大图上面这张图总结了java集合类的继承结构,下面是对集合类的一些总结和特性描述:CollectionCollection是一个接口,是高度抽象出来的集合,它包含了集合的基本操作:添加、删除、清空、遍历、是否为空、获取大小、是否保护某元素等等。Collection接口的所有子类(直接子类和间接子类)都必须实现2种构造函数:不带参数的构造函数和参 数据 抽象类 数组 序列化 java (6)Java数据结构-- 转:JAVA常用数据结构及原理分析 JAVA常用数据结构及原理分析 ://.2cto.com/kf/201506/412305.html 前不久面试官让我说一下怎么理解java数据结构框架,之前也看过部分源码,balabala讲了一堆,现在总结一下。 java.util包中三个重要的接口及特点:List(列表)、Set( 数组 java 实现原理 线性表 原理图