计算机基础 使用JAVA实现散列的数据结构

一、散列

散列是为了解决快速插入和快速查找的功能,它是基于数组+链表来实现的

1.散列结构

散列结构

  • 散列的节点:实际存储的节点
  • 散列函数:hash函数,它通过一定的算法将所存储节点的key转化为一个整数,我们可以根据这个计算出来的整数值来确定它应该存储到散列表的什么位置
  • 散列表:用于存放一系列散列节点的表

注:我们通过key计算出其hashCode值,但不同的key可能其hashCode值相同,这就是所谓的h

计算机基础 B树和B+树数据结构以及B树在MySQL索引中的使用说明

一、二叉树到多叉树

1.二叉树的劣势
  • 二叉树每个节点至多只有两个子节点,如果整个数据比较大,那么我们的树的深度(高度)将非常大,无论对于插入或者删除,速度将会变得比较缓慢
2.多叉树(多路搜索树)

注:多叉树并不是专业的叫法,这里只是为了更好的理解

多路搜索树结构

M阶多路搜索树

  • 每个节点至多M个子节点

二、B树和B+树

1.B树即B-tree

注:这里的B是Balance

(1)B树的性质

B树又叫多路平衡查找树,其

计算机基础 java数据结构之基于红黑树的TreeMap的使用及实现解读

一、红黑树说明

1.红黑树的结构

红黑树是一种特殊的二叉树,它有以下性质:

  • 每一个节点或着成红色,或着成红色
  • 根是黑色的
  • 如果一个节点是红色的,那么它的子节点必须是黑色的(如果这个节点是叶子节点,即没有子节点,不需要满足这个条件,这是在有子节点的情况下)
  • 从根节点到叶子节点的每一条路径必须包含相同数目的黑色节点

红黑树的结构

2.将普通二叉树变成红黑树
  • 将节点着色或改变颜色
  • 将节点进行旋转操作

二、TreeMap的使用

计算机基础 树形结构说明及使用java实现二叉树

一、树形结构的必要性

1.数组列表和链表优势与劣势的比较
数据结构名称 优势 劣势
数组(包括数组列表) 访问数据快 插入节点或删除节点慢(移动节点代价大)
链表 插入节点或删除节点快(修改指针即可) 访问数据慢(需要遍历)
2.树的优势
  • 插入或删除节点快
  • 访问元素快

它只是将插入或删除节点和访问节点的性能要求做了一个平衡

二、树形结构概述

1.树形结构

树形结构

根据日常生活中的树,我们可

计算机基础 Java数据结构之队列Queue的使用及实现原理解读

一、Java集合中实现队列Queue的两种形式

  • ArrayDeque:基于数组实现的队列
  • LinkedList:基于链表实现的队列

二、ArrayDeque的使用及实现

  • ArrayDeque是一个双端队列,即它可以在两端插入或删除,也普通的队列有所区别
1.ArrayDeque与其他集合接口的关系

ArraDequeue与其他结构的关系

2.ArrayQueue的使用及实现解读
(1)属性
  • elements : 存放元素的对象数组
  • head

计算机基础 使用JAVA实现队列的数据结构

队列,是一种特殊的链表,是一种只能在表尾进行插入,表头进行删除的特殊链表,是一种先进先出的结构。

一、队列的结构

队列本质是一种链表,因此栈存储结构与链表一致,形象图如下:

整个栈像我们日常生活中的排队,每个排队的人物就是一个队列元素,新来的人只能排在队尾,从开始依次出队

1.给队列添加元素

给队列添加元素

  • 就像在食堂打饭,后来的人就得在队列后面排着,前面的人先到打饭窗口打饭
2.从队列里面删除元素

从队列中删除元素

  • 在食堂打饭

计算机基础 Java数据结构之栈Stack的使用和实现原理解读

一、java中栈与其他集合的关系

1.Stack与其他相关数据结构接口的关系

栈与其他相关数据结构接口的关系

2.Stack与Vector
  • Vector是Stack的父类,它实现了Stack实现与之相关接口的所有方法
3.Vector与ArrayList
  • 相同点:
    • 它们都实现了List接口和Collection接口等 
    • 它们的底层都使用数组来存储节点
  • 不同点
    • (1)线程安全:ArrayList是不是线程安全的,而Vector是线程安

计算机基础 使用JAVA实现栈的数据结构

栈,是一种特殊的链表,是一种只能在表尾进行操作的特殊链表,是一种后进先出的结构。

一、栈的结构

栈本质是一种链表,因此栈存储结构与链表一致,形象图如下:

整个栈像我们日常使用的行礼箱,它是一层一层的放置东西,每件物品相当于一个栈元素,我们如果想放东西,只能从下面往上面放,最后放的东西永远在最上面,如果拿东西,也是从第上面开始拿

1.给栈添加元素

给栈添加元素

  • 就像往箱子里面放东西,后放的东西总是在最上面
2.从

计算机基础 java数据结构之链表LinkedList的使用与实现原理解读

一、LinkedList的优缺点 

  • 优点:
    • 插入和删除操作较快,只需要修改对应的指针即可
  • 缺点:
    • 通过索引查找元素较慢

二、LinkedList与其他数据结构的关系

1.LinkedList与集合等结构的关系

LinkedList与其他集合的关系

2.LinkedList实现的方法

LinkedList实现的接口方法

三、LinkedList的使用及实现原理解读

1.LinkedList的属性
  • size : 元素个数
  • first : 链首,链表的第一个节点(Node)
  • las

计算机基础 java数据结构之数组列表ArrayList的使用及实现原理解读

一、ArrayList的作用及优缺点

ArrayList是通过数组作为存储为实现的列表,它是一种顺序存储结构

  • 优点
    • 通过位置(索引)查找数据较快
  • 缺点
    • 插入数据需要移动插入位置后面所有的元素
    • 删除数据需要移动删除位置后面所有的元素

二、ArrayList类与其他数据结构之间的关系

1.ArrayList与其他集合类型的关系

ArrayList与其他数据结构之间的关系

2.ArrayList与具体的集合类型的关联

ArrayList与其他接口之间的关系

  • JAVA数据结构大致可分为两