蚂蚁课堂每特教育第五期互联网架构tomcat8深度源码分析底层模式

1、Tomcat8深度源码分析COMMODITY DESIGN OF LARGE-SCALE MERCE SYSTEM134533idea如何导入Tomcat8源码实现断点调试Tomcat底层是如何实现启动244Tomcat8启动方式有那些14Tomcat8核心架构流程源码分析为什么Java8中的HashMap会引入 红黑树？目的是什么？为什么Java8中的HashMap会引入 红黑树？目的是什么？在Java7中的HashMap，当hashCode冲突的时候会使用同一个链表存放，如果链表的长度过长会导致查询效率非常慢，时间复杂度为o(N)所以在Java8中HashMap使用数组+链表+红黑树，在链

2、表中长度大于8的时候，将后面的数据以红黑树实现存放，从而加快检索速度；时间复杂度与空间复杂度基本概念 O(1)：就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话） O(n) ：比如时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法，要找到一个数组里面最大的一个数，你要把n个变量都扫描一遍，操作次数为n，那么算法复杂度是O(n). O(log n)，当数据增大n倍时，耗时增大log n倍（这里的log是以2为底的

3、，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(log n)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。思考：在Java集合中Arraylist、LinkeList、HashMap时间复杂度分别为多少在Java集合中Arraylist、LinkeList、HashMap时间复杂度分别为多少Arraylist的底层是采用数组实现，根据下标查询时间复杂度为o(1)、根据元素值查询时间复杂度o(n);LinkeList底层采用链表实现，根据下标查询时间复杂度为o(log n)、根据元素值查询时间复杂度为o(n);Jdk7Ha

4、shMap底层数组+链表实现，根据key查询时间复杂度为o(1)思考：比如在链表中有1-100个节点，那么现在如何根据下标查询到某个节点1-100 查找63举例查询链表中第63个节点二叉搜索树基本特征二叉搜索树具有如下特征：1.节点的左子树只包含小于当前根节点的数2.节点的右子树只包含大于当前根节点的数3.所有左子树和右子树自身必须也是二叉搜索树查找效率：20亿个点 也就是查询231=21 时间复杂度：2x=nx=log2n=logn 二叉二叉搜索树存在的缺点不平衡 和时间插入的顺序有关系，使用插入的第一个节点作为平衡点，如果插入第一个是为0的情况下，最后成为了一条线。所以：查找时间复杂度其实

5、就是为树的深度，也就是变为O(n)建议使用平衡二叉树，红黑树是平衡二叉树一种实现方案什么是红黑树红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。基本特征：1.每个节点不是红色就是黑色2.不可能有连在一起的红色节点3.根节点都是黑色4.每个红色节点的两个子节点都是黑色红黑树变换规则：1.改变节点颜色2.左旋转3.右旋转红黑树变换规则 改变颜色和旋转变颜色的情况：当前节点父亲是红色，且它的祖父亲节点的另一个子节点也是红色(叔叔节点)： 1.将父亲节点设置为黑色 2.将叔叔节点设为黑色 3.将祖父也就是父亲的父亲设为红色

6、4.把指针定义到祖父节点设为当前操作左旋转： 左旋：当父亲节点为红色情况，叔叔的节点为黑色的情况，且当前的节点是右子树，左旋转以父节点作为左旋； 右旋转:当父亲节点为红色情况，叔叔的节点为黑色的情况，且当前的节点是左子树，右旋转以 1.将父节点变为黑色2.将祖父节点变为红色(爷爷)3.以祖父节点开始旋转Jdk1.8比1.7HashMap优化了那些地方数据结构：Jdk1.7使用数组+链表Jdk1.8使用数组+链表+红黑树（解决链表过长查询慢的问题）(当链表深度达到8的时候，就会采用红黑树存放，这时候时间复杂度为O (n )变为O(log n)扩容线程安全问题：Jdk1.7采用头插法，在数组扩容的时候容易导致死循环问题、Jdk