文章 答疑

如何理解并掌握 Java 数据结构

曾经先后在驴妈妈,携程,要买车公司担任过Java高级工程师、架构师、开发主管、技术经理等职务。在电商公司工作期间,负责过PC站和后端服务的平台架构、实现和升级。 目前在做一些Java架构工作。前后从业10几年没有离开Java,2015年出版《Java并发编程从入门到精通》。2018年出版《Spring Data Jpa从入门到精通》。 网名:张振华.Jack
文章 答疑

Jack和大家一起来重温《Java数据结构》经典之作。

第一部分:Java数据结构

要理解Java数据结构,必须能清楚何为数据结构?

数据结构:

  1. Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。
  2. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。
  3. 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构。

一、Java数据结构之:线性数据结构

线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。

1:一维数组

在Java里面常用的util有:String [],int [],ArrayList,Vector,CopyOnWriteArrayList等。及可以同过一维数组[]自己实现不同逻辑结构的Util类。而ArrayList封装了一些[]的基本操作方法。ArrayList和Vector的区别是:Vector是线程安全的,方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。(PS:如果不懂出门右拐看另一篇chat)。

数组这种数据结构典型的操作方法,是根据下标进行操作的,所以insert的的时候可以根据下标插入到具体的某个位置,但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新,删除效率也比较低,而查询效率非常高,查询效率时间复杂度是1。

2: 线性表

线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的,链表的每一个节点都知道上一个节点、或者下一个节点是谁,通常用Node表示。常见的有顺序链表(LinkedList、Linked***),单项链表(里面只有Node类),双向链表(两个Node类),循环链表(多个Node类)等。

操作方法:插入效率比较高,插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了,如果实现的不好,需要整个链路找下去才能找到应该找的元素。所以常见的方法有:add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

常见的Uitil有:LinkedList,LinkedMap等,而这两个JDK底层也做了N多优化,可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。

3: 栈Stack

栈,最主要的是要实现先进后出,后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈,pop()出栈。

java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构,就是线程栈,来保证当前线程的执行顺序。

4:队列

队列,队列是一种特殊的线性数据结构,队列只能允许在队头,队尾进行添加和查询等相关操作。队列又有单项有序队列,双向队列,阻塞队列等。

Queue这种数据结构注定了基本操作方法有:add(E e)加入队列,remove(),poll()等方法。

队列在Java语言环境中是使用频率相当高的数据结构,所有其实现的类也很多来满足不同场景。

queue

使用场景也非常多,如线程池,mq,连接池等。

5:串

串:也称字符串,是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat[]来进行储存。

KMP算法: 这个算法一定要牢记,Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是:在字符串比对的时候,主串的比较位置不需要回退的问题。

二、Java数据结构之:非线性数据结构

非线性数据结构:常见的有:多维数组,集合,树,图,散列表(hash).

1:多维数组

一维数组前面咱也提到了,多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类,而java里面tree和图底层的native方法用了多维数组来储存。

2:集合

由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

Collection

3:树

树形结构,作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成,可以有多个子节点。树,显然是由递归算法组成。

树的特点:

  1. 在一个树结构中,有且仅有一个结点没有直接父节点,它就是根节点。
  2. 除了根节点,其他结点有且只有一个直接父节点
  3. 每个结点可以有任意多个直接子节点。

树的数据结构又分如下几种:

  • 1) 自由树/普通树:对子节点没有任何约束。

    自由树

  • 2) 二叉树:每个节点最多含有两个子节点的树称为二叉树。

    2.1) 一般二叉树:每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。

    2.2) 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;

    2.3) 满二叉树:所有的节点都是二叉的二叉树成为满二叉树。

    二叉树

  • 3) 二叉搜索树/BST:binary search tree,又称二叉排序树、二叉查找树。是有序的。要点:如果不为空,那么其左子树节点的值都小于根节点的值;右子树节点的值都大于根节点的值。

    二叉搜索树

    3.1) 二叉平衡树:二叉搜索树,是有序的排序树,但左右两边包括子节点不一定平衡,而二叉平衡树是排序树的一种,并且加点条件,就是任意一个节点的两个叉的深度差不多(比如差值的绝对值小于某个常数,或者一个不能比另一个深出去一倍之类的)。这样的树可以保证二分搜索任意元素都是O(log n)的,一般还附带带有插入或者删除某个元素也是O(log n)的的性质。

    为了实现,二叉平衡树又延伸出来了一些算法,业界常见的有AVL、和红黑算法,所以又有以下两种树:

    3.1.1) AVL树:最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

    3.1.2) 红黑树:通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。

    红黑树的5条性质:

    1. 每个结点要么是红的,要么是黑的。
    2. 根结点是黑的。
    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
    4. 如果一个结点是红的,那么它的俩个儿子都是黑的。
    5. 对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

    红黑树

  • 4) B-tree:又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子(m>=2)。它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。

    B-tree

  • 4) B+tree:又称B+。是B-树的变体,也是一种多路搜索树。

    B+tree

树总结:
树在Java里面应用的也比较多。非排序树,主要用来做数据储存和展示。而排序树,主要用来做算法和运算,HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。

4:Hash

Hash概念:

  • Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),变换成固定长度的输出,该输出就是散列值。一般通过Hash算法实现。

  • 所谓的Hash算法都是散列算法,把任意长度的输入,变换成固定长度的输出,该输出就是散列值.(如:MD5,SHA1,加解密算法等)

  • 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Java中的hashCode:

  • 我们都知道所有的class都是Object的子类,既所有的class都会有默认Object.java里面的hashCode的方法,如果自己没有重写,默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。

  • 最大的特性是:不同的对象,不同的值有可能计算出来的hashCode可能是一样的。"

2018年1月10日,周三晚上8点30分,曾经先后在驴妈妈、携程、要买车公司担任过 Java 高级工程师、架构师、开发主管、技术经理等职务,在电商公司工作期间,负责过 PC 站和后端服务的平台架构、实现和升级的张振华带来了主题为《如何理解并掌握 Java 数据结构》的交流。以下是主持人天怡整理的问答实录,记录了作者和读者间问答的精彩时刻。


内容提要:

  • 关于面试的几个问题出题面试候选人,在数据结构和算法这块,请问会出哪些题,着重哪些点?如果要准备面试,虽然短期内刷 leetcode 可以积累一些思路,但过些时间就模糊了,怎么在平时工作中训练,长期内都能掌握?工作中平时比较多的是写基本的 CURD 业务,关于数据结构的算法用的比较少,但是面试中又比较爱面试,怎么找到这个平衡?笔试或面试中图这类数据结构的一般考点是什么?面试的话是更重视算法和数据结构基础,还是相关业务的项目经验或者框架使用经验和框架原理?
  • 关于冒泡排序和选择排序,我曾经搜索过网络上很多文章,发现大部分都是错的,自己做文章筛选的成本很高,还可能被误导。因此能不能请给出更多的参考链接?
  • 能否请结合一个例子讲解一下工作中用数据结构解决的问题?
  • 请问有更详细的讲解 Java 数据结构和算法的资料或者书籍推荐吗?
  • 有关二叉平衡树的意义,可以稍微详细讲一下吗?
  • 工作中哪些地方会用到数据结构?
  • 完全二叉树是否可以理解为 D-1 层最右子树没有右叶子的二叉树?
  • 关于树的知识记得有前序、中序、后序遍历算法。文中没有提及,可以讲一下吗?以及这些遍历在实际生产中如何使用?
  • 请问老师 B+ 树和 B- 树怎么理解?

问:关于面试的几个问题出题面试候选人,在数据结构和算法这块,请问会出哪些题,着重哪些点?如果要准备面试,虽然短期内刷 leetcode 可以积累一些思路,但过些时间就模糊了,怎么在平时工作中训练,长期内都能掌握?工作中平时比较多的是写基本的 CURD 业务,关于数据结构的算法用的比较少,但是面试中又比较爱面试,怎么找到这个平衡?笔试或面试中图这类数据结构的一般考点是什么?面试的话是更重视算法和数据结构基础,还是相关业务的项目经验或者框架使用经验和框架原理?

答:我把问题中的5个问题分成两类。一类是面试题大概有些哪些以及如何准备面试?

  1. 首先我建议准备面试的这些人,把文章通读一遍,如果能背诵,不等面试官发问基本上就可以对你有好印象了。

  2. 详细的只需要熟悉数据结构的基本点一到两个。如 HashMap、快速排序。把这些常见的能描述清楚就非常不错了。

  3. 针对架构师级别的,能要更深入一些,如 redis 里面,数据索引原理等都要能讲到里面的原理,并且要能说出来你说的那些数据结构在什么地方用到了。

第二类是我如何掌握数据结构,怎么学、怎么入手?

  1. 建议大家一开始不要看那么多资料,只要看一本就够了。把一本看透,其实书上有些讲的还是不错的,自己要沉下心。

  2. 当自己用 MySQL,redis,util 工具类的时候,想想这里面的数据结构是什么,这时候你其实就会发现,无处不数据结构,只是深与浅的问题,如最浅的 String 就是用了树结构。

  3. 多看这些思维导图,哪块不深入,有针对性地补就可以了。如下图所示。


问:关于冒泡排序和选择排序,我曾经搜索过网络上很多文章,发现大部分都是错的,自己做文章筛选的成本很高,还可能被误导。因此能不能请给出更多的参考链接呢?

答:其实看看我的文章就能找到答案,给大家推荐两个博客《字符串匹配的 KMP 算法》《八大排序算法总结与 Java 实现》,我觉得基本上就能理解,都讲得非常详细。


问:能否请结合一个例子讲解一下工作中用数据结构解决的问题?

答:我以 MySQL 为例给大家讲一下。大家都知道 MySQL 有两种 DB:一个是 Innodb,一个是 MyISAM。索引机制肯定用了树形结构,"

即可阅读全文

打开微信"扫一扫",将本文章分享到朋友圈

快给朋友分享吧!

收藏 收藏

1236人已收藏