ArrayList底层原理在构造一个包含指定元素的列表初始化方法中JDK 1.8 里 Collection 转换为 Object[] 时可能会出现问题转换出来的结果可能不是 Object[] 类型。这是因为每个集合的 toArray 方法实现都不一样所以需要和 elementData 数组进行对比判断是否为 Object[]。如果不是 Object[]则需要通过 copyOf 进行数组转换底层实际上使用了 System.arraycopy 方法完成数组转换。如果构造时没有任何参数则初始化一个长度为 10 的数组。扩容机制添加元素时在末尾进行追加执行 size1。如果数组为空minCapacity最小容量就等于 size1也就是 1空的数组放不了数据。此时通过 max 方法对默认容量和 minCapacity 进行大小比较取最大值将 minCapacity 变为 10初始容量即为 10。第一次进来初始容量是 10之后再进来时如果需要的容量大于 10就开始扩容。扩容时新数组的大小 老数组的大小 老数组大小 1将老数组大小向右移动一位得到老数组大小的一半相当于 1.5 倍扩容随后进行各种判断。failFast 机制创建迭代对象时将全局的 modCount 赋值给迭代器的局部变量 expectedModCount。在迭代过程中如果 modCount ! expectedModCount则迅速抛出异常。原理同时两个线程执行a 线程执行 add 方法b 线程执行迭代查询方法并调用 next 方法。在 b 线程查询的一瞬间初始化迭代器的时候比如初始化的 expectedModCount 值为 8但此时 a 线程也在进行 add 添加操作add 的时候会对 modCount 进行 操作导致 modCount 和 expectedModCount 两个变量的值不一致从而触发了 failFast 机制。因为 ArrayList 是线程不安全的所以会出现这种问题。解决办法是使用 Collections 工具类中的 synchronizedList 方法进行同步处理使其变为线程安全的。单向链表单向链表只可以从前往后找最前面为一个虚拟空节点目的是使得插入第一条数据时不用去判断它是不是头节点。添加的时候比如在索引 2 的位置插入 node 值 100就可以用 prev.nextprev 表示索引位 2 的前一个索引位指向这个 node 节点node.nextnode 表示要插入的索引值指向原先 prev.next 指向的位置就可以得出node.next prev.nextprev.next node。删除节点的时候需要找到要删除节点的前一个节点 prev要删除的节点为 delNode。需要让 prev.next 指向 delNode.next 指向的位置也就是删除节点的下一个节点。最后要把 delNode 赋值为 null让 GC 进行回收得出prev.next delNode.nextdelNode null。注意一点不能直接把 delNode 直接指向 delNode.next即 delNode delNode.next这样会导致 delNode 无法被删除。双向链表LinkedList 就是基于双向链表实现的除了继承 List 接口还会实现队列接口。add 方法有两种方式1、add 方法中的 linkLast表示向尾部去添加数据。三个构造参数中l 表示指向的前一个节点e 表示当前加入的节点next 指向的是下一个节点。因为是在尾部添加数据所以指向的下一个节点为 null。2、push 中的 linkFirst表示向头部去添加数据。prev 跟上面一样指向前一个节点。因为这个方法是向头部添加所以当前添加的位置就是头部前面没有任何节点。e 表示当前添加的数据节点f 表示当前数据的下一个节点位置。树二叉树概念每个节点最多只能有两个子节点子节点分为左节点和右节点。满二叉树条件所有非叶子节点都存在左子树和右子树并且所有叶子节点都在最后一层的二叉树。叶子节点只能在最后一层非叶子节点的度一定是 2。同样深度的二叉树中满二叉树的节点个数最多叶子数也最多。完全二叉树条件如果该二叉树的所有叶子节点都在最后一层或者倒数第二层而且最后一层的叶子节点在左边连续倒数第二层的叶子节点在右边连续。二叉搜索树BST也叫二叉排序树。任何一个非叶子节点要求左子节点的值比当前节点的值小右子节点的值比当前节点的值大。如果遇到相同的值可以将该节点放在左子节点或右子节点。二叉搜索树的深度优先遍历分为前序遍历、中序遍历、后序遍历。前序遍历先输出父节点再遍历左子树和右子树。中序遍历先遍历左子树再输出父节点再遍历右子树。中序遍历的结果是有序的。后序遍历先遍历左子树再遍历右子树最后输出父节点。二叉搜索树的问题比如数据1, 2, 3, 4, 5, 6创建 BST左子树全部为空更像一个单链表。插入速度没有影响。查询速度明显降低。解决方案是平衡二叉树。平衡二叉树AVL也叫平衡二叉搜索树必须满足 BST 的特征。任意一个节点平衡因子的绝对值不超过 1。某节点的高度值 max左子树高度右子树高度 1。每个节点的左子树和右子树的高度差叫做平衡因子左右子树高度差为左子树高度和右子树高度两边值的差不大于 1。因为计算平衡因子出现 2大于了 1所以要经过右旋和左旋来解决不平衡问题。右旋过程ps左旋同理R.right NN.left T3R root根节点。缺点当频繁进行插入和删除操作时AVL 性能会大打折扣效率比较低问题出现在左右旋的时候。每个节点也只能存储一个数据对节点的利用率较差。红黑树前提研究红黑树时叶子节点指的是最后的空节点也就是我们原来理解的叶子节点的孩子节点即每个叶子节点下面分别指向的左右 nil 空节点。根节点是黑色的每个叶子节点都是黑色的红色节点向左倾斜叫做左倾红黑树如果一个节点是红色的那么它的孩子节点都是黑色的从任何一个节点到叶子节点经过的黑色节点个数是一样的。2-3 树每个节点都可以存放一个元素或者两个元素。存放一个元素的节点称为 2-节点存放两个元素的称为 3-节点。每个节点有两个或三个元素的树称为 2-3 树2-3 树满足二叉搜索树的基本性质。2-3 树是绝对平衡的树。前提满足二叉搜索树的特征、维持绝对平衡、不能往 null 节点插入数据。添加 2-3 树的规律如上图最开始添加为 42出现一个一元素二节点再添加一个 50出现一个二元素三节点并且 42 和 50 在同一行因为元素不能往 null 节点插入42 左右子节点都是空所以 50 放到 42 右边紧接着再放入一个 3333 比 42 小所以放在 42 左边此时为一个三元素四节点。2-3 树每个节点只可以存放一个或两个元素此时为三个元素所以要开始分裂最后分裂为二叉搜索树形式分别将 33 和 50 放到 42 的左右节点。以此类推往后接着放元素进行添加、分裂维持平衡。2-3 树中添加一个新元素或者添加到 2-节点或者添加到 3-节点。添加到 2-节点形成一个 3-节点。添加到 3-节点暂时形成一个 4-节点然后把 4-节点进行分裂。如果待融合的节点是 3-节点的叶子节点父节点是 2-节点那么插入的时候要保持绝对平衡。在插入左边的 3-节点时成为了四节点此时要分裂然后出现不平衡需要把开始分裂的节点进行融合保持绝对平衡如下图如果待融入的节点是 3-节点的叶子节点父节点也是 3-节点则需要分裂、融合、分裂直到平衡为止如下图2-3 树和红黑树的等价性看三张图的变化过程2-3 树格式2-3 树演变红黑树半完整左倾红黑树形式