表和集合相关表和集合相关

1：算法时间复杂度
大O表示法：语句的总执行次数 T（n）是关于问题规模n的函数。随着问题规模的增加，算法时间的增长率和f(n)的增长率相同。记作T（n）=O（f（n））。
计算方法：只保留最高阶。用常数1代替
常数项： int sum=（1+n）*n
平方阶: 多重for(int i=0; i<10; i++)
线性阶：简单for循环
对数阶：count=count*2count< n 有多少个2相乘后大于n，就会退出
常用的算法时间复杂度：
O（1） 【表和集合相关】2:算法的空间复杂度
算法的空间复杂度一般都是计算算法所需要的存储空间实现
2：线性表线性表：是由0个或者多个相同元素的有限序列
当元素存在多个的情形下：则第一个元素没有前驱，最后的一个元素没有后继。
线性表分为顺序存储结构和链式存储结构。
2.1：顺序存储结构顺序存储结构：指的是用一段地址连续的存储单元依此存储线性表的数据元素。
数组的长度是指存放这个线性表的存储空间的长度。
而线性表的长度，是指线性表中数据元素的个数。

存储器中的每一个存储单元都有自己的编号，这个编号就是地址。

假如每个数据元素都占用C个存储单元。那么在线性表中a1和an之间的地址就存在一定的关系。这样就可以随便算出每一个元素的地址。不管是第一个还是最后一个，都是相同的时间。这个时间其实就是O（1）。
2.1.1: 顺序表的插入和删除操作
顺序表的插入操作是：
1：如果插入位置不合理，就直接抛出异常
2：如果线性表长度大于等于数组长度，则会开始进行动态扩容
3：从最后的一个元素一直到将要插入的位置后的数据元素依次向后移动一位。
4：将插入位置放到指定位置处。
重点：当要插入的元素位置，必须要小于数组中实际元素的位置。如果这个顺序表中没有元素，是会报指针越界异常的。
删除操作：
前面几步类似
3：从要删除的元素的下一个元素一直到最后一个数据元素直接向前移动一位。
2.2：链式存储结构为了表示每个数据元素和其后面的元素之间的逻辑关系。对数据元素ai来说，除了要存储其本身的信息外，还需要存储一个指示其直接后继的信息。我们把存储这个数据元素的域称为数据域，存储直接后继位置的域称为指针域。这两部分信息称为节点 node。
N个节点链接为一个链表，这个就是线性表的链式存储结构。因此，每个节点中只包含了一个指针域，所以叫做单链表。
一般会在第一个数据节点的前面附加一个节点，叫做头节点。
头指针是链表指向第一个结点的指针，若链表有头节点，则是指向头节点的指针。
有了头节点，对在第一个元素节点前插入节点和删除节点就与其他操作节点统一了。
可以没有头节点，但是一定有头指针。
.2.1：单链表的插入和删除

插入：空节点S s.next=p.nextp.next=s;
删除要删除的q q=p.nextp.next=q.next

单链表的插入和删除其实分为2个部分：
1：遍历和查找节点i
2：插入和删除节点i
从整个算法的时间复杂度来说，其实都是O（n）操作。但是侧重点不一样。链表的插入和删除都是O（n），主要是由于在查找结点的时候消耗掉了，再进行插入和删除的时候，是O（1）.但是顺序表的查找要操作的节点位置是O（1），但是在进行插入和删除的时候是O（n）。需要把相关数据元素整体移动！！！在移动的过程中消耗的是O（n）。
2.2.2 单循环链表和双向链表
循环链表：将单链表中的最后一个节点的指针改为指向头节点，就使整个单链表形成了一个环，这种首尾相互循环的单链表就成为单循环链表。
双向链表：在单链表的每个节点中，再设置一个指向其前驱的指针域。
双向链表的添加： pq中添加S
首先保证P和Q 之间是没有断线
1：S.prior=P
2: S.next=P.next
3:p.next.prior=s
4:p.next=s
顺序非常重要，如果第4步先执行，那么p的后继指针节点位置就会消失，也就是说p和q之间就会断线

双向链表的删除：删除S节点
1：把S.next赋值给S的前驱的后继S.prior.next=s.next
2：把S。prior 赋值给S.next.priors.next.prior=s.prior

3:Hash 散列技术：
散列技术在记录的存储位置和它的关键字之间建立了一个确定的对应关系，使得每个关键字key都对应了一个存储位置。这种对应关系就是称为散列函数，又被称为哈希函数。
Hash值冲突的解决方法：

1：开放地址法：就是一旦发生了冲突，就回去寻找下一个散列位置，只要散列表足够大，它的散列地址总是可以找到的。这种解决冲突的开放地址法也被称为了线性探测法。它主要是用在：散列表未填满的时候，总是能找到不发生冲突的地址时，用到的。当出现多个不是同义词但是却需要争夺一个地址的情况时，我们称这种现象为堆积。
2：再散列函数法：就是当发生地址冲突的情况下，再使用其他的散列函数来计算，相信总有一个可以解决冲突。
3：链地址法：简单点就是将所有关键字为同义词的记录存储到一个单链表中，这样绝对不会存在找不到地址的问题，但是查找效率比较低。

4：集合集合和数组的区别：
1：数组就是一个顺序表，内容是固定的，是用一段连续的存储单元来表示
而集合容量是不固定的。有个默认值为10，当超过的时候，会进行扩容，一般是扩容1.5倍
2：数组可以存放基本数据类型和引用类型，但是一个数组里面只能存放一种类型
而集合，可以保持有多种数据类型。
在现实生活中，不同的事物需要使用不同的容器存放，这样不断抽取，就出现了一个顶级接口collection.
Collection没有直接的实现类，一般都是实现它的子类。并且一般都是以多态的形式出现。

使用多态，前提是，引用类型和实际的对象的类型之间需要有继承关系（实现接口的关系）。

4.1：迭代器
迭代器iterator是一个标准化来遍历集合数据的接口。
但是要遍历集合中的所有元素，因为集合的实现不同，保存数据的方式也不一样，所以我们取出数据的方法也不一样；
要该集合内部实现了迭代器，就可以在不知道API或者集合内部结构的情况下通过迭代器遍历该集合的元素。
迭代器存在一个快速失败机制，Java 集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作或者集合在迭代元素时直接直接调用自身方法改变集合结构而没有通知迭代器时，有可能会触发 fail-fast 机制并抛出ConcurrentModificationException异常

因为一旦获取这个容器的迭代器对象，那么这个迭代器就会保存这个容器的索引信息，
每次调用迭代器的next方法的时候，就会移动光标，就会比对迭代器的信息和元素信息，如果两者不相等，就会报错，建立多线程下使用CopyOnWriteArrayList （线程安全的集合类）。

迭代器只能单向迭代。
使用集合的remove会报错，但是使用迭代器的remove不会报错！！！！
4.2：list接口
使用增强for循环遍历list的时候，不能修改容器接口，会报错，
List接口的实现类主要有ArrayList；LinledList；Vector；
这个容器允许有重复元素，也可以存储null。

ArrayList 底层，实际上是用一个Object数组来保存数据的默认大小是10.当容量不够的时候，会开启自动扩容，扩容为1.5倍。调用方法是Arrays.copyOf来实现扩容。
LinkedList 其实就是基于链表的接口实现。
Vector 其实就是一个线程安全的list，效率比较低。

4.3 Set接口
1、set接口，只能保存不重复的元素；判断是否重复，主要通过equals方法判断；读取数据的顺序是无法保证的。
常用的HashSet TreeSet等
Hash表：
利用哈希算法，根据数据的特征，对保存的数据进行分块的一种数据结构，可以提高数据的查找效率。
Hash表就是一个链表+数组。

Hash保存数据的流程：
1、计算要保存对象的哈希值（Java中通过对象的hashCode方法获取），然后根据哈希值计算数据在哈希表中的位置；
2、找到位置后，如果位置上已经有数据了，就调用equals方法判断新保存的数据和原来的数据是否相等，如果相等，就不用保存，否则就在相应位置扩展一个空间保存新数据；

HashSet要能够保证保存的对象唯一，首先需要调用保存的对象的hashCode方法，获取哈希值，计算对象需要保存的位置，并以此判断对象接下来是否需要通过equals方法进行相等性判断；
如果两个对象的哈希值不同，就不会保存在同一区域，也不会调用equals方法进行相等性验证；

如果是自定义的对象保存到HashSet中时，需要重写HashCode方法和Equal方法。

LinkedHashSet这个就是为了保证存储有顺序。
4.3.2 TreeSet
如果向集合中存储自定义元素，并且还按照一定字段进行排序。需要使用TreeSet。底层是二叉树的实现，
在排序时通过compareTo（或 compare）方法对所有元素进行比较；
自定义的对象必须实现Compareable接口或者是直接传递比较器来进行比较。
4.4：总结
Collection集合：它本身接口，是在定义所有单列集合的共性操作规则。增删查判断遍历方法，没有修改的方法

List接口：
有序列表，可以存放重复元素，可以根据下标（索引、角标）操作集合中的任何元素。
List接口中定义了可以根据角标操作的增删改查方法。
ArrayList：底层是可变数组，查询快，增删慢。线程不安全。
LinkedList：底层是链表结构，增删快，查询慢。线程不安全。
Vector：底层是可变数组，什么都慢。被ArrayList代替。线程安全。

Set接口：
不能存储重复元素。允许有一个null。
HashSet：底层哈希表，不保证存取顺序。保证元素唯一，需要依赖元素的hashCode和equals方法。因此给哈希表中存放的元素需要复写Object类中的hashCode和equals方法。
LinkedHashSet：底层是哈希表+链表，没有自己特有方法，全部继承HashSet，可以保证存取顺序。保证唯一。
TreeSet：底层是二叉树（红黑树）。可以对其中存储的元素进行排序。排序依赖当前这个对象的compareTo方法。要求给二叉树中存储的对象所属的类要实现Comparable接口。
如果对象自身的compareTo方法不符合当前要求，或者对象本身就没有比较大小的方法，这时可以定义比较器对象Comparator。将这个比较器传递给TreeSet集合。

5 Map Map是保存了Key—Value的键值对。其中它的key是一个set集合，value是一个collections。
主要有下面几种map。一个是HashMap一个是TreeMap还有一个HashTable。
5.1 HashMap

容量(Capacity)和负载因子(Load factor)
默认容器是16，加载因子是0.75，当bucket填充的数目（即hashmap中元素的个数）大于capacity*load factor时就需要调整buckets的数目为当前的2倍并且重新调用Hash方法。
HashMap是线程不安全的。在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

5.2 HashTable
它是线程安全的，它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table，这就意味着所有的线程都在竞争一把锁，在多线程的环境下，它是安全的，但是无疑是效率低下的。
5.3 ConcurrentHashMap

ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成。
Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到的锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样。
在Jdk1.8的时候，已经完全修改了。
JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap。