数据结构是的大二时候学的，后来做项目的时候感觉其实应用的还挺多的，不过除了常用的基本上也都忘得差不多了，好好复习复习，查漏补缺。
链表与数组
数组是一组具有相同类型和名称的变量的集合。这些变量称为数组的元素,每个数组元素都有一个编号,
这个编号叫做下标,我们可以通过下标来区别这些元素。数组元素的个数有时也称之为数组的长度。数组在内存中是逐个存放的，也就是说倘若数组的第一个元素在地址A,则数组第二个元素就在地址A+1。
而链表则不是，链表每个节点没有相对固定的位置关系。某个节点在地址A其后的节点不一定是A+1,而在内存的其他空闲区域，呈现一种随机的状态。
数组一旦显式的被申明后，其大小就固定了，不能动态进行扩充。而链表则可以，可以动态生成节点并且添加到已有的链表后面。
链表灵活，但是空间和时间额外耗费较大；数组大小固定，元素位置固定，但是操作不灵活，且容易浪费空间，但是时间耗费较小，尤其是元素变化不大的时候效率很高。双向链表比单向的更灵活，但是空间耗费也更大
链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。
通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。
双链表的化每个元素即要保存到下一个元素的指针，还要保存一个上一个元素的指针。
循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。
队列和栈，出栈与入栈。
栈和队列是两种特殊的线性表
1) 栈（LIFO，后进先出）
栈是一种限定只能在栈尾执行插入和删除操作的线性表。
栈的顺序存储结构：进栈/出栈操作均在数组尾部，时间复杂度=O(1);
缺陷：数组长度固定，长度不够时需扩容，消耗资源。
栈的链式存储结构：保存栈顶指针，出栈与入栈的时间复杂度=O(1)，且没有数据空间的限制
2) 队列(queue)(FIFO,先进先出)
队列的顺序存储结构：入列时间复杂度=O(1),出队列时间复杂度=O(n)
循环队列：解决出队列操作时间复杂度=O(n)的问题，队列的链式存储结构：入/出队列时间复杂度=O(1)
在长度确定的情况下，用顺序存储结构；长度变化较大，用链式。
字符串操作
| 要求 | 方法 | 解释 |
|---|---|---|
| 字符串的连接 | public String concat(String str) | 该方法的参数为一个String类对象,作用是将参数中的字符串str连接到原来字符串的后面. |
| 求字符串的长度 | public int length() | 返回字串的长度,这里的长度指的是字符串中Unicode字符的数目. |
| 求字符串中某一位置的字符 | public char charAt(int index) | 该方法在一个特定的位置索引一个字符串,以得到字符串中指定位置的字符.值得注意的是,在字符串中第一个字符的索引是0,第二个字符的索引是1,依次类推,最后一个字符的索引是length()-1. |
| 字符串的比较 | public int compareTo(String anotherString) | 其比较过程实际上是两个字符串中相同位置上的字符按Unicode中排列顺序逐个比较的结果.如果在整个比较过程中,没有发现任何不同的地方,则表明两个字符串是完全相等的,compareTo方法返回0;如果在比较过程中,发现了不同的地方,则比较过程会停下来,这时一定是两个字符串在某个位置上不相同,如果当前字符串在这个位置上的字符大于参数中的这个位置上的字符,compareTo方法返回一个大于0的整数,否则返回一个小于0的整数. |
| 字符串的比较 | public boolean equals(Object anObject) | 该方法比较两个字符串,和Character类提供的equals方法相似,因为它们都是重载Object类的方法.该方法比较当前字符串和参数字符串,在两个字符串相等的时候返回true,否则返回false. |
| 字符串的比较 | public boolean equalsIgnoreCase(String anotherString) | 该方法和equals方法相似,不同的地方在于,equalsIgnoreCase方法将忽略字母大小写的区别 |
| 从字符串中提取子串 | public String substring(int beginIndex) | 该方法从beginIndex位置起,从当前字符串中取出剩余的字符作为一个新的字符串返回. |
| 字符串的比较 | public String substring(int beginIndex, int endIndex) | 该方法从当前字符串中取出一个子串,该子串从beginIndex位置起至endIndex-1为结束.子串返的长度为endIndex-beginIndex. |
| 判断字符串的前缀和后缀 | public boolean startsWith(String prefix) | 该方法用于判断当前字符串的前缀是否和参数中指定的字符串prefix一致,如果是,返回true,否则返回false. |
| 判断字符串的前缀和后缀 | public boolean startsWith(String prefix, int toffset) | 该方法用于判断当前字符串从toffset位置开始的子串的前缀是否和参数中指定的字符串prefix一致,如果是,返回true,否则返回false. |
| 判断字符串的前缀和后缀 | public boolean endsWith(String suffix) | 该方法用于判断当前字符串的后缀是否和参数中指定的字符串suffix一致,如果是,返回true,否则返回false. |
| 字符串中单个字符的查找 | public int indexOf(int ch) | 该方法用于查找当前字符串中某一个特定字符ch出现的位置.该方法从头向后查找,如果在字符串中找到字符ch,则返回字符ch在字符串中第一次出现的位置;如果在整个字符串中没有找到字符ch,则返回-1. |
| 字符串中单个字符的查找 | public int indexOf(int ch, int fromIndex) | 该方法和第一种方法类似,不同的地方在于,该方法从fromIndex位置向后查找,返回的仍然是字符ch在字符串第一次出现的位置 |
| 字符串中单个字符的查找 | public int lastIndexOf(int ch) | 该方法和第一种方法类似,不同的地方在于,该方法从字符串的末尾位置向前查找,返回的仍然是字符ch在字符串第一次出现的位置. |
| 字符串中单个字符的查找 | public int lastIndexOf(int ch, int fromIndex) | 该方法和第二种方法类似,不同的地方在于,该方法从fromIndex位置向前查找,返回的仍然是字符ch在字符串第一次出现的位置. |
| 字符串中子串的查找 | public int indexOf(String str) public int indexOf(String str, int fromIndex) public int lastIndexOf(String str) public int lastIndexOf(String str, int fromIndex) | 类似查找单个字符 |
| 字符串中字符大小写的转换 | public String toLowerCase() | 该方法将字符串中所有字符转换成小写,并返回转换后的新串. |
| 字符串中子串的查找 | public String toUpperCase() | 该方法将字符串中所有字符转换成大写,并返回转换后的新串. |
| 字符串中多余空格的去除 | public String trim() | 该方法只是去掉开头和结尾的空格,并返回得到的新字符串.值得注意的是,在原来字符串中间的空格并不去掉. |
| 字符串中字符的替换 | public String replace(char oldChar,char newChar) | 该方法用字符newChar替换当前字符串中所有的字符oldChar,并返回一个新的字符串. |
| 字符串中字符的替换 | public String replaceFirst(String regex, String replacement) | 该方法用字符串replacement的内容替换当前字符串中遇到的第一个和字符串regex相一致的子串,并将产生的新字符串返回. |
| 字符串中字符的替换 | public String replaceAll(String regex, String replacement) | 该方法用字符串replacement的内容替换当前字符串中遇到的所有和字符串regex相一致的子串,并将产生的新字符串返回. |
String、StringBuilder、StringBuffer
三者在执行速度方面的比较：StringBuilder > StringBuffer > String
StringBuilder：线程非安全的
StringBuffer：线程安全的
如果要操作少量的数据用 = String
单线程操作字符串缓冲区 下操作大量数据 = StringBuilder
多线程操作字符串缓冲区 下操作大量数据 = StringBuffer
Hash表的hash函数，冲突解决方法有哪些
在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样我们就能预先知道所查关键字在表中的位置，从而直接通过下标找到记录。使ASL趋近与0.
哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；
由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1 != key2，而 f(key1) = f(key2)。
只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值
| hash构造函数 | 解释 | 适用场景 |
|---|---|---|
| 直接定址法 | 哈希函数为关键字的线性函数，H(key) = key 或者 H(key) = a ´ key + b | 哈希函数为关键字的线性函数，H(key) = key 或者 H(key) = a ´ key + b |
| 数字分析法 | 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。 | 能预先估计出全体关键字的每一位上各种数字出现的频度 |
| 平方取中法 | 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。 | 关键字中的每一位都有某些数字重复出现频度很高的现象 |
| 折叠法 | 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分割后的几部分低位对齐相加；间界叠加:从一端沿分割界来回折叠，然后对齐相加。 | 关键字的数字位数特别多。 |
| 除留余数法 | 设定哈希函数为:H(key) = key MOD p ( p≤m )，其中， m为表长，p 为不大于 m 的素数，或是不含 20 以下的质因子 | |
| 随机数法 | 设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数 | 对长度不等的关键字构造哈希函数 |
冲突解决办法
1) 开放定址法：为产生冲突的关键字地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤s≤m-1，Hi = ( H(key)+di ) MOD m，其中： i=1, 2, …, s，H(key)为哈希函数;m为哈希表长;
2) 链地址法：将所有哈希地址相同的记录都链接在同一链表中；
3) 再哈希法：构造若干个哈希函数，当发生冲突时，根据另一个哈希函数计算下一个哈希地址，直到冲突不再发生。即：Hi=Rhi(key) i=1,2,……k，其中：Rhi——不同的哈希函数，特点：计算时间增加