Loading... ## 阅读来源 > 本文阅读源 微信公众号 [彤哥读源码](https://mp.weixin.qq.com/mp/profile_ext?action=home&__biz=MzkxNDEyOTI0OQ==&scene=124#wechat_redirect) > 您可以点击 [文章系列目录](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzkxNDEyOTI0OQ==&action=getalbum&album_id=1538024362992254978&scene=173#wechat_redirect) 一起学习 > 建议您在此之前,先查看 [阅读建议](https://mp.weixin.qq.com/s/dn4zwUPdtoott91ttEfM5g) > > 您也可以一边查看[源代码](https://gitee.com/alan-tang-tt/yuan)一边进行阅读 > > **由于读书笔记的特殊性,大篇幅为原文复制** > > **引用部分为笔记,脚注部分为重点提示,拓展标题为根据文章后期自我总结的额外学习拓展** --- ## 笔记内容 ### ArrayList [阅读原文](https://mp.weixin.qq.com/s/EBweLpilAjW0uBTqmFAp2g) #### 继承体系 ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。 ArrayList实现了List,提供了基础的添加、删除、遍历等操作。 ArrayList实现了RandomAccess,提供了随机访问的能力。 ArrayList实现了Cloneable,可以被克隆。 ArrayList实现了Serializable,可以被序列化。 #### 总结 (1)ArrayList内部使用数组存储元素,当数组长度不够时进行扩容,每次加一半的空间,ArrayList不会进行缩容; (2)ArrayList支持随机访问,通过索引访问元素极快,时间复杂度为O(1); (3)ArrayList添加元素到尾部极快,平均时间复杂度为O(1); (4)ArrayList添加元素到中间比较慢,因为要搬移元素,平均时间复杂度为O(n); (5)ArrayList从尾部删除元素极快,时间复杂度为O(1); (6)ArrayList从中间删除元素比较慢,因为要搬移元素,平均时间复杂度为O(n); (7)ArrayList支持求并集,调用addAll(Collection c)方法即可; (8)ArrayList支持求交集,调用retainAll(Collection c)方法即可; (7)ArrayList支持求单向差集,调用removeAll(Collection c)方法即可; > 1. ArrayList的复杂度还是很低的,其中进行中间增删的操作复杂度为O(n)是由于需要进行元素搬移 > 2. 在retainAll、removeAll中,使用了一个方法 > > **boolean batchRemove(Collection<?> c, boolean complement)** > > **双指针遍历数组,读指针每次自增1,写指针放入元素的时候才+1,可以达到不需要额外空间在原数组上操作就可以完成批量移除** > > **方法中,在finally实现业务逻辑,证明在必要的时候,try-catch-finally中的finally也可以用来完成业务逻辑,并不是只能死板的用于异常捕获和日志记录** > 3. 在增加元素时,会检查并扩容,但是在减少元素时不会扩容 > 4. 减少元素进行圆度搬移时,最后一个索引位置赋值为null,可以帮助GC回收,这个操作很细节 #### 拓展 使用关键字 **transient** 可以使相关字段不被序列化 ### CopyOnWriteArrayList CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组,这样保证了只阻塞写操作,不阻塞读操作,实现读写分离。 [阅读原文](https://mp.weixin.qq.com/s/3P3km4pHoudbR_ky29twAA) #### 继承体系 CopyOnWriteArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。 CopyOnWriteArrayList实现了List,提供了基础的添加、删除、遍历等操作。 CopyOnWriteArrayList实现了RandomAccess,提供了随机访问的能力。 CopyOnWriteArrayList实现了Cloneable,可以被克隆。 CopyOnWriteArrayList实现了Serializable,可以被序列化。 #### 总结 (1)CopyOnWriteArrayList使用ReentrantLock重入锁加锁,保证线程安全; (2)CopyOnWriteArrayList的写操作都要先拷贝一份新数组,在新数组中做修改,修改完了再用新数组替换老数组,所以空间复杂度是O(n),性能比较低下; (3)CopyOnWriteArrayList的读操作支持随机访问,时间复杂度为O(1); (4)CopyOnWriteArrayList采用读写分离[^1]的思想,读操作不加锁,写操作加锁,且写操作占用较大内存空间,所以适用于读多写少的场合; (5)CopyOnWriteArrayList只保证最终一致性,不保证实时一致性[^2] > 1. CopyOnWriteArrayList是线程安全的ArrayList实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组 > 2. 没有size,因为每次都是拷贝新数组替换,所以不存在扩容缩容问题,有多少元素就有多大容量 > 3. 由于加锁和数组拷贝机制,空间和时间复杂度都没有ArrayList优秀 ### HashMap [阅读原文](https://mp.weixin.qq.com/s/9acWEJP1XNgD3NMgWD42Yg) #### 继承体系 HashMap实现了Cloneable,可以被克隆。 HashMap实现了Serializable,可以被序列化。 HashMap继承自AbstractMap,实现了Map接口,具有Map的所有功能。 #### 存储结构 Java中,HashMap的实现采用了(**数组 + 链表 + 红黑树**)的复杂结构,**数组的一个元素又称作桶**。 在添加元素时,会**根据hash值算出元素在数组中的位置**,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素**以链表的形式放置在链表的尾部**。 当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把**链表转化为红黑树**,从而提高效率。 数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以**当元素数量非常多的时候,转化为红黑树能极大地提高效率**。 > 1. 桶:是一个典型的单链表(包含下一个节点的地址)节点 **Node<K,V>**,使用**final int hash**存储key计算得到的hash值,同时实现了**Map.Entry<K,V>** > 2. TreeNode:典型的树节点 **TreeNode<K,V>**(包含左节点、右节点、父节点,重点是,prev是链表中的节点,用于在删除元素的时候可以快速找到它的前置节点)继承了**LInkedHashMap.Entry** #### 总结 (1)HashMap是一种散列表,采用(数组 + 链表 + 红黑树)的存储结构; (2)HashMap的默认初始容量为16(1<<4),默认装载因子为0.75f,容量总是2的n次方; (3)HashMap扩容时每次容量变为原来的两倍; (4)当桶的数量小于64时不会进行树化,只会扩容; (5)当桶的数量大于64且单个桶中元素的数量大于8时,进行树化; (6)当单个桶中元素数量小于6时,进行反树化; (7)HashMap是非线程安全的容器; (8)HashMap查找添加元素的时间复杂度都为O(1); #### 彩蛋 红黑树知多少? 红黑树具有以下5种性质: (1)节点是红色或黑色。 (2)根节点是黑色。 (3)每个叶节点(NIL节点,空节点)是黑色的。 (4)每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) (5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 红黑树的时间复杂度为O(log n),与树的高度成正比。 红黑树每次的插入、删除操作都需要做平衡,平衡时有可能会改变根节点的位置,颜色转换,左旋,右旋等。 > **红黑树需要掌握** #### 拓展 1. 构造方法中有一个tableSizeFor方法值得关注 ```java static final int tableSizeFor(int cap) { // 扩容门槛为传入的初始容量往上取最近的2的n次方 int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return(n < 0) ? 1: (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } ``` 该方法使用位操作达到寻找向上的最近的2的n次方的效果,非常硬核和高效,可以重点掌握。 [^1]: 因为只需要在写时保证线程安全,读无需关心线程安全问题 [^2]: 在多线操作时,只保证最终插入的数据都存在,但是并不保证先执行add操作的元素的索引一定在后执行add操作之前 Last modification:October © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏