主题
数据结构面试题
一、栈(stack)
栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶(top)，它是后进先出(LIFO)的。对栈的基本操作只有push(进栈)和pop(出栈)两种，前者相当于插入，后者相当于删除最后的元素。
| boolean | empty()：测试堆栈是否为空 |
|---|---|
| peek()：查看栈顶部对象，但不从堆栈中移除它。 | |
| pop()：移除堆栈顶部的对象，并作为此函数的值返回该对象 | |
| push()：把项压入堆栈顶部。 | |
| int | search()：返回对象在堆栈中的位置，以1为基数。 |
二、队列(queue)
队列是一种特殊的线性表，特殊之处在于只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端成为对尾，进行删除的端成为队头。(先进先出)
| offer | 方法往队列添加元素如果队列已满直接返回false,队列未满则直接插入并返回true; |
|---|---|
| add | 方法是对offer()方法的简单封装.如果队列已满,抛出异常new IllegalStateException("Queue full") |
| put | 方法往队列里插入元素,如果队列已经满,则会一直等待直到队列为空插入新元素,或者线程被中断抛出异常 |
| remove | 方法直接删除队头的元素 |
| peek | 方法直接取出队头的元素,并不删除 |
| element | 方法对peek方法进行简单封装,如果队头元素存在则取出并不删除,如果不存在抛出异常NoSuchElementException() |
| poll | 方法取出并删除队头的元素,当队列为空,返回null |
| take | 方法取出并删除队头的元素,当队列为空,则会一直等待直到队列有新元素可以取出,或者线程被中断抛出异常 |
三、链表(Link)
链表是一种数据结构，和数组同级。比如，在java中我们使用的ArrayList，其实就是链表，链表在进行循环遍历时效率不高，但是插入和删除时优势明显。
四、散列表
散列表(Hash table，也叫哈希表)根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数**，存放记录的数组叫做散列表****。**
记录的存储位置=关键字。
这里的对应关系关键字称为散列函数，又称为哈希(hash函数)，采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表。
散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素，因而必须要在数据元素的存储位置和它的关键字（可用 key 表示）之间建立一个确定的对应关系，使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时，只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。
Hash的应用
1、Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
2、查找：哈希表，又称为散列，是一种更加快捷的查找技术；当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！
例：假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。
3、Hash表在海量数据处理中有着广泛应用。
散列表的优缺点：
1.优点：
不论哈希表中有多少条数据，查找、插入、删除（有时也包括删除）只需要接近常量的时间即O(1)的时间级；哈希表运算的非常快，在计算机程序中，如果需要在一秒钟内查找上千条记录通常使用哈希表，哈希表的速度明显比树快，树的操作通常需要O(N)的时间级；如果不需要有序遍历数据，并且可以提前预测数据量的大小，那么可以使用哈希表。
2.缺点：
它是基于数组的，数组创建后难于扩建，在某些哈希表被基本填满时，性能下降非常严重；所以开发人员必须要清除表中到底要存储多少数据；或者定期将哈希表里的数据转移到更大的哈希表中（费时）。
哈希函数的构造方法：
1.直接定址法
取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数（这种散列函数叫做自身函数）。
2.除余法
取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址，即： h(key) = key MOD p p ≤ m。
3.基数转换法
将关键码看作是某个基数制上的整数，然后将其转换为另一基数制上的数。
例：
4.平方取中法
求得关键字的平方，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的的每一位都相关，所以由此产生的散列地址较为均匀。
5.折叠法
折叠法即将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。
哈希冲突
哈希冲突是指利用同样的计算方式，对不同的内容计算出相同的哈希地址，这就是哈希冲突，例：
哈希表需要把巨大的数字空间压缩为较小的数字空间，然要付出代价，即不能保证每个单词都映射到数组的空白单元。例如上面的哈希函数对21和30求出的哈希地址就是相同的，这就是哈希冲突。
哈希冲突的处理
1.开放定址法
当冲突发生时，使用某种探查技术在散列中形成一个探序列。沿着该序列查找，直到找到关键字或一个开放的地址（即地址单元为空）。一般有线性探查法和双散列函数法：
- 线性探查法
发生冲突后直接向下线性找一个新的空间存放。例如：
3和8的哈希地址都为3号地址，当存储8的时候发现地址内已经存储了3，那么就向下探查到4号地址，如果为空，就将8存储到4号地址，依次类推，发生冲突就向下探查，知道发现开放地址。
同时还有二次探查法，即向下探测的间隔是平方式，例如哈希表中原始下标是x，那么线性探测是：x+1，x+2，x+3……；而在二次探测中，探测过程是：x+12，x+22，x+32……。二次探测是防止聚集的产生，思想是探测相隔较远的单元，而不是相邻的单元。
- 双散列表函数法
当发生冲突之后，向下探查的间隔由函数hi决定。
2.拉链法
当存储结构是链表时，多采用拉链法，用拉链法处理冲突的办法是：把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。
用拉链法处理冲突，虽然比开放定址法多占用一些存储空间用做链接指针，但它可以减少在插入和查找过程中同关键字平均比较次数(平均查找长度)，这是因为，在拉链法中待比较的结点都是同义词结点，而在开放定址法中，待比较的结点不仅包含有同义词结点，而且包含有非同义词结点，往往非同义词结点比同义词结点还要多。
显然，开放定址法处理冲突的的平均查找长度要高于拉链法处理冲突的平均查找长度。
**拉链法的缺点：**指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
五、排序二叉树
首先如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值大于它的根节点值，则这样的二叉树就是排序二叉树。
插入操作
首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中 寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。
删除操作
删除操作主要分为三种情况， 即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。
- 对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
- 对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
- 对于要删除的节点有两个子节点， 则首先找该节点的替换节点（即右子树中最小的节点），接着替换要删除的节点为替换节点，然后删除替换节点。
查询操作
查找操作的主要流程为：先和根节点比较，如果相同就返回， 如果小于根节点则到左子树中归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值
六、前缀树
前缀树(Prefix Trees 或者 Trie)与树类似，用于处理字符串相关的问题时非常高效。它可以实现快速检索，常用于字典中的单词查询，搜索引擎的自动补全甚至 IP 路由。下图展示了“top”, “thus”和“their”三个单词在前缀树中如何存储的：
7.B-Tree
B-tree 又叫平衡多路查找树。一棵 m 阶的 B-tree (m 叉树)的特性如下（其中 ceil(x)是一个取上限的函数） ：
- 树中每个结点至多有 m 个孩子；
- 除根结点和叶子结点外，其它每个结点至少有有 ceil(m / 2)个孩子；
- 若根结点不是叶子结点，则至少有 2 个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，实际上这些结点不存在，指向这些结点的指针都为 null)；
- 每个非终端结点中包含有 n 个关键字信息： (n， P0， K1， P1， K2， P2， ......， Kn， Pn)。其中：
a) Ki (i=1...n)为关键字，且关键字按顺序排序 K(i-1)< Ki。
b) Pi 为指向子树根的接点，且指针 P(i-1)指向子树种所有结点的关键字均小于 Ki，但都大于 K(i-1)。
c) 关键字的个数 n 必须满足： ceil(m / 2)-1 <= n <= m-1。
一棵 m 阶的 B+tree 和 m 阶的 B-tree 的差异在于：
1.有 n 棵子树的结点中含有 n 个关键字； (B-tree 是 n 棵子树有 n-1 个关键字)
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B-tree 的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(B-tree 的非终节点也包含需要查找的有效信息)