数据结构原理

数组：

数组是最常见的数据结构，创建数组必须要内存中一块连续的空间，并且数组中必须存放相同的数据类型。比如我们创建的长度10，数据类为整形的数组，在内存中的地址是从1000开始，那么他在内存中的存储格式如下：

由于每个整形数据占据4个字节的内存空间，因此整个数组的内存空间地址是1000--1039，根据这个，就可以轻易算出每个数据的内存下标地址，利用这个特性，只要知道了数组的下标，也就是数据在数组中的位置，比如下标2，就可以计算得到这个数据在内存中的位置1008，从而对这个位置的数据241进行快速的读写访问，时间复杂度为O(1)。随机快速读写是数组的一个重要特性，但是要随机访问数据，必须知道数据在数组中的下标，如果我们只是知道数据的值，想要在数组中找到这个值，那么就只能遍历整个数组，时间复杂度为O(n)

链表：

不同于数组必须要连续的内存空间，链表可以使用零散的内存空间存储数据，不过，因为链表在内存中的数据不是连续的，所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。如下图，链表的每个元素包含两个部分，一个部分是数据，一个部分是指向下个元素的地址指针，最后一个元素指向null，表示链表的结束。

因为链表是不连续存储的，要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是O(n)

但是就因为链表是不连续存储的，所以在链表中插入或者删除一个数据是非常容易的，只要找到要插入、删除的位置，修改链表指针就可以了，如图，想要在b和c之间插入一个元素x，只需要将b指向c的指针修改为指向x，然后将x的指针指向c就可以了。

相比在链表中国轻易的插入，删除一个元素这种简单的操作，如果我们想要在数组中插入、删除一个数据，就会改变数组连续内存空间的大小，需要重新分配内存空间，这样复杂度要大的多。

Hash表

对数组中的数据进行快速访问必须要通过数组的下标，时间复杂度为O(1)。如果只是知道数据或者数据中的部分内容，想要在数组中找到这个数据，还是需要遍历整个数组，时间复杂度为O(1).

如果知道了部分数据，查找完整数据的需求在软件开发中会经常遇到，比如说知道了商品的ID，想要查找完整的商品信息，知道了名称，想要查找详细的信息等等

这类场景需要用到Hash表这种数据结构，Hash表中的数据以Key、Value的方式进行存储，上面的例子中，商品ID和词条名称就是Key，商品信息和词条信息就是Value，存储的时候将Key、Value写入Hash表中，读取的时候，只是需要提供Key，就可以快速查找到Value

Hash表的物理存储其实就是一个数组，如果能够根据Key计算出数组的下标，就可以快速的在数组中查找到需要的Key和Value，编程语言支持获得任意对象的HashCode，比如说Java语言中HashCode方法包含在根对象Object中，其返回值是一个Int，可以利用这个int类型的HashCode计算数组的下标，最简单的方法就是余数法，使用Hash表的数组长度对HashCode求余数，余数即为Hash表的下标，使用这个下标就可以直接访问得到Hash表中存储的Key、Value

上面这个例子中，Key是字符串abc，Value是字符串hello，先计算Key的哈希值，得到101这样的一个整型值，然后利用101对8进行取模，这个8是哈希表数组的长度。101对8取模余数5，这个5就是数组的下标，这样就可以把（“abc”，“hello”）这样一个key、Value值存储在下标为5的数组记录中

读取数据的时候，只要给定key abc，用这样一个算法过程，先求取它的HashCode 101，然后对8进行取模，因为数组的长度不变，对8取模以后依然是5，那么我们到数组下标中找5这个位置，就可以找到前面存储进行的abc对应的value值

但是如果不同的key计算出来的数组下标相同怎么处理？HashCode101对8取模余数5，HashCode109对8取模余数也是5，也就是说，不同的key有可能计算得到相同数组下标，这就是所谓的Hash冲突，解决Hash冲突常用的方法就是链表法

事实上，（“abc”，“hello”）这样的key 、Value数据并不会直接存储在Hash表的数组中，因为数组要求存储固定数据类型，主要目的是每个数组元素中要存储固定长度的数据，所以，数组中存储的是key、value数据元素的地址指针，一旦发生了Hash冲突，只需要将相同下标，不同Key的数据元素添加到这个链表就可以了，查找的时候再遍历这个链表，匹配正确的key

因为有Hash冲突的存在，所以Hash表的时间复杂度为什么是O(1)，这句话的说的并不严谨，极端情况下，如果所有的key的数组下标都冲突，那么Hash表就退化为一条链表，查询的时间复杂度是O(n)。

栈

数组和链表都被称为线性栈，因为里面的数据是按照线性组织存放的，每个数据元素的前面只能有一个前驱数据元素，后面也只能有一个后继元素，所以称为线性栈。但是对数组和链表的操作可以是随机的，可以对其上任何元素进行操作，如果对操作方式加以限制，就形成了新的数据结构

栈是在线性表的基础上加了这样的操作限制条件，后面添加了数据，在删除的时候必须先删除，通常所说的“后进先出”。可以把栈想象成一个桶，往桶里面放食物，一层一层放进去，如果要吃的时候，必须从最上面一层开始吃，吃了几层之后，再往里面放食物，还是从当前的最上面一层放。

栈在线性表的基础上增加了操作限制，具体实现的时候，因为栈不需要随机访问，也不需要在中间添加，删除苏护具，所以可以用数组实现，也可以用链表实现。顺序表的基础上增加操作限制的好处是？

程序在运行的过程中，方法的调用需要用栈来管理每个方法的工作区，这样不管方法如何嵌套调用，栈顶元素始终是当前正在执行的方法的工作区，这样事情就会变得简单，简单是软件开发追求的一个目标

队列

队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出

在软件运行期间，经常会遇到资源不足的情况，提交任务请求线程池执行，但是线程池已经用完了，任务需要放入队列，先进先出排队执行，线程在运行中需要访问数据库，数据库连接有限，已经用完了，线程进入阻塞队列，当有数据库连接释放的时候，从阻塞队列头唤醒一个线程，出队列获得连接访问数据库。

树

数组、链表、栈、队列都是线性表，也就是每个数据元素都只有一个前驱，一个后继，而树则是非线性表，树是这样的

软件开发中，很多地方会用到树，比如说开发一个OA系统，部分的组织就是一颗树，编写程序在编译的时候，每一步就是将程序代码生成抽象语法树，传统上树的遍历使用的是递归的方式处理的。