数据结构总结

线性表之顺序表

数组是顺序存储的随机存取结构，占用一组连续的存储单元，通过下标识别元素，元素地址是下标的线性函数，一个下标能唯一确定一个元素
模拟ArrayList

线性表之单链表

线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相连的数据元素在物理位置上不一定相连，必须采用附加信息表示数据元素之间的关系，并且存储单元至少包含两部分-数据域和地址域
单链表中结点只有一个地址并且指向后继结点
模拟SinglyLinkenList

串之字符串

串是由n(n>=0)个字符组成的有限序列，它是一种特殊的线性表。而子串是指串s中任意连续字符组成的一个子序列组成的串。同时，串的比较通常由其字符编码的相关规则比较

常量字符串String
字符串采用字符数组作为存储结构，并且采用顺序存储结构，不过String类一次性申请了固定的空间，同时由于其存储结构为最终型，所以string不提供删除，插入子串
变量字符串StringBuffer
该字符数组的容量总是大于串长，并且能够修改

栈

栈是一种特殊的线性表，其特殊之处在于插入和删除操作的位置受到限制，而且插入和删除只允许在线性表的一端进行，特点是后进先出
顺序栈、链式栈

队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。特点是先进先出。
顺序队列使用数组存储数据元素
1.当队列空时，设置队头、队尾下标front=rear=-1，
2.当第一个元素入队时，front=rear=0，同时改变两个下标
3.进行入队、出队操作，front、rear随之变化
4.当入队的元素个数（包括已出队元素）超出数组容量时，rear下标越界，数据溢出，但是，由于之前已有若干元素出队，数组前部以空出许多存储单元，所以这种溢出并不是因为存储空间不够而产生的，称为假溢出
所以顺序队列有两个缺点：假溢出和存储单元没有重复使用机制
顺序循环队列
相比较顺序队列，有如下不同
1.队头、队尾元素按照如下循环规律变化，其中length表示数组长度
front=（front+1)%length;
rear=(rear+1)%length;
所以可以看出front和rear的取值范围为0~length-1
链式队列

树和二叉树

基本术语
孩子优先遍历
兄弟优先遍历
完全二叉树和满二叉树
顺序与链式存储
模拟二叉树类

hash散列表

散列（hash）表是一种支持高效的查找、插入和删除操作的数据结构，它是针对查找效率接近O（1）而专门设计的。它根据元素的关键字确定元素的存储位置，而其中主要解决两个问题，设计散列函数和处理冲突
散列函数实质上是关键字集合到地址集合的映射，如果这种映射是一一对应的，则查找效率是O（1），但是由于散列表是一个压缩映射，即存储容量有限，即映射关系是多对一的映射，所以会产生冲突
除留余数法
该散列函数定义为hash（k）=k%p，函数结果范围为0~p-1，图示就是采用这种方法，而p取值为小于散列表长度的最大素数，如散列表长度分别为8,16,128，则对应的p（最大素数）分别为7,13,127
开放定址法
链地址法
模拟HashSet类

二叉排序树

原理
AVL树

哈夫曼树

基本术语
哈弗曼编码
压缩与解压原理

图

基本术语
邻接矩阵
深度（先序）
广度（层序）

集合简单总结

java集合主要分为以下三种类型：
Set(集)：集合中的对象不按特定方式排序，且没有重复对象。它的有些实现类能对集合中的对象按照特地方式排序。
List(列表)：集合中的对象按照索引位置排序，可以有重复对象，允许使用索引检索对象。
Map(映射)：集合中的每一个元素都包含一对键对象和值对象（key-value），集合中的键对象是不能重复的,它的一些实现类能对集合中的键对象进行排序。
注意这里的不能重复与比较hashcode和equals有关

Collection接口
Collection接口是Set、List、Queue接口的父接口，提供了多数集合常用的方法声明，包括 add()、remove()、contains() 、size() 、iterator() 等

List接口
它的特点是有序可重复，使用此接口能够精确的控制每个元素插入的位置用户能够使用索引来访问List中的元素并且允许有可重复的元素

ArrayList
底层实现是一个动态的数组，查询快，增删慢，线程不安全，效率高

LinkedList
底层实现是一个双向循环链表，查询慢，增删快，线程不安全，效率较高

Vector
是ArrlyList的线程安全版，底层同它基本一致，但是效率低，现在基本很少

Set接口
它的特点就是唯一性并且不允许出现重复元素和是无序的

hashSet
底层是基于哈希表实现的，而其核心就是先比较hashCode（）值是否相同（相当于索引），然后在用equals比较是否相同，从而确定元素是否重复，所以当不希望集合中有重复值，并且不关心元素之间的顺序时可以使用此类

LinkedHashSet
底层实现是使用链表和哈希表，它由链表保证元素有序，哈希表保证元素唯一，因此当不希望集合中有重复值，并且希望按照元素的插入顺序进行迭代遍历时可采用此类

TreeSet
底层实现是红黑树，也就是一种平衡AVL树，通过比较返回值是否是0来保证元素唯一性，并且通过自然排序来保证元素的排序（自然排序也就是让元素所属的类实现Comparable接口，比如abc排在abd前面，总之就是和插入顺序无关，只和元素本身的内容和特质有关）

Queue接口
它的特点就是队列，即用于保存将要执行的任务列表

LinkedList
实现了该接口，可以实现先进先出的队列

PriorityQueue
底层采用某种排序的单链表存储队列元素，用来创建自然排序的优先级队列

Map接口
Map关心的是唯一的标识符，也就是将唯一的键映射到某个元素，以键值对形式存储，键唯一，值可重复

HashMap
底层实现是基于哈希表依赖于hashCode（）和equals（）方法，线程不安全，允许key和value为NULL，效率高

Hashtable
HashMap的线程安全版，效率低，不允许key和value为NULL

LinkedHashMap
底层是由链表和哈希表组成，链表保证元素有序，哈希表保证元素唯一，所以当需要键值对，并且关心插入顺序时可采用它

TreeMap
底层是由红黑树实现，当需要键值对，并关心元素的自然排序时可采用它

Collections
内置了一些常见的集合算法，像排序，查找算法等

13.并发集合类是什么？
Java1.5并发包（java.util.concurrent）包含线程安全集合类，允许在迭代时修改集合。迭代器被设计为fail-fast的，会抛出ConcurrentModificationException。一部分类为：CopyOnWriteArrayList、 ConcurrentHashMap、CopyOnWriteArraySet。

多路查找树

每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素
2-3树、2-3-4树
B树、B+树、

说说红黑树

红黑树—使二叉搜索树更加平衡：他是一种二叉搜索树，但在每个节点上增加一个存储
位表示节点的颜色，可是red 或black，红黑树的查找、插入、删除的时间复杂度最坏为O(lgn)。
因为由n 个节点随机生成的二叉搜索树的高度为lgn，所以二叉搜索树的一般操作的执行时
间为O(lgn)。如何保证一颗n 个节点的红黑树的高度始终为lgn，因为红黑树的5 个性质：
1）每个节点，要么红的，要么黑的
2）根节点是黑的
3）叶节点都是黑的，指的是NIL 指针
4）若一个节点时红的，则它的两个儿子都是黑的。
5）对于任意节点而言，其到叶节点数尾端NIL 指针的每条路径都包含相同数目的叶节点。