Java教程

Java中常见的八种数据结构

本文主要是介绍Java中常见的八种数据结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Java中常见数据结构

一、 8种数据结构

Java中有8种常见数据结构

  • 哈希表(Hash)
  • 队列(Queue)
  • 树(Tree)
  • 堆(Heap)
  • 数组(Array)
  • 栈(Stock)
  • 链表(Linked List)
  • 图(Graph)

哈希表(Hash)

哈希表也叫散列表,是一种可以通过关键码值(Key-Value)直接访问的数据结构,可以实现快速查询、插入、删除。

数组类型的数据结构在 插入和删除 时时间复杂度高;链表类型的数据结构在 查询 时时间复杂度高;而哈希表结合了数组与链表的优势。

在jdk8中,Java中经典的HashMap,以 数组+链表+红黑树 构成。

哈希函数在哈希表中起着关键作用,能够将任意长度的输入转为定长的输出(哈希值)。通过哈希函数,能够快速地对数据元素进行定位。

哈希值并不是具有唯一性,在某些情况下Hash值会冲突,HashMap在Hash冲突时,会将元素在数组的位置上添加为链表元素结点,当链表长度大于8时,链表会转换为 红黑树 。

队列(Queue)

类比水管,两端放开,一端入水,一端出水。

队列是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作。

树(Tree)

树是一种非线性结构,由n(n>0)个有限结点组成有层次关系的集合。

术语:

  • 二叉树:每个结点最多含有2个子树。

  • 完全二叉树:除了最外层的结点,其他各层结点都达到最大数。

  • 满二叉树:

    • 国内定义:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。
    • 国外定义:如果一棵二叉树的结点要么是叶子结点,要么它有两个子结点,这样的树就是满二叉树。
  • 二叉查找树:

    • 任意结点的左子树不为空,左子树所有结点的值均小于根结点的值。
    • 任意结点的右子树不为空,右子树所有结点的值均大于根节点的值。
    • 任意结点的左右子树也是一颗二叉查找树。
  • 平衡二叉树:也称AVL树,当且仅当任何结点的两棵子树的高度差不大于1的二叉树。Java中HashMap的红黑树就是平衡二叉树!!!

  • B树:一种对读写优化的自平衡二叉树,在数据库的索引中常见的BTREE就是自平衡二叉树。

  • B+树:B+树是应文件系统所需而产生的B树的变形树。

    • 所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字
    • 所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。
    • 有m个子树的中间节点包含有m个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引。

Java8中HashMap的红黑树

实质上就是 平衡二叉树 ,通过颜色约束二叉树的平衡:

1)每个节点都只能是红色或者黑色

2)根节点是黑色

3)每个叶节点(NIL 节点,空节点)是黑色的。

4)如果一个节点是红色的,则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。

5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

堆(Heap)

堆可以被看成一个树的数组对象,具有如下特点:

  • 堆是一颗完全二叉树。
  • 最大堆/大根堆:某个结点的值不大于父结点的值。
  • 最小堆/小根堆:某个结点的值不小于父结点的值。

数组(Array)

数组是一种 线性表 的数据结构, 连续的空间 存储 相同类型 的数据。

优点:查询速度快。

缺点:数组在创建时大小确定,无法扩容。数组只能存储一种类型的数据。添加、删除元素慢。

栈(Stock)

栈可以类比为水桶,只有一端能够进出,遵循的先进后出的规则。

栈先进的元素进入栈底,读元素的时候从栈顶取元素。

链表(Linked List)

链表是一种线性表的链式存储方式,链表的内存是不连续的,前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的元素串起来。

  • 单向链表:单向链表是最简单的链表形式。我们将链表中最基本的数据称为节点(node),每一个节点包含了数据块和指向下一个节点的指针。
  • 双向链表:顾名思义,双向链表就是有两个方向的链表。同单向链表不同,在双向链表中每一个节点不仅存储指向下一个节点的指针,而且存储指向前一个节点的指针。通过这种方式,能够通过在O(1)时间内通过目的节点直接找到前驱节点,但是同时会增加大量的指针存储空间。
  • 循环链表:循环链表与双向链表相似,不同的地方在于:在链表的尾部增加一个指向头结点的指针,头结点也增加一个指向尾节点的指针,以及第一个节点指向头节点的指针,从而更方便索引链表元素。

图(Graph)

一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。

节点之间的关系是任意的,图中任意两个数据元素之间都有可能相关。

 

这篇关于Java中常见的八种数据结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!