Guava ImmutableSet.Builder源码分析，移位原码补码反码复习

1
2
3
 public static <E> Builder<E> builder() {
    return new Builder<E>();
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
  /**
   * A builder for creating {@code ImmutableSet} instances
   *
   *   static final ImmutableSet<Color> GOOGLE_COLORS =
   *       ImmutableSet.<Color>builder()
   *           .addAll(WEBSAFE_COLORS)
   *           .add(new Color(0, 191, 255))
   *           .build();}</pre>
   */
  public static class Builder<E> 
    extends 
    ImmutableCollection.ArrayBasedBuilder<E> {
    /**
     * Creates a new builder. 
     *The returned builder is equivalent to the builder
     * generated by {@link ImmutableSet#builder}.
     *下面这些都是调用父类的方法
     */
    public Builder() {
      this(DEFAULT_INITIAL_CAPACITY);//4
    }
    Builder(int capacity) {
      super(capacity);
    }
    @Override
    public Builder<E> add(E element) {
      super.add(element);
      return this;
    }
    @Override
    public Builder<E> add(E... elements) {
      super.add(elements);
      return this;
    }
    @Override
    public Builder<E> addAll(Iterable< ? extends E> elements) {
      super.addAll(elements);
      return this;
    }
    @Override
    public Builder<E> addAll(Iterator< ? extends E> elements) {
      super.addAll(elements);
      return this;
    }
    @Override
    Builder<E> combine(ArrayBasedBuilder<E> builder) {
      super.combine(builder);
      return this;
    }
    /**
     * Returns a newly-created  based on the contents of
     * the {@code Builder}.
     * construct调用当前类ImuutableSet的构造方法，这里要处理去重
     * 所以size改变感觉没啥用
     */
    @Override
    public ImmutableSet<E> build() {
      ImmutableSet<E> result = construct(size, contents);
      // construct has the side effect of deduping contents, so we update size
      // accordingly.
      size = result.size();
      return result;
    }
  }
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
abstract static class ArrayBasedBuilder<E>
     extends ImmutableCollection.Builder<E> {
    Object[] contents;//容器哦！
    int size;//当前容器使用的大小！
    ArrayBasedBuilder(int initialCapacity) {
      //CollectPreconditions 中的检测不为负数
      checkNonnegative(initialCapacity, "initialCapacity");
      this.contents = new Object[initialCapacity];
      this.size = 0;
    }

    /**
     * Expand the absolute capacity of the builder 
     * so it can accept at least
     * the specified number of elements without being resized.
     * 每增加一个元素就去检测当前的容器的大小，然后在进行扩容
     * expandedCapacity是父类扩容的方法，一会会说
     * Arrays.copyOf复制一个数据，扩展它的长度
     */
    private void ensureCapacity(int minCapacity) {
      if (contents.length < minCapacity) {
        this.contents =
            Arrays.copyOf(
                this.contents, 
                expandedCapacity(contents.length, minCapacity)
                );
      }
    }
    /**
    *这里只是添加元素，对于底层Set的数据构造，是由他们自己去搞定
    */
    @Override
    public ArrayBasedBuilder<E> add(E element) {
      checkNotNull(element);//非空判断
      ensureCapacity(size + 1);//扩容
      contents[size++] = element;//插入数据
      return this;
    }
   /*
    *static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 
    *从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。 
    */
    @Override
    public Builder<E> add(E... elements) {
      checkElementsNotNull(elements);
      ensureCapacity(size + elements.length);
      System.arraycopy(elements, 0, contents, size, elements.length);
      size += elements.length;
      return this;
    }
     /*
     *Iterable抵代器都是基本上Collection
     */
    @Override
    public Builder<E> addAll(Iterable<? extends E> elements) {
      if (elements instanceof Collection) {
        Collection<?> collection = (Collection<?>) elements;
        ensureCapacity(size + collection.size());
      }
      super.addAll(elements);
      return this;
    }
    //两个builder和并啊
    @CanIgnoreReturnValue
    ArrayBasedBuilder<E> combine(ArrayBasedBuilder<E> builder) {
      checkNotNull(builder);
      ensureCapacity(size + builder.size);
      System.arraycopy(builder.contents, 0, this.contents, size, builder.size);
      size += builder.size;
      return this;
    }
  }
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
   * Abstract base class for builders of 
   * ImmutableCollectiontypes.
   */
  public abstract static class Builder<E> {
    static final int DEFAULT_INITIAL_CAPACITY = 4;
    //默认的数组的大小
    //如下是扩容的具体的做法，非常的精妙，一会在分析
    //Integer.highestOneBit 
    static int expandedCapacity(int oldCapacity, int minCapacity) {
      if (minCapacity < 0) {
        throw new AssertionError("cannot store more than MAX_VALUE elements");
      }
      // careful of overflow!
      //这里是扩大容量扩大
      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
      if (newCapacity < minCapacity) {
        //highestOneBit取最高位的值，-1也就是相当于右移一位
        //比如 1101->1000(highestOneBit)->0111(-1)->1111(<<1)
        //这样处理的好处因为minCapacity是大于0的，在当前位肯定不会超出31位
        //这样就可以把当前位全部填充为1，这个是最大的值了。
        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
      }
      //这里的处理感觉没必要了，不会超位的
      if (newCapacity < 0) {
        newCapacity = Integer.MAX_VALUE;
        // guaranteed to be >= newCapacity
      }
      return newCapacity;
    }

    Builder() {}
    //模板方法，留给子类自己去实现
    public abstract Builder<E> add(E element);
    public Builder<E> add(E... elements) {
      for (E element : elements) {
        add(element);
      }
      return this;
    }
    public Builder<E> addAll(Iterable<? extends E> elements) {
      for (E element : elements) {
        add(element);
      }
      return this;
    }

    @CanIgnoreReturnValue
    public Builder<E> addAll(Iterator<? extends E> elements) {
      while (elements.hasNext()) {
        add(elements.next());
      }
      return this;
    }

    /**
     *这里的构造才是最后最重要的部门哦，最后被ImmutableSet构造，你可以回去看看逻辑 ImmutableSet<E> result = construct(size, contents);
     * Returns a newly-created 
     *{@code ImmutableCollection} of the appropriate
     * type, containing the elements provided to this builder.
     *
     * <p>Note that each builder class covariantly returns the appropriate type
     * of {@code ImmutableCollection} from this method.
     */
    public abstract ImmutableCollection<E> build();
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int highestOneBit(int i) {
    // 例如1000
    i |= (i >>  1); 
    // 使前2位变为1，相当于i = i | (i >> 1); 
    //i = 1000 | 0100 = 1100
    i |= (i >>  2); 
    // 使前4位变为1，由于上一步确保了前两位都是1，
    //所以这一次移动两位，1111
    i |= (i >>  4); // 使前8位变为1，1111
    i |= (i >>  8); // 使前16位变为1，1111
    i |= (i >> 16); // 使前32位变为1，1111
    return i - (i >>> 1); 
    // i >>> 1 无符号右移，使最高位为0，其余位为1
    //相减即得出结果，1111 - 0111 = 1000 
}