数据结构

1.数组

数组(Array)大概是最简单，也是最常用的数据结构了。其他数据结构，比如栈和队列都是由数组衍生 出来的。 下图展示了 1 个数组，它有 4 个元素：

image-20210504160237833

每一个数组元素的位置由数字编号，称为下标或者索引(index)。大多数编程语言的数组第一个元素的下 标是 0。根据维度区分，有 2 种不同的数组： 一维数组(如上图所示)多维数组(数组的元素为数组)数组的基本操作Insert - 在某个索引处插入元素Get - 读取某个索引处的元素Delete - 删除某个索引处的元素Size - 获取数组的长度

2.栈

撤回，即 Ctrl+Z，是我们最常见的操作之一，大多数应用都会支持这个功能。你知道它是怎么实现的吗？答案是这样的：把之前的应用状态(限制个数)保存到内存中，最近的状态放到第一个。这时，我们 需要栈(stack)来实现这个功能栈中的元素采用 LIFO (Last In First Out)，即后进先出。 下图的栈有 3 个元素，3 在最上面，因此它会被第一个移除：

image-20210504160255985

栈的基本操作 Push — 在栈的最上方插入元素 Pop — 返回栈最上方的元素，并将其删除 isEmpty — 查询栈是否为空 Top— 返回栈最上方的元素，并不删除

3.队列

队列(Queue)与栈类似，都是采用线性结构存储数据。它们的区别在于，栈采用 LIFO 方式，而队列采用先进先出，即FIFO(First in First Out)。 下图展示了一个队列，1 是最上面的元素，它会被第一个移除：

image-20210504160310624

队列的基本操作

Enqueue — 在队列末尾插入元素Dequeue — 将队列第一个元素删除isEmpty — 查询队列是否为空Top— 返回队列的第一个元素

队列的种类

img单队列（单队列就是常⻅的队列, 每次添加元素时，都是添加到队尾，存在“假溢出”的问题也就是明明有位置却不能添加的情况）

img循环队列（避免了“假溢出”的问题）

Java 集合框架中的队列 Queue

Java 集合中的 Queue 继承⾃ Collection 接⼝ ，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。 Queue ⽤来存放 等待处理元素 的集合，这种场景⼀般⽤于缓冲、并发访问。 除了继承 Collection 接⼝的⼀些⽅法，Queue 还添加了额外的 添加、删除、查询操作。

4.链表

链表(Linked List)也是线性结构，它与数组看起来非常像，但是它们的内存分配方式、内部结构和插入删除操作方式都不一样。 链表是一系列节点组成的链，每一个节点保存了数据以及指向下一个节点的指针。链表头指针指向第一 个节点，如果链表为空，则头指针为空或者为 null。 链表可以用来实现文件系统、哈希表和邻接表。下图展示了一个链表，它有 3 个节点：

image-20210504160323832

链表分为 2 种： 单向链表双向链表 链表的基本操作 InsertAtEnd — 在链表结尾插入元素InsertAtHead — 在链表开头插入元素Delete — 删除链表的指定元素DeleteAtHead — 删除链表第一个元素Search — 在链表中查询指定元素isEmpty — 查询链表是否为空

List的常⻅实现类

ArrayList 是⼀个数组队列，相当于动态数组。它由数组实现，随机访问效率⾼，随机插⼊、随机删除效率低。

LinkedList 是⼀个双向链表。它也可以被当作堆栈、队列或双端队列进⾏操作。LinkedList随机访问效率低，但随机插⼊、随机删除效率⾼。

Vector 是⽮量队列，和ArrayList⼀样，它也是⼀个动态数组，由数组实现。但是ArrayList是⾮线程安全的，⽽Vector是线程安全的。

Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。相关阅读：java

5.图

图(graph)由多个节点(vertex)构成，节点之间阔以互相连接组成一个网络。(x, y)表示一条边(edge)， 它表示节点 x 与 y 相连。边可能会有权值(weight/cost)。

image-20210504160332284

图分为两种:

  • 无向图
  • 有向图

在编程语言中，图有可能有以下两种形式表示：

  • 邻接矩阵(Adjacency Matrix)
  • 邻接表(Adjacency List)

遍历图有两周算法

  • 广度优先搜索(Breadth First Search)
  • 深度优先搜索(Depth First Search)

6.树

树(Tree)是一个分层的数据结构，由节点和连接节点的边组成。树是一种特殊的图，它与图最大的区别 是没有循环。 树被广泛应用在人工智能和一些复杂算法中，用来提供高效的存储结构。下图是一个简单的树以及与树相关的术语：

image-20210504160343320

树有很多分类：

  • N 叉树(N-ary Tree)
  • 平衡树(Balanced Tree)
  • 二叉树(Binary Tree)
  • 二叉查找树(Binary Search Tree)
  • 平衡二叉树(AVL Tree)
  • 红黑树(Red Black Tree)
  • 2-3 树(2–3 Tree)

其中，二叉树和二叉查找树是最常用的树。

⼆叉树

⼆叉树（百度百科）

(1) 完全⼆叉树——若设⼆叉树的⾼度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最⼤个数，第h层有叶⼦结点，并且叶⼦结点都是从左到右依次排布，这就是完全⼆叉树。

(2) 满⼆叉树——除了叶结点外每⼀个结点都有左右⼦叶且叶⼦结点都处在最底层的⼆叉树。

(3) 平衡⼆叉树——平衡⼆叉树⼜被称为AVL树（区别于AVL算法），它是⼀棵⼆叉排序树，且具有以下性 质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆ 叉树。

完全⼆叉树

完全⼆叉树（百度百科）

完全⼆叉树：叶节点只能出现在最下层和次下层，并且最下⾯⼀层的结点都集中在该层最左边的若⼲位 置的⼆叉树。

满⼆叉树

满⼆叉树（百度百科，国内外的定义不同）

国内教程定义：⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就 是说，如果⼀个⼆叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满⼆叉树。

堆

数据结构之堆的定义

堆是具有以下性质的完全⼆叉树：每个结点的值都⼤于或等于其左右孩⼦结点的值，称为⼤顶堆；或者 每个结点的值都⼩于或等于其左右孩⼦结点的值，称为⼩顶堆。

⼆叉查找树（BST）

浅谈算法和数据结构: 七 ⼆叉查找树

⼆叉查找树的特点：

  1. 若任意节点的左⼦树不空，则左⼦树上所有结点的 值均⼩于它的根结点的值；

  2. 若任意节点的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；

  3. 任意节点的左、右⼦树也分别为⼆叉查找树；

  4. 没有键值相等的节点（no duplicate nodes）。

平衡⼆叉树（Self-balancing binary search tree）

平衡⼆叉树（百度百科，平衡⼆叉树的常⽤实现⽅法有红⿊树、AVL、替罪⽺树、Treap、伸展树等）

红⿊树

红⿊树特点:

  1. 每个节点⾮红即⿊；

  2. 根节点总是⿊⾊的；

  3. 每个叶⼦节点都是⿊⾊的空节点（NIL节点）；

  4. 如果节点是红⾊的，则它的⼦节点必须是⿊⾊的（反之不⼀定）；

  5. 从根节点到叶节点或空⼦节点的每条路径，必须包含相同数⽬的⿊⾊节点（即相同的⿊⾊⾼ 度）。

红⿊树的应⽤：

TreeMap、TreeSet以及JDK1.8的HashMap底层都⽤到了红⿊树。

为什么要⽤红⿊树？

简单来说红⿊树就是为了解决⼆叉查找树的缺陷，因为⼆叉查找树在某些情况下会退化成⼀个线性结 构

B-，B+，B树

⼆叉树学习笔记之B树、B+树、B树

《B-树，B+树，B树详解》

《B-树，B+树与B树的优缺点⽐较》

B-树（或B树）是⼀种平衡的多路查找（⼜称排序）树，在⽂件系统中有所应⽤。主要⽤作⽂件的索 引。其中的B就表示平衡(Balance)

  1. B+ 树的叶⼦节点链表结构相⽐于 B- 树便于扫库，和范围检索。

  2. B+树⽀持range-query（区间查询）⾮常⽅便，⽽B树不⽀持。这是数据库选⽤B+树的最主要原因。

  3. B树 是B+树的变体，B树分配新结点的概率⽐B+树要低，空间使⽤率更⾼；

LSM 树

[HBase] LSM树 VS B+树

B+树最⼤的性能问题是会产⽣⼤量的随机IO

为了克服B+树的弱点，HBase引⼊了LSM树的概念，即Log-Structured Merge-Trees。LSM树由来、设计思想以及应⽤到HBase的索引

7.前缀树

前缀树(Prefix Trees 或者 Trie)与树类似，用于处理字符串相关的问题时非常高效。它可以实现快速检索，常用于字典中的单词查询，搜索引擎的自动补全甚至 IP 路由。 下图展示了“top”, “thus”和“their”三个单词在前缀树中如何存储的：

image-20210504160353718

单词是按照字母从上往下存储，“p”, “s”和“r”节点分别表示“top”, “thus”和“their”的单词结尾。

8.哈希表

哈希(Hash)将某个对象变换为唯一标识符，该标识符通常用一个短的随机字母和数字组成的字符串来代 表。哈希可以用来实现各种数据结构，其中最常用的就是哈希表(hash table)。

哈希表通常由数组实现。哈希表的性能取决于 3 个指标： 哈希函数 、哈希表的大小 、 哈希冲突处理方式 下图展示了有数组实现的哈希表，数组的下标即为哈希值，由哈希函数计算，作为哈希表的键(key)， 而数组中保存的数据即为值(value)：

image-20210504160417315

9.set

什么是 Set

Set 继承于 Collection 接⼝，是⼀个不允许出现重复元素，并且⽆序的集合，主要 HashSet 和

TreeSet 两⼤实现类。

在判断重复元素的时候，HashSet 集合会调⽤ hashCode()和 equal()⽅法来实现；TreeSet 集合会调

⽤compareTo⽅法来实现。

补充：有序集合与⽆序集合说明
  • 有序集合：集合⾥的元素可以根据 key 或 index 访问 (List、Map)
  • ⽆序集合：集合⾥的元素只能遍历。（Set)
HashSet 和 TreeSet 底层数据结构

HashSet 是哈希表结构，主要利⽤ HashMap 的 key 来存储元素，计算插⼊元素的 hashCode 来获取元素在集合中的位置；

TreeSet 是红⿊树结构，每⼀个元素都是树中的⼀个节点，插⼊的元素都会进⾏排序；

results matching ""

    No results matching ""