共计 17266 个字符，预计需要花费 44 分钟才能阅读完成。
数据结构是什么？
程序 = 数据结构 + 算法
是的，下面这句话是十分经典的，程序由数据结构以及算法组成，当然数据结构和算法也是相辅相成的，不能齐全独立来对待，然而本文会绝对重点聊聊那些罕用的数据结构。
数据结构是什么呢？
首先得晓得数据是什么？数据是对主观事务的符号示意 ，在计算机科学中是指所有能输出到计算机中并被计算机程序解决的符号总称。那为何加上“构造” 两字？
数据元素是数据的根本单位 ，而任何问题中，数据元素都不是独立存在的，它们之间总是存在着某种关系，这种 数据元素之间的关系咱们称之为构造。
因而，咱们有了以下定义：
数据结构是计算机存储、组织数据的形式。数据结构是指相互之间存在一种或多种特定关系的数据元素的汇合。通常状况下，精心抉择的数据结构能够带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术无关。
简略讲，数据结构就是组织，治理以及存储数据的形式。尽管实践上所有的数据都能够混淆，或者糅合，或者狼吞虎咽，轻易存储，然而计算机是谋求高效的，如果咱们能理解数据结构，找到较为适宜以后问题场景的数据结构，将数据之间的关系体现在存储上，计算的时候能够较为高效的利用适配的算法，那么程序的运行效率必定也会有所提高。
罕用的 4 种数据结构有：
- 汇合：只有同属于一个汇合的关系，没有其余关系
- 线性构造：构造中的数据元素之间存在一个对一个的关系
- 树形构造：构造中的数据元素之间存在一个对多个的关系
- 图状构造或者网状结构：图状构造或者网状结构
何为逻辑构造和存储构造？
数据元素之间的逻辑关系，称之为逻辑构造 ，也就是咱们定义了对操作对象的一种数学形容。然而咱们还必须晓得在计算机中如何示意它。 数据结构在计算机中的示意（又称为映像），称之为数据的物理构造，又称存储构造。
数据元素之前的关系在计算机中有两种不同的示意办法：程序映像和非程序映像 ，并且由此失去两种不同的存储构造： 顺序存储构造 和链式存储构造，比方顺序存储构造，咱们要示意复数z1 =3.0 - 2.3i , 能够间接借助元素在存储器中的绝对地位来示意数据元素之间的逻辑关系：
而链式构造，则是以 指针 示意数据元素之间的逻辑关系，同样是z1 =3.0 - 2.3i ，先找到下一个是 100，是一个地址，依据地址找到实在的数据-2.3i:
位（bit）
在计算机中示意信息的最小的单位是二进制数中的一位，叫做 位。也就是咱们常见的相似 01010101010 这种数据，计算机的底层就是各种晶体管，电路板，所以不论是什么数据，即便是图片，声音，在最底层也是 0 和1, 如果有八条电路，那么每条电路有本人的闭合状态，有 8 个2相乘，2^8^，也就是 256 种不同的信号。
然而个别咱们须要示意正数，也就是最高的一位示意符号位，0示意负数，1示意正数，也就是 8 位的最大值是01111111，也就是127。
值得咱们留神的是，计算机的世界里，多了原码，反码，补码的概念：
- 原码：用第一位示意符号，其余位示意值
- 反码：负数的补码反码是其自身，正数的反码是符号位放弃不变，其余位取反。
- 补码：负数的补码是其自身，正数的补码是在其反码的根底上 + 1
为什么有了原码还要反码和补码？
咱们晓得加减法是高频的运算，人能够很直观的看出加号减号，马上就能够算进去，然而计算机如果辨别不同的符号，那么加减就会比较复杂，比方负数 + 负数，负数 - 负数，负数 - 正数，正数 + 正数 … 等等。于是，有人就想用同一个运算器（加号运算器），解决所有的加减法计算，能够缩小很多简单的电路，以及各种符号转换的开销，计算也更加高效。
咱们能够看到，上面正数加入运算的后果也是合乎补码的规定的：
00100011 35
+ 11011101 -35
-------------------------
00000000 0 00100011 35
+ 11011011 -37
-------------------------
11111110 -2当然，如果计算结果超出了位数所能示意的范畴，那就是溢出，就阐明须要更多的位数能力正确示意。
个别能用位运算的，都尽量应用位运算，因为它比拟高效, 常见的位运算：
~：按位取反&：按为与运算|：按位或运算^：按位异或<<: 带符号左移，比方35(00100011), 左移一位为70(01000110),-35(11011101)左移一位为-70(10111010)>>：带符号右移，比方35(00100011), 右移一位为17(00010001),-35(11011101)左移一位为-18(11101110)<<<: 无符号左移，比方35(00100011), 左移一位为70(01000110)>>>: 无符号右移，比方-35(11011101), 右移一位为110(01101110)x ^= y; y ^= x; x ^= y;: 替换s &= ~(1 << k): 第k地位 0
要说哪里应用位运算比拟经典，那么要数 布隆过滤器，须要理解详情的能够参考：http://aphysia.cn/archives/ca…
布隆过滤器是什么呢？
布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在 1970 年提出的，它实际上是由一个很长的二进制向量和一系列随机 hash 映射函数组成（说白了，就是用二进制数组存储数据的特色）。能够应用它来判断一个元素是否存在于汇合中，它的长处在于查问效率高，空间小，毛病是存在肯定的误差，以及咱们想要剔除元素的时候，可能会相互影响。
也就是当一个元素被退出汇合的时候，通过多个 hash 函数，将元素映射到位数组中的 k 个点，置为1。
重点是多个 hash 函数，能够将数据 hash 到不同的位上，也只有这些位全副为 1 的时候，咱们能力判断该数据曾经存在
假如有三个 hash 函数，那么不同的元素，都会应用三个 hash 函数，hash到三个地位上。
假如前面又来了一个张三，那么在 hash 的时候，同样会 hash 到以下地位，所有位都是1，咱们就能够说张三曾经存在在外面了。
那么有没有可能呈现误判的状况呢？这是有可能的，比方当初只有张三，李四，王五，蔡八，hash映射值如下：
前面来了陈六，然而不凑巧的是，它 hash 的三个函数 hash 进去的位，刚刚好就是被别的元素 hash 之后，改成 1 了，判断它曾经存在了，然而实际上，陈六之前是不存在的。
下面的状况，就是误判，布隆过滤器都会不可避免的呈现误判。然而它有一个益处是，布隆过滤器，判断存在的元素，可能不存在，然而判断不存在的元素，肯定不存在。，因为判断不存在阐明至多有一位 hash 进去是对不上的。
也是因为会呈现多个元素可能 hash 到一起，但有一个数据被踢出了汇合，咱们想把它映射的位，置为0，相当于删除该数据。这个时候，就会影响到其余的元素，可能会把别的元素映射的位，置为了0。这也就是为什么布隆过滤器不能删除的起因。
数组
线性示意最罕用而且最为简略的一种数据结构，一个线性示意 n 个数据元素的无限序列，有以下特点：
- 存在惟一的第一个的数据元素
- 存在惟一被称为最初一个的数据元素
- 除了第一个以外，汇合中每一个元素均有一个前驱
- 除了最初一个元素之外，汇合中的每一个数据元素都有一个后继元素
线性表包含上面几种：
- 数组：查问 / 更新快，查找 / 删除慢
- 链表
- 队列
- 栈
数组是线性表的一种，线性表的程序示意指的是用一组地址间断的存储单元顺次存储线性表的数据元素：
在 Java 中示意为：
int[] nums = new int[100];
int[] nums = {1,2,3,4,5};
Object[] Objects = new Object[100];在C++ 中示意为：
int nums[100];数组是一种线性的构造，个别在底层是间断的空间，存储雷同类型的数据，因为间断紧凑构造以及人造索引反对，查问数据效率高:
假如咱们晓得数组 a 的第 1 个值是 地址是 296, 外面的数据类型占 2 个 单位，那么咱们如果冀望失去第 5 个：296+（5-1）*2 = 304,O(1)的工夫复杂度就能够获取到。
更新的实质也是查找，先查找到该元素，就能够入手更新了：
然而如果冀望插入数据的话，须要挪动前面的数据，比方上面的数组，插入元素6，最差的是挪动所有的元素，工夫复杂度为O(n)
而删除元素则须要把前面的数据挪动到后面，最差的工夫复杂度同样为O(n):
Java 代码实现数组的增删改查：
package datastruction;
import java.util.Arrays;
public class MyArray {private int[] data;
private int elementCount;
private int length;
public MyArray(int max) {
length = max;
data = new int[max];
elementCount = 0;
}
public void add(int value) {if (elementCount == length) {
length = 2 * length;
data = Arrays.copyOf(data, length);
}
data[elementCount] = value;
elementCount++;
}
public int find(int searchKey) {
int i;
for (i = 0; i < elementCount; i++) {if (data[i] == searchKey)
break;
}
if (i == elementCount) {return -1;}
return i;
}
public boolean delete(int value) {int i = find(value);
if (i == -1) {return false;}
for (int j = i; j < elementCount - 1; j++) {data[j] = data[j + 1];
}
elementCount--;
return true;
}
public boolean update(int oldValue, int newValue) {int i = find(oldValue);
if (i == -1) {return false;}
data[i] = newValue;
return true;
}
}
// 测试类
public class Test {public static void main(String[] args) {MyArray myArray = new MyArray(2);
myArray.add(1);
myArray.add(2);
myArray.add(3);
myArray.delete(2);
System.out.println(myArray);
}
}链表
下面的例子中，咱们能够看到数组是须要间断的空间，这外面如果空间大小只有 2，放到第 3 个元素的时候，就不得不扩容，不仅如此，还得拷贝元素。一些删除，插入操作会引起较多的数据挪动的操作。
链表，也就是链式数据结构，因为它不要求逻辑上相邻的数据元素在物理地位上也相邻，所以它没有顺序存储构造所具备的毛病，然而同时也失去了通过索引下标间接查找元素的长处。
重点：链表在计算机的存储中不是间断的，而是前一个节点存储了后一个节点的指针（地址），通过地址找到后一个节点。
上面是单链表的构造：
个别咱们会手动在单链表的后面设置一个前置结点，也能够称为头结点，然而这并非相对：
个别链表构造分为以下几种：
- 单向链表：链表中的每一个结点，都有且只有一个指针指向下一个结点，并且最初一个节点指向空。
- 双向链表 ：每个节点都有两个指针（为不便，咱们称之为 前指针 ， 后指针），别离指向上一个节点和下一个节点，第一个节点的前指针指向
NULL，最初一个节点的后指针指向NULL - 循环链表：每一个节点的指针指向下一个节点，并且最初一个节点的指针指向第一个节点（尽管是循环链表，然而必要的时候还须要标识头结点或者尾节点，防止死循环）
- 简单链表：每一个链表有一个后指针，指向下一个节点，同时有一个随机指针，指向任意一个结点。
链表操作的工夫复杂度：
- 查问：
O(n), 须要遍历链表 - 插入：
O(1)，批改前后指针即可 - 删除：
O(1)，同样是批改前后指针即可 - 批改：不须要查问则为
O(1)，须要查问则为O(n)
链表的构造代码怎么示意呢？
上面只示意单链表构造，C++示意：
// 结点
typedef struct LNode{
// 数据
ElemType data;
// 下一个节点的指针
struct LNode *next;
}*Link,*Position;
// 链表
typedef struct{
// 头结点，尾节点
Link head,tail;
// 长度
int len;
}LinkList;Java 代码示意：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {this.val = val;}
}本人实现简略链表，实现增删改查性能：
class ListNode<T> {
T val;
ListNode next = null;
ListNode(T val) {this.val = val;}
}
public class MyList<T> {
private ListNode<T> head;
private ListNode<T> tail;
private int size;
public MyList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public void add(T element) {add(size, element);
}
public void add(int index, T element) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("超出链表长度范畴");
}
ListNode current = new ListNode(element);
if (index == 0) {if (head == null) {
head = current;
tail = current;
} else {
current.next = head;
head = current;
}
} else if (index == size) {
tail.next = current;
tail = current;
} else {ListNode preNode = get(index - 1);
current.next = preNode.next;
preNode.next = current;
}
size++;
}
public ListNode get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("超出链表长度");
}
ListNode temp = head;
for (int i = 0; i < index; i++) {temp = temp.next;}
return temp;
}
public ListNode delete(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("超出链表节点范畴");
}
ListNode node = null;
if (index == 0) {
node = head;
head = head.next;
} else if (index == size - 1) {ListNode preNode = get(index - 1);
node = tail;
preNode.next = null;
tail = preNode;
} else {ListNode pre = get(index - 1);
pre.next = pre.next.next;
node = pre.next;
}
size--;
return node;
}
public void update(int index, T element) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("超出链表节点范畴");
}
ListNode node = get(index);
node.val = element;
}
public void display() {
ListNode temp = head;
while (temp != null) {System.out.print(temp.val + "->");
temp = temp.next;
}
System.out.println("");
}
}
测试代码如下：
public class Test {public static void main(String[] args) {MyList myList = new MyList();
myList.add(1);
myList.add(2);
// 1->2
myList.display();
// 1
System.out.println(myList.get(0).val);
myList.update(1,3);
// 1->3
myList.display();
myList.add(4);
// 1->3->4
myList.display();
myList.delete(1);
// 1->4
myList.display();}
}输入后果：
1 -> 2 ->
1
1 -> 3 ->
1 -> 3 -> 4 ->
1 -> 4 ->单向链表的查找更新比较简单，咱们看看插入新节点的具体过程（这里只展现两头地位的插入，头尾插入比较简单）：
那如何删除一个两头的节点呢？上面是具体的过程：
或者你会好奇，a5节点只是指针没有了，那它去哪里了？
如果是 Java 程序，垃圾回收器会收集这种没有被援用的节点，帮咱们回收掉了这部分内存，然而为了放慢垃圾回收的速度，个别不须要的节点咱们须要置空，比方 node = null, 如果在C++ 程序中，那么就须要手动回收了，否则容易造成内存透露等问题。
简单链表的操作临时讲到这里，前面我会独自把链表这一块的数据结构以及罕用算法独自分享一下，本文章次要讲数据结构全貌。
跳表
下面咱们能够察看到，链表如果搜寻，是很麻烦的，如果这个节点在最初，须要遍历所有的节点，能力找到，查找效率切实太低，有没有什么好的方法呢？
方法总比问题多，然而想要相对的”多快好省“是不存在的，有舍有得，计算机的世界里，充斥哲学的滋味。既然搜寻效率有问题，那么咱们不如给链表排个序。排序后的链表，还是只能晓得头尾节点，晓得两头的范畴，然而要找到两头的节点，还是得走遍历的老路。如果咱们把两头节点存储起来呢？存起来，的确咱们就晓得数据在前一半，还是在后一半。比方找7，必定就从两头节点开始找。如果查找4, 就得从头开始找，最差到两头节点，就进行查找。
然而如此，还是没有彻底解决问题，因为链表很长的状况，只能通过前后两局部查找。不如回到准则：空间和工夫，咱们抉择工夫，那就要舍弃一部分空间 , 咱们每个节点再加一个指针，当初有 2 层指针（留神： 节点只有一份，都是同一个节点，只是为了难看，弄了两份，实际上是同一个节点，有两个指针，比方 1，既指向 2，也指向 5 ）：
两层指针，问题仍然存在，那就一直加层，比方每两个节点，就加一层：
这就是跳表了，跳表的定义如下：
跳表 (SkipList，全称跳跃表) 是用于有序元素序列疾速搜寻查找的一个数据结构，跳表是一个随机化的数据结构，本质就是一种能够进行二分查找的有序链表。跳表在原有的有序链表下面减少了多级索引，通过索引来实现疾速查找。跳表不仅能进步搜寻性能，同时也能够进步插入和删除操作的性能。它在性能上和红黑树，AVL 树并驾齐驱，然而跳表的原理非常简单，实现也比红黑树简略很多。
次要的原理是用空间换工夫，能够实现近乎二分查找的效率，实际上耗费的空间，假如每两个加一层，1 + 2 + 4 + ... + n = 2n-1, 多出了差不多一倍的空间。你看它像不像书的目录，一级目录，二级，三级 …
如果咱们一直往跳表中插入数据，可能呈现某一段节点会特地多的状况，这个时候就须要动静更新索引，除了插入数据，还要插入到上一层的链表中，保障查问效率。
redis 中应用了跳表来实现 zset,redis 中应用一个随机算法来计算层级，计算出每个节点到底多少层索引，尽管不能相对保障比拟均衡，然而根本保障了效率，实现起来比那些均衡树，红黑树的算法简略一点。
栈
栈是一种数据结构，在 Java 外面体现是 Stack 类。它的实质是 先进后出，就像是一个桶，只能一直的放在下面，取出来的时候，也只能一直的取出最下面的数据。要想取出底层的数据，只有等到下面的数据都取出来，能力做到。当然，如果有这种需要，咱们个别会应用双向队列。
以下是栈的个性演示：
栈的底层用什么实现的？其实能够用链表，也能够用数组，然而 JDK 底层的栈，是用数组实现的，封装之后，通过 API 操作的永远都只能是最初一个元素，栈常常用来实现递归的性能。如果想要理解 Java 外面的栈或者其余汇合实现剖析，能够看看这系列文章：http://aphysia.cn/categories/…
元素退出称之为入栈（压栈），取出元素，称之为出栈，栈顶元素则是最初一次放进去的元素。
应用数组实现简略的栈(留神仅供参考测试，理论会有线程平安等问题)：
import java.util.Arrays;
public class MyStack<T> {private T[] data;
private int length = 2;
private int maxIndex;
public MyStack() {data = (T[]) new Object[length];
maxIndex = -1;
}
public void push(T element) {if (isFull()) {
length = 2 * length;
data = Arrays.copyOf(data, length);
}
data[maxIndex + 1] = element;
maxIndex++;
}
public T pop() {if (isEmpty()) {throw new IndexOutOfBoundsException("栈内没有数据");
} else {T[] newdata = (T[]) new Object[data.length - 1];
for (int i = 0; i < data.length - 1; i++) {newdata[i] = data[i];
}
T element = data[maxIndex];
maxIndex--;
data = newdata;
return element;
}
}
private boolean isFull() {return data.length - 1 == maxIndex;}
public boolean isEmpty() {return maxIndex == -1;}
public void display() {for (int i = 0; i < data.length; i++) {System.out.print(data[i]+" ");
}
System.out.println("");
}
}
测试代码：
public class MyStackTest {public static void main(String[] args) {MyStack<Integer> myStack = new MyStack<>();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.display();
System.out.println(myStack.pop());
myStack.display();}
}输入后果如下，合乎预期：
1 2 3 4
4
1 2 3 栈的特点就是先进先出，然而如果须要随机取出后面的数据，效率会比拟低，须要倒腾进去，然而如果底层应用数组，实践上是能够通过索引下标取出的，Java外面正是这样实现。
队列
既然后面有先进后出的数据结构，那咱们必然也有先进先出的数据结构，疫情的时候，排队预计大家都有测过核酸，那排队老长了，排在后面先测，排在前面后测，这情理大家都懂。
队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的特点是先进先出，以下是例子：
个别只有说到先进先出（FIFO）, 全称First In First Out, 就会想到队列，然而如果你想领有队列即能够从队头取出元素，又能够从队尾取出元素，那就须要用到非凡的队列（双向队列），双向队列个别应用双向链表实现会简略一点。
上面咱们用 Java 实现简略的单向队列：
class Node<T> {
public T data;
public Node next;
public Node(T data) {this.data = data;}
}
public class MyQueue<T> {
private Node<T> head;
private Node<T> rear;
private int size;
public MyQueue() {size = 0;}
public void pushBack(T element) {Node newNode = new Node(element);
if (isEmpty()) {head = newNode;} else {rear.next = newNode;}
rear = newNode;
size++;
}
public boolean isEmpty() {return head == null;}
public T popFront() {if (isEmpty()) {throw new NullPointerException("队列没有数据");
} else {
Node<T> node = head;
head = head.next;
size--;
return node.data;
}
}
public void dispaly() {
Node temp = head;
while (temp != null) {System.out.print(temp.data +"->");
temp = temp.next;
}
System.out.println("");
}
}测试代码如下：
public class MyStackTest {public static void main(String[] args) {MyStack<Integer> myStack = new MyStack<>();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.display();
System.out.println(myStack.pop());
myStack.display();}
}运行后果：
1 -> 2 -> 3 ->
1
2 -> 3 ->
2
3 -> 罕用的队列类型如下：
- 单向队列：也就是咱们说的一般队列，先进先出。
- 双向队列：能够从不同方向进出队列
- 优先队列：外部是主动排序的，依照肯定程序出队列
- 阻塞队列：从队列取出元素的时候，队列没有元素则会阻塞，同样如果队列满了，往队列外面放入元素也会被阻塞。
- 循环队列：能够了解为一个循环链表，然而个别须要标识出头尾节点，避免死循环，尾节点的
next指向头结点。
队列个别能够用来保留须要程序的数据，或者保留工作，在树的档次遍历中能够应用队列解决，个别广度优先搜寻都能够应用队列解决。
哈希表
后面的数据结构，查找的时候，个别都是应用 = 或者 !=, 在折半查找或者其余范畴查问的时候，可能会应用< 和>, 现实的时候，咱们必定心愿不通过任何的比拟，间接能定位到某个地位（存储地位），这种在数组中，能够通过索引获得元素。那么，如果咱们将须要存储的数据和数组的索引对应起来，并且是一对一的关系，那不就能够很快定位到元素的地位了么？
只有通过函数 f(k) 就能找到 k 对应的地位，这个函数 f(k) 就是 hash 函数。它示意的是一种映射关系，然而对不同的值，可能会映射到同一个值（同一个 hash 地址），也就是 f(k1) = f(k2)，这种景象咱们称之为 抵触 或者 碰撞。
hash表定义如下：
散列表（Hash table，也叫哈希表），是依据键（Key）而间接拜访在内存贮存地位的数据结构。也就是说，它通过计算一个对于键值的函数，将所需查问的数据映射到表中一个地位来拜访记录，这放慢了查找速度。这个映射函数称做散列函数，寄存记录的数组称做散列表。
个别罕用的hash 函数有：
- 间接定址法：取出关键字或者关键字的某个线性函数的值为哈希函数，比方
H(key) = key或者H(key) = a * key + b - 数字分析法：对于可能呈现的数值全副理解，取关键字的若干数位组成哈希地址
- 平方取中法：取关键字平方后的两头几位作为哈希地址
- 折叠法：将关键字宰割成为位数雷同的几局部（最初一部分的位数能够不同），取这几局部的叠加和（舍去进位），作为哈希地址。
- 除留余数法：取关键字被某个不大于散列表表长
m的数p除后所得的余数为散列地址。即 hash(k)=k mod p，p< =m。不仅能够对关键字间接取模，也可在折叠法、平方取中法等运算之后取模。对p的抉择很重要，个别取素数或m，若p抉择不好，容易产生抵触。 - 随机数法：取关键字的随机函数值作为它的哈希地址。
然而这些办法，都无奈防止哈希抵触，只能无意识的缩小。那解决 hash 抵触，个别有哪些办法呢？
- 凋谢地址法：
hash计算后，如果该地位曾经有数据，那么对该地址+1，也就是往后找，晓得找到一个空的地位。 - 从新
hash法：产生哈希抵触后，能够应用另外的hash函数从新极计算，找到空的hash地址, 如果有，还能够再叠加hash函数。 - 链地址法：所有
hash值一样的, 链接成为一个链表，挂在数组前面。 - 建设公共溢出区：不常见，意思是所有元素，如果和表中的元素
hash抵触，都弄到另外一个表，也叫溢出表。
Java外面，用的就是链地址法：
然而如果 hash 抵触比较严重，链表会比拟长，查问的时候，须要遍历前面的链表，因而 JDK 优化了一版，链表的长度超过阈值的时候，会变成 红黑树，红黑树有肯定的规定去均衡子树，防止进化成为链表，影响查问效率。
然而你必定会想到，如果数组太小了，放了比拟多数据了，怎么办？再放抵触的概率会越来越高，其实这个时候会触发一个扩容机制，将数组扩容成为 2倍大小，从新 hash 以前的数据，哈希到不同的数组中。
hash表的长处是查找速度快，然而如果一直触发从新 hash, 响应速度也会变慢。同时，如果心愿范畴查问，hash表不是好的抉择。
树
数组和链表都是线性构造，而这里要介绍的树，则是非线性构造。事实中树是金字塔构造，数据结构中的树，最下面称之为根节点。
咱们该如何定义树结构呢？
树 是一种数据结构，它是由 n(n≥1) 个无限节点组成一个具备档次关系的汇合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具备以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点能够分为多个不相交的子树。(百度百科)
上面是树的根本术语（来自于清华大学数据结构 C 语言版）：
- 节点的度：一个节点含有的子树的个数称为该节点的度
- 树的度：一棵树中，最大的节点度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具备雷同父节点的节点互称为兄弟节点；
- 节点的档次：从根开始定义起，根为第
1层，根的子节点为第2层，以此类推； - 深度：对于任意节点
n,n的深度为从根到 n 的惟一门路长，根的深度为0； - 高度：对于任意节点
n,n的高度为从n到一片树叶的最长门路长，所有树叶的高度为0； - 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的先人：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 有序树：将树种的节点的各个子树看成从左至右是有秩序的（不能调换），则应该称该树为有序树，否则为无序树
- 第一个孩子：在有序树中最右边的子树的根称为第一个孩子
- 最初一个孩子：在有序树种最左边的子树的根称为最初一个孩子
- 森林：由
m（m>=0）棵互不相交的树的汇合称为森林；
树，其实咱们最罕用的是二叉树：
二叉树的特点是每个节点最多只有两个子树，并且子树有左右之分，左右子节点的秩序不能任意颠倒。
二叉树在 Java 中示意：
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {this.val = val;}
}满二叉树：一棵深度为 k 且有 2k-1 个节点的二叉树，称之为满二叉树
齐全二叉树：深度为 k 的，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 到 n 的节点一一对应是，称之为齐全二叉树。
个别二叉树的遍历有几种：
- 前序遍历：遍历程序 根节点 –> 左子节点 –> 右子节点
- 中序遍历：遍历程序 左子节点 –> 根节点 –> 右子节点
- 后序遍历：遍历程序 左子节点 –> 右子节点 –> 根节点
- 广度 / 档次遍历：从上往下，一层一层的遍历
如果是一棵凌乱的二叉树，那查找或者搜寻的效率也会比拟低，和一条凌乱的链表没有什么区别，何必弄更加简单的构造呢？
其实，二叉树是能够用在排序或者搜寻中的，因为二叉树有严格的左右子树之分，咱们能够定义根节点，左子节点，右子节点的大小之分。于是有了二叉搜寻树：
二叉查找树（Binary Search Tree），（又：二叉搜寻树，二叉排序树）它或者是一棵空树，或者是具备下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也别离为二叉排序树。二叉搜寻树作为一种经典的数据结构，它既有链表的疾速插入与删除操作的特点，又有数组疾速查找的劣势；所以利用非常宽泛，例如在文件系统和数据库系统个别会采纳这种数据结构进行高效率的排序与检索操作。
二叉查找树样例如下：
比方下面的树，如果咱们须要查找到 4，从 5开始，4比 5 小，往左子树走，查找到 3，4 比3大，往右子树走，找到了 4，也就是一个 7 个节点的树，咱们只查找了 3 次，也就是层数，假如 n 个节点，那就是log(n+1)。
树保护好了，查问效率诚然高，然而如果树没保护好，容易进化成为链表，查问效率也会降落，比方：
一棵对查问敌对的二叉树，应该是一个均衡或者靠近均衡的二叉树，何为均衡二叉树：
均衡二叉搜寻树的任何结点的左子树和右子树高度最多相差 1。均衡二叉树也称为 AVL 树。
为了保障插入或者删除数据等之后，二叉树还是均衡二叉树，那么就须要调整节点，这个也称为均衡过程，外面会波及各种旋转调整，这里临时不开展。
然而如果波及大量的更新，删除操作，均衡树种的各种调整须要就义不小的性能，为了解决这个问题，有大佬提出了红黑树.
红黑树（Red Black Tree）是一种自均衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用处是实现关联数组。[1]
红黑树是在 1972 年由 Rudolf Bayer 创造的，过后被称为均衡二叉 B 树（symmetric binary B-trees）。起初，在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 批改为现在的“红黑树”。[2]
红黑树是一种特化的 AVL 树（均衡二叉树），都是在进行插入和删除操作时通过特定操作放弃二叉查找树的均衡，从而取得较高的查找性能。
红黑树有以下的特点：
- 性质 1. 结点是红色或彩色。
- 性质 2. 根结点是彩色。
- 性质 3. 所有叶子都是彩色。（叶子是 NIL 结点）
- 性质 4. 每个红色结点的两个子结点都是彩色。（从每个叶子到根的所有门路上不能有两个间断的红色结点）
- 性质 5. 从任一节结点其每个叶子的所有门路都蕴含雷同数目的彩色结点。
正是这些个性，让红黑树在调整的时候，不像一般的均衡二叉树调整那般艰难，频繁。也就是加上了条条框框，让它合乎肯定的规范，缩小均衡过程的凌乱以及频次。
后面说的哈希表，Java 中的实现，正是利用了红黑树，在 hash 抵触较多的时候，会将链表转换成为红黑树。
下面说的都是二叉树，然而咱们不得不扯一下多叉树，为什么呢？尽管二叉树中的各种搜寻树，红黑树曾经很优良了，然而在与磁盘交互的时候，大多数是数据存储中，咱们不得不思考 IO 的因素，因为磁盘 IO 比内存慢太多了。如果索引树的层高有几千上万，那么磁盘读取的时候，须要次数太多了。B 树更加适宜磁盘存储。
970 年，R.Bayer 和 E.mccreight 提出了一种实用于外查找的树，它是一种均衡的多叉树，称为 B 树（或 B - 树、B_树）。
一棵 m 阶 B 树 (balanced tree of order m) 是一棵均衡的 m 路搜寻树。它或者是空树，或者是满足下列性质的树：
1、根结点至多有两个子女；
2、每个非根节点所蕴含的关键字个数 j 满足：m/2 – 1 <= j <= m – 1；
3、除根结点以外的所有结点（不包含叶子结点）的度数正好是关键字总数加 1，故 外部子树 个数 k 满足：m/2 <= k <= m；
4、所有的叶子结点都位于同一层。
每个节点放多一点数据，查找的时候，内存中的操作比磁盘快很多，b树能够缩小磁盘 IO 的次数。B 树：
而每个节点的 data 可能很大, 这样会导致每一页查出来的数据很少，IO 查问次数天然就减少了，那咱们不如只在叶子节点中存储数据：
B+ 树是 B 树的一种变形模式，B+ 树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引应用。一棵 m 阶的 B + 树定义如下:
(1)每个结点至少有 m 个子女；
(2)除根结点外，每个结点至多有 [m/2] 个子女，根结点至多有两个子女；
(3)有 k 个子女的结点必有 k 个关键字。
个别 b + 树的叶子节点，会用链表连接起来，不便遍历以及范畴遍历。
这就是 b+ 树，b+树绝对于 B 树 多了以下劣势：
b+树的两头节点不保留数据，每次 IO 查问能查到更多的索引，, 是一个矮胖的树。- 对于范畴查找来说，
b+树只需遍历叶子节点链表即可，b树却须要从根节点都叶子节点。
除了下面的树，其实还有一种叫 Huffman 树：给定 N 个权值作为 N 个叶子结点，结构一棵二叉树，若该树的带权门路长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权门路长度最短的树，权值较大的结点离根较近。
个别用来作为压缩应用，因为数据中，每个字符呈现的频率不一样，呈现频率越高的字符，咱们用越短的编码保留，就能够达到压缩的目标。那这个编码怎么来的呢？
假如字符是 hello, 那么编码可能是（只是编码的大抵雏形，高频率呈现的字符，编码更短），编码就是从根节点到以后字符的门路的01 串：
通过不同权值的编码，哈夫曼树到了无效的压缩。
堆
堆，其实也是二叉树中的一种，堆必须是齐全二叉树，齐全二叉树是：除了最初一层，其余层的节点个数都是满的，最初一层的节点都集中在左部间断地位。
而堆还有一个要求：堆中每一个节点的值都必须大于等于（或小于等于）其左右子节点的值。
堆次要分为两种：
- 大顶堆：每个节点都大于等于其子树节点（堆顶是最大值）
- 小顶堆：每个节点都小于等于其子树节点（堆顶是最小值）
个别状况下，咱们都是用数组来示意堆，比方上面的小顶堆：
数组中父子节点以及左右节点的关系如下：
i结点的父结点parent = floor((i-1)/2)(向下取整)i结点的左子结点2 * i +1i结点的右子结点2 * i + 2
既然是存储数据的，那么肯定会波及到插入删除等操作，堆外面插入删除，会波及到堆的调整，调整之后能力从新满足它的定义，这个调整的过程，叫做 堆化。
用小顶堆举例，调整次要是为了保障：
- 还是齐全二叉树
- 堆中每一个节点都还小于等于其左右子节点
对于小顶堆，调整的时候是：小元素往上浮，大元素往下沉，就是一直替换的过程。
堆个别能够用来求解TOP K 问题，或者后面咱们说的优先队列等。
图
终于来到了图的解说，图其实就是二维立体，之前写过扫雷，扫雷的整个方块区域，其实也能够说是图相干的。图是非线性的数据结构，次要是由边和顶点组成。
同时图又分为有向图与无向图，下面的是无向图，因为边没有指明方向，只是示意两者关联关系，而有向图则是这样：
如果每个顶点是一个中央，每条边是门路，那么这就是一张地图网络，因而图也常常被用于求解最短距离。先来看看图相干的概念：
- 顶点：图最根本的单元，那些节点
- 边：顶点之间的关联关系
- 相邻顶点：由边间接关联的顶点
- 度：一个顶点间接连贯的相邻顶点的数量
- 权重：边的权值
个别示意图有以下几种办法：
- 邻接矩阵，应用二维数组示意，为 1 示意联通，0 示意不连通，当然如果示意门路长度的时候，能够用大于
0的数示意门路长度，用-1示意不连通。
上面的图片中，0 和 1，2 连通，咱们能够看到第 0 行的第 1，2 列是 1，示意连通。还有一点：顶点本身咱们是标识了 0，示意不连通，然而有些状况能够视为连通状态。
- 邻接表
邻接表，存储办法跟树的孩子链表示法相相似，是一种程序调配和链式调配相结合的存储构造。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点顺次寄存于表头结点所指向的单向链表中。
对于无向图来说，应用邻接表进行存储也会呈现数据冗余，表头结点 A 所指链表中存在一个指向 C 的表结点的同时，表头结点 C 所指链表也会存在一个指向 A 的表结点。
图外面遍历个别分为广度优先遍历和深度优先遍历，广度优先遍历是指优先遍历与以后顶点 间接相干 的顶点，个别借助队列实现。而深度优先遍历则是往一个方向始终走到不能再走，有点不撞南墙不回头的意思，个别应用递归实现。
图，除了用了计算最小门路以外，还有一个概念：最小生成树。
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且蕴含原图中的所有 n 个结点，并且有放弃图连通的起码的边。最小生成树能够用 kruskal（克鲁斯卡尔）算法或 prim（普里姆）算法求出。
有一种说法，图是立体上的点，咱们把其中一个点拎起来，能将其余顶点带起来的边，取最小权值，多余的边去掉，就是最小生成树。
当然，最小生成树并不一定是惟一的，可能存在多种后果。
秦怀 @观点
理解这些根本的数据结构，在写代码或者数据建模的时候，可能抉择更加适合的，这是最大的用途。计算机是为人服务的，代码也是，数据结构的全副类型咱们是无奈一下子一一把握的，然而根本的货色是变动不会很大，除非新一代革命性变动。
程序是由数据结构和算法组成，数据结构就像是基石，借助《数据结构 C 语言》版本中的一句话结尾：
为了编写出一个”好“的程序，必须剖析待处理的对象的个性以及各解决对象之间存在的关系，这就是”数据结构“这门学科和倒退的背景。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，集体网站：http://aphysia.cn，技术之路不在一时，山高水长，纵使迟缓，驰而不息。
剑指 Offer 全副题解 PDF
开源编程笔记