网络消费网 >  dc > > 正文
java常用数据结构有哪些?Java常见的8种数据结构是什么?
时间:2022-09-30 14:43:28

java数据结构有:1、数组;2、链表,一种递归的数据结构;3、栈,按照“后进先出”、“先进后出”的原则来存储数据;4、队列;5、树,是由 n(n>0)个有限节点组成的一个具有层次关系的集合;6、堆;7、图;8、哈希表。

①、数组

优点:

按照索引查询速度很快;

按照索引遍历数组也很方便。

缺点:

数组的大小在创建后就确定了,无法扩容;

数组只能存储一种类型的数据;

添加、删除元素的操作很耗时间,因为要移动其他元素。

②、链表

由于不必按照顺序的方式存储,链表在插入、删除的时候可以达到 O(1) 的时间复杂度(只需要重新指向引用即可,不需要像数组那样移动其他元素)。除此之外,链表还克服了数组必须预先知道数据大小的缺点,从而可以实现灵活的内存动态管理。

优点:

不需要初始化容量;

插入和删除快,砍断连接,更新引用;

查询慢,需要遍历整个链表。

缺点:

含有大量的引用,占用的内存空间大;

查找元素需要遍历整个链表,耗时。

③、栈

栈就好像水桶一样,底部是密封的,顶部是开口,水可以进可以出。用过水桶的小伙伴应该明白这样一个道理:先进去的水在桶的底部,后进去的水在桶的顶部;后进去的水先被倒出来,先进去的水后被倒出来。

同理,栈按照“后进先出”、“先进后出”的原则来存储数据,先插入的数据被压入栈底,后插入的数据在栈顶,读出数据的时候,从栈顶开始依次读出。

④、队列

队列就好像一段水管一样,两端都是开口的,水从一端进去,然后从另外一端出来。先进去的水先出来,后进去的水后出来。

和水管有些不同的是,队列会对两端进行定义,一端叫队头,另外一端就叫队尾。队头只允许删除操作(出队),队尾只允许插入操作(入队)。

⑤、树

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

之所以叫“树”,是因为这种数据结构看起来就像是一个倒挂的树,只不过根在上,叶在下。树形数据结构有以下这些特点:

每个节点都只有有限个子节点或无子节点;

没有父节点的节点称为根节点;

每一个非根节点有且只有一个父节点;

除了根节点外,每个子节点可以分为多个不相交的子树。

树的分类:二叉查找树,平衡二叉树(AVL树),B-Tree,B+Tree,红黑树

二叉查找树:Binnary Search Tree(BST)

特点:小的往左,大的往后

极端情况,往一边走,导致树太高,退化成链表

基于二叉查找树的特点,它相比较于其他数据结构的优势就在于查找、插入的时间复杂度较低,为 O(logn)。假如我们要从上图中查找 5 元素,先从根节点 2开始找,5 必定在 2的右侧,找到 4,那 5 必定在 4 的右侧,找到了。

理想情况下,通过 BST 查找节点,所需要检查的节点数可以减半。

平衡二叉树(AVL):通过旋转达到左右平衡,本质上也是一颗二叉查找树,不过为了限制左右子树的高度差,避免出现倾斜树等偏向于线性结构演化的情况,所以对二叉搜索树中每个节点的左右子树作了限制,左右子树的高度差称之为平衡因子

平衡二叉树的难点在于,当删除或者增加节点的情况下,如何通过左旋或者右旋的方式来保持左右平衡,树太高,导致IO次数过多

Java 中最常见的平衡二叉树就是红黑树,节点是红色或者黑色,通过颜色的约束来维持着二叉树的平衡:

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

2)根节点是黑色

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

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

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

B-Tree: 通过分裂和合并,达到一个节点

存在问题:每个节点都存储key和data,所有节点组成这棵树

没有双向指针

范围查找,扫描全表,查询慢

B+Tree:

特点:数据都存储在叶子节点上面,

叶子之间有双向指针,

非叶子节点存储键值(指针的键;索引的值)信息

备注:B-Tree用来做二级索引,B+Tree用来做聚集索引

⑥、堆

堆可以被看做是一棵树的数组对象,具有以下特点:

堆中某个节点的值总是不大于或不小于其父节点的值;

堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)均有唯一的“前驱”和“后继”;

在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(子节点)相关;

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

⑧、哈希表

哈希表(Hash Table),也叫散列表,是一种可以通过关键码值(key-value)直接访问的数据结构,它最大的特点就是可以快速实现查找、插入和删除。

数组的最大特点就是查找容易,插入和删除困难;而链表正好相反,查找困难,而插入和删除容易。哈希表很完美地结合了两者的优点, Java 的 HashMap 在此基础上还加入了树的优点。

哈希函数在哈希表中起着⾮常关键的作⽤,它可以把任意长度的输入变换成固定长度的输出,该输出就是哈希值。哈希函数使得一个数据序列的访问过程变得更加迅速有效,通过哈希函数,数据元素能够被很快的进行定位。

若关键字为 k,则其值存放在hash(k)的存储位置上。由此,不需要遍历就可以直接取得 k 对应的值。

对于任意两个不同的数据块,其哈希值相同的可能性极小,也就是说,对于一个给定的数据块,找到和它哈希值相同的数据块极为困难。再者,对于一个数据块,哪怕只改动它的一个比特位,其哈希值的改动也会非常的大——这正是 Hash 存在的价值!

尽管可能性极小,但仍然会发生,如果哈希冲突了,Java 的 HashMap 会在数组的同一个位置上增加链表,如果链表的长度大于 8,将会转化成红黑树进行处理——这就是所谓的拉链法(数组+链表)。

关键词: java常用数据结构有哪些 Java常见的8种数据结构是什么 java中常用的数据结构 java的四种结构

版权声明:
    凡注明来网络消费网的作品,版权均属网络消费网所有,未经授权不得转载、摘编或利用其它方式使用上述作品。已经本网授权使用作品的,应在授权范围内使用,并注明"来源:网络消费网"。违反上述声明者,本网将追究其相关法律责任。
    除来源署名为网络消费网稿件外,其他所转载内容之原创性、真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考并自行核实。
热文

网站首页 |网站简介 | 关于我们 | 广告业务 | 投稿信箱
 

Copyright © 2000-2020 www.sosol.com.cn All Rights Reserved.
 

中国网络消费网 版权所有 未经书面授权 不得复制或建立镜像
 

联系邮箱:920 891 263@qq.com

备案号:京ICP备2022016840号-15

营业执照公示信息