算法复杂度分析

时间复杂度分析

时间复杂度分析：来评估代码的执行耗时的
大O表示法：不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势

空间复杂度

空间复杂度的全称是渐进空间复杂度，表示算法占用的额外存储空间和数据规模之间的增长关系

数组

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构

数组如何获取其他元素的地址值

寻址公式：a[i] = baseAddress + i * dataTypeSize
baseAddrss：数组的首地址
dataTypeSize：代表数组中元素类型的大小，int刑的数组，dataTypeSize=4个字节

为什么数组索引从0开始，而不是1

寻址公式：a[i] = baseAddress + (i-1) * dataTypeSize
此公式对cpu来说就多了一次减法指令，性能不如从0开始

操作数组的时间复杂度

查找

1. 随机查询（根据索引查询）：数据元素的访问是通过下标来访问的，计算机通过数组的首地址和寻址公式能欧很快速的找到想要访问的元素（O（1））
2. 未知索引查询
   情况一：查找数组内的元素（O（n））
   情况二：查找排序后数组内的元素（O（logn））

插入/删除

数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变得很低
最好的情况下是O（1），最坏的情况下是O（n），平均情况下的时间复杂度是O（n）

ArrayList

成员变量

构造方法

添加和扩容操作

如果空间够就直接添加，不够的话就扩容后拷贝数组再添加

实现原理

1. ArrayList底层是用动态的数组实现的
2. ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10
3. ArrayList在进行扩容的时候时原来容量的1.5倍，每次扩容都需要拷贝数组
4. ArrayList在添加数据的时候
   1. 确保数组已使用长度（size）加1之后足够存下下一个数据
   2. 计算数组的容量，如果当前数组已使用长度+1后的大于当前数组长度，则调用grow方法扩容（原来的1.5倍）
   3. 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上
   4. 返回添加成功布尔值

如何实现数组和List之间的转换

数组转换成List：Arrays.asList(Array)，修改原数组会收到影响，因为这个方法没有创建新对象，只是引用了地址
List转换为数组：list.toArray(new String[list.size()])

单向链表

1. 链表中的每一个元素称之为节点（Node）
2. 物理存储单元上，非连续，非顺序的存储结构
3. 单向链表：每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。记录下个节点地址的指针叫做后续指针

查询

1. 只有在查询头节点的时候不需要遍历链表，时间复杂度是O（1）
2. 查询其他节点需要遍历链表，时间复杂度时O（n）

删除

1. 只有在删除头节点的时候不需要遍历链表，时间复杂度是O（1）
2. 删除其他节点需要遍历链表，时间复杂度时O（n）

双向链表

顾名思义，它支持两个方向

1. 每个节点不止有一个后继指针next指向后面的节点，有一个前驱指针prev指向前面的节点
   对比单链表
   1. 双向链表需要额外的两个空间来存储后继节点和前驱节点的地址
   2. 支持双向遍历，这样也带来了双向链表操作的灵活性

ArrayList与LinkedList

1. 底层数据结构
   1. ArrayList是动态数组的数据结构实现
   2. LinkedList是双向链表的数据结构实现
2. 操作数据效率
   1. ArrayList按照下表查询的时间复杂度O（1）【内存是连续的，根据寻址公式】，LinkedList不支持下标查询
   2. 查询（未知索引）：ArrayList需要遍历，链表也需要遍历，时间复杂度都是O（n）
   3. 新增和删除
      1. ArrayList尾部插入和删除是O（1）；其他部分是O（n）
      2. LinkedList头尾节点删除时间复杂度是O（1）；其他部分是O（n）
3. 内存空间占用
   1. ArrayList底层是数组，内存连续，节省内存
   2. LinkedList是双向链表需要存储数据，和两个指针，更占用内存
4. 线程安全
   1. 都不线程安全
   2. 解决方案：
      1. 在方法内使用，局部变量是安全的
      2. 使用线程全的ArrayList和LinkedList
      3. List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>())

HashMap

二叉树

二叉树，每个节点最多有两个叉，也就是两个子节点，分别是左子节点和右子节点，不过，二叉树并不要求每个节点都有两个子节点，有的只有左子节点，有的只有右子节点
二叉树的每个左子树和右子树也分别满足二叉树的定义
Java中有两个方式可以实现二叉树：数组存储，链式存储
基于链式存储的数的节点可定义如下：

private class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	Treenode(){}
	Treenode(int val){this.val = val}
	Treenode(int val,TreeNode left,TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

二叉搜索树

二叉搜索树（Binary Search Tree，BST）右名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型，二叉查找树要求，在数中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值
插入，查找，删除的时间复杂度O（logn）

红黑树

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树（BST），之前叫做平衡二叉B树（Symmetric Binary B-Tree）

红黑树的特质

1. 节点要么是红色要么是黑色
2. 根节点是黑色
3. 叶子节点都是黑色的空节点
4. 红黑树中红色节点的子节点都是黑色
5. 从任意节点到叶子节点的所有路径都包含相同数目的黑色节点

红黑树的复杂度

查找，添加，删除：（O（logn））

散列表

在HashMap中的最重要的一个数据结构就是散列表，在散列表中又使用到了红黑树和链表
散列表（Hash Table）又名哈希表/Hash表，是根据键（Key）直接访问在内存存储位置值（Value）的数据结构，他是由数组演化而来的，利用了数组支持按照下标进行随机访问数组的特性。
将键（key）映射为数组下标的函数叫做散列函数，可以表示为：hashValue=hash（key）
散列函数的基本要求：

1. 散列函数计算得到的散列值必须是大于等于0的正整数，因为hashValue需要作为数组的下标。
2. 如果key1==key2，那么经过hash后得到的hash值也必相同：hash(key1)==hash(key）
3. 反之亦然

散列冲突

实际的情况想找一个散列函数能够做到对不同的key计算得到的散列值都不同几乎是不可能的，即是像著名的MD5，SHA等哈希算法也无法避免这一情况，这就是散列冲突（或者哈希冲突，哈希碰撞，就是多个key映射到同一下标）

HashMap的实现原理

HashMap的数据结构：底层使用hash标数据结构，即数组和链表或红黑树

1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况
   1. 如果key相同，则覆盖原始值
   2. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中
3. 获取时，直接找到hash值对应的下标，再进一步判断ey是否相同，从而找到对应值

jdk1.7与1.8的区别

1. JDK1.8之前采用的是拉链法。拉链法：将链表和数组结合。也就是说创建了一个链表数组，数组中每一格就是一个链表。若遇到hash冲突。则将冲突的值加到链表中即可
2. jdk1.8在解决hash冲突时有了较大的变化，当链表长度大于阈值（默认为8）时并且数组长度达到64时，将链表转化为红黑树，以减少搜索时间。扩容resize()时，红黑树拆分成的树的节点数小于等于临界值6个，则退化成链表

HashMap的put方法的具体流程

源码-常见属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认的初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的加载因子
transient HashMap.Node<K,V> [] table;
transient int size;

扩容阈值==数组容量*加载因子

Map<String,String> map = new HashMap<>();
map.put("666","666");	

以上代码会发生：

1. HashMap是懒惰加载，在创建对象时并没有初始化数组
2. 在无参的构造函数中，设置了默认的加载因子是0.75

添加数据

HashMap的扩容机制

1. 在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次扩容都是达到了扩容阈值（数组长度*0.75）
2. 每次扩容的时候，都是扩容之前的容量的2倍
3. 扩容之后，会创建一个数组，需要把老数组中的数据挪动到新的数组中
   1. 没有hash冲突的节点，则直接使用e.hash&(newCap-1)计算新数组的索引位置
   2. 如果是红黑树，走红黑树的添加
   3. 如果是链表，则需要遍历链表，可能需要拆分链表，判断（e.hash&oldCap），该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

HashMap的寻址算法

右移16位是扰动算法，使得hash值更加均匀，减少hash冲突

(n-1)&hash：得到数组中的索引，代替取模，性能更好，数组长度必须是2的n次幂

为什么HashMap的数组长度一定是2的次幂

1. 计算索引时效率更高：如果是2的n次幂可以使用位与运算代替取模
2. 扩容时重新计算索引效率更高：hash&oldCap==0的元素留在原来位置，否则新位置=旧位置+oldCap