面试复习题-CopyOnWriteArrayList源码分析

逐个分析方法:

构造方法部分

空参构造 CopyOnWriteArrayList()

private transient volatile Object[] array; //transient 防止序列化 volatile 保证可见,有序

public CopyOnWriteArrayList() {
       setArray(new Object[0]);  //新建一个 长度0的数组
   }
final void setArray(Object[] a) {
       array = a;
   }

传递集合的构造方法CopyOnWriteArrayList(Collection<? extends E> c)

//Collection<? extends E> c) 的意思是可以传递 继承了Collection的类 List Set都可以
public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)  //判断传递进来的集合的类型 如果是自己直接转数组就可以了
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            elements = c.toArray();
          
            if (elements.getClass() != Object[].class)  //如果不是Object[]就复制数组
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);     //设置给自己的数组
    }
增加部分 add addIfAbsent

只传值的add(E e)

 public boolean add(E e) {
        final ReentrantLock lock = this.lock;    //加锁
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;   //获取长度
            Object[] newElements = Arrays.copyOf(elements, len + 1);  //利用新数组来完成添加
            newElements[len] = e;   //完成赋值在末尾
            setArray(newElements);  //替换原数组
            return true;
        } finally {
            lock.unlock();
        }
    }

传下标又传值的 add(int index, E element)

public void add(int index, E element) {
      final ReentrantLock lock = this.lock;   //加索
      lock.lock();
      try {
          Object[] elements = getArray();  //获取初始数组
          int len = elements.length;  //获取长度
          if (index > len || index < 0)   //下标异常抛异常
              throw new IndexOutOfBoundsException("Index: "+index+
                                                  ", Size: "+len);
          Object[] newElements;   //创建新数组
          int numMoved = len - index;   //移动的范围
          if (numMoved == 0)   //没移动时 就相当于结尾添加,单纯的给结尾扩容就行
              newElements = Arrays.copyOf(elements, len + 1);
          else { //需要在数组中间插入
              newElements = new Object[len + 1];  //创建新数组 
              System.arraycopy(elements, 0, newElements, 0, index); //复制插入前部分
              System.arraycopy(elements, index, newElements, index + 1,
                               numMoved); //复制插入后部分 空出index的位置
          }
          newElements[index] = element;  //插入index 
          setArray(newElements);  //替换原始数组
      } finally {
          lock.unlock();
      }
  }

接下来是addIfAbsent(E e)

    public boolean addIfAbsent(E e) {
        Object[] snapshot = getArray();   //获取实时初始数组
    //这里返回的是判断要添加的参数 e是否存在,首先看 indexOf方法,这里把现在的初始数组和希望
    //添加的参数添加进去了 ,如果不在返回-1如果存在返回对应下标
    //然后如果存在了,返回的是下标一定>=0 所以没必要添加 返回false
    //如果此时数组里没有e返回的是-1,那么就开始执行添加的方法addIfAbsent(e, snapshot);
        return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
            addIfAbsent(e, snapshot);
    }
    //有参数返回参数下标 没有返回 -1
    private static int indexOf(Object o, Object[] elements,
                               int index, int fence) {
        if (o == null) {   //参数为空
            for (int i = index; i < fence; i++)
                if (elements[i] == null)
                    return i;   //返回下标
        } else {
            for (int i = index; i < fence; i++)
                if (o.equals(elements[i]))
                    return i;    //不为空 返回下标
        }
        return -1;  //不存在返回 -1
    }
   //执行添加 防止并发修改 需要二次判断
    private boolean addIfAbsent(E e, Object[] snapshot) {
        final ReentrantLock lock = this.lock;   //加锁
        lock.lock();
        try {
            Object[] current = getArray();    //再次获取实时初始数组 因为有可能被别人修改了
            int len = current.length;   //获取现在的初始数组长度
            if (snapshot != current) {  //这里主要是为了找到假如初始数组发生变化
                                    //期望值是否已经被其他线程添加到了这个集合中
                // Optimize for lost race to another addXXX operation
                int common = Math.min(snapshot.length, len); //找到两次数组中短的长度,防止下标溢出
                for (int i = 0; i < common; i++)
                    if (current[i] != snapshot[i] && eq(e, current[i]))
                        return false;  //如果出现相同下标两次数组内容不同 
                            //并且期望添加值和新数组里的值相同 就说明不同添加 返回false
                if (indexOf(e, current, common, len) >= 0) //这里是为了搜索刚才没搜索到的部分 
                        //刚才是可短的来的,这回要把第二次搜索到的数组剩余部分检查了
                        return false;
            }
       //下面就是和普通的add一样 写入一个新数组
            Object[] newElements = Arrays.copyOf(current, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
删除部分 根据Index和根据对象删除

根据下标删除 remove(int index)

public E remove(int index) {
     final ReentrantLock lock = this.lock;  //加锁
     lock.lock();
     try {
         Object[] elements = getArray();  //获取初始数组
         int len = elements.length;    //获取初始数组长度
         E oldValue = get(elements, index);   //根据index获取原本的值
         int numMoved = len - index - 1;   //获取偏移量
         if (numMoved == 0)   //偏移量为0 相当于末尾删除
             setArray(Arrays.copyOf(elements, len - 1));
         else {
             //从中间删除拷贝跳过index部分
             Object[] newElements = new Object[len - 1];  //新建数组
             System.arraycopy(elements, 0, newElements, 0, index); //拷贝index前数据
             System.arraycopy(elements, index + 1, newElements, index,
                              numMoved); //拷贝Index后数据
             setArray(newElements);  //将拷贝的设置为新的数组
         }
         return oldValue;
     } finally {
         lock.unlock();
     }
 }

private E get(Object[] a, int index) {
     return (E) a[index];
 }

 final Object[] getArray() {
     return array;
 }

 final void setArray(Object[] a) {
     array = a;
 }

根据元素删除remove(Object o) 这个就比根据下标复杂了

public boolean remove(Object o) {
     //第一次获取初始数组
      Object[] snapshot = getArray(); 
//还是判断是否包含待删除元素 不是就反回false表示其他线程已经删除了
// 否就执行remove(Object o, Object[] snapshot, int index)
      int index = indexOf(o, snapshot, 0, snapshot.length);
      return (index < 0) ? false : remove(o, snapshot, index);
  }
//有参数返回参数下标 没有返回 -1
  private static int indexOf(Object o, Object[] elements,
                             int index, int fence) {
      if (o == null) {   //参数为空
          for (int i = index; i < fence; i++)
              if (elements[i] == null)
                  return i;   //返回下标
      } else {
          for (int i = index; i < fence; i++)
              if (o.equals(elements[i]))
                  return i;    //不为空 返回下标
      }
      return -1;  //不存在返回 -1
  }
//核心的地方来了
//Object o 期望删除得值
//Object[] snapshot 第一次获取得数组
//int index 第一次获取得待删除元素在snapshot  中得位置
private boolean remove(Object o, Object[] snapshot, int index) {
      final ReentrantLock lock = this.lock;  //加锁
      lock.lock();
      try {
          Object[] current = getArray();   //第二次获取初始数组
          int len = current.length; //获取第二次获取的初始数组的长度
          if (snapshot != current) findIndex: {  //如果两次获取二点数组不一样,就有问题了
          //这里需要找到期望修改的e在第二次获取到的最新数组中的位置
          //findIndex: 是break:标识 表示跳出循环就跳出到这里不全都跳
         //这里出现问题就是第一次值没有被删,到这里已经被删除或者数组发生了其他的改变
              int prefix = Math.min(index, len);   //获取在第一次数组中的下标
                                          //和第二次的长度比较取 最小值,防止下标溢出
                                        //e.g. 第一次要检测到待删除元素在最后一位然后
                                        //其他线程已经删除了 length值减少 index会溢出
                                        
              for (int i = 0; i < prefix; i++) {   //循环最小值长度
                  if (current[i] != snapshot[i] && eq(o, current[i])) { 
//如果第一次第二次数组相同下标值不同并且期望修改的值和此时第二次获取数组值一样就记录
                      index = i;   //记录此时 期望删除值得位置
                      break findIndex;   //跳出循环 执行删除部分 Object[] newElements = new Object[len - 1];
                  }
              }
              if (index >= len)   //下标大于第二次数组长度 说明可能已经被删除了
                  return false;
              if (current[index] == o)  //如果此时第二次数组中index正好是对应元素,跳出执行删除
                  break findIndex;
              index = indexOf(o, current, index, len); //获取待删除的值在第二次数组的位置
              if (index < 0) //如果不存在就说明已经删除了
                  return false;
          }
//通过CopyOnWrite 删除 创建新数组 截取除了待删除之外的其他数据,并setArray记录下来
          Object[] newElements = new Object[len - 1];
          System.arraycopy(current, 0, newElements, 0, index);
          System.arraycopy(current, index + 1,
                           newElements, index,
                           len - index - 1);
          setArray(newElements);
          return true;
      } finally {
          lock.unlock();
      }
  }


替换部分

set(int index, E element)

public E set(int index, E element) {
        final ReentrantLock lock = this.lock; //加索
        lock.lock();
        try {
            Object[] elements = getArray();     //获取初始数组
            E oldValue = get(elements, index);   //根据下标获取数组里的旧值

            if (oldValue != element) {  //旧值不等于新值才替换
      //复制一个新数组,然后把Index值进行替换,然后再保存数组
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,658评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,482评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,213评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,395评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,487评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,523评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,525评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,300评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,753评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,048评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,223评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,905评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,541评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,168评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,417评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,094评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,088评论 2 352

推荐阅读更多精彩内容