Guava类库中的Multisets的实现机制源码分析

1
2
3
4
5
6
7
8
9
10
11
public void wordCounts(List words) {
    Map<String, Integer> counts = new HashMap<String, Integer>();
    for (String word : words) {
        Integer count = counts.get(word);
        if (count == null) {
            counts.put(word, 1);
        } else {
            counts.put(word, count + 1);
        }
    }
}

1
int goodCount = counts.get("XXX");

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
public interface Multiset<E> extends Collection<E> {

  /**
   * multiset, which is given by {@code entrySet().size()}.
   */
  @Override
  int size();

  int count(@Nullable @CompatibleWith("E") Object element);
  //增加一个或者多个元素，体现在count计数上面
  int add(@Nullable E element, int occurrences);

  int remove(@Nullable @CompatibleWith("E") Object element, int occurrences);
  //设置某个元素的数量
  int setCount(E element, int count);
  //有条件的设置数量只用oldcount=当前元素的数量才设置
  boolean setCount(E element, int oldCount, int newCount);

//这个的作用没发现
  Set<E> elementSet();

//这个就是和HashMap中的Entry一样的，方便我们去查看
//容器中的元素的值
  Set<Entry<E>> entrySet();

//Entry 条目
  interface Entry<E> {

    E getElement();

    int getCount();

    @Override
    boolean equals(Object o);

    @Override
    int hashCode();

    @Override
    String toString();
  }


  @Override
  // TODO(kevinb): caveats about equivalence-relation?
  boolean equals(@Nullable Object object);


  @Override
  Iterator<E> iterator();

  @Override
  boolean contains(@Nullable Object element);

  @Override
  boolean containsAll(Collection<< ?> elements);


  @Override
  boolean add(E element);


  @Override
  boolean remove(@Nullable Object element);

  @Override
  boolean removeAll(Collection< ?> c);

}

1
2
3
4
5
6
7
8
9
10
11
 /**
   * An implementation of {@link Multiset#size}.
   */
  static int sizeImpl(Multiset< ?> multiset) {
    long size = 0;
    for (Entry< ?> entry : multiset.entrySet()) {
      size += entry.getCount();
    }
    return Ints.saturatedCast(size);
  }

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
abstract class AbstractMultiset<E> extends AbstractCollection<E> implements Multiset<E> {

  //这种传递this的写法很好玩，实际调用的是子类的this
  //将所有的业务逻辑写到一个公共类中去了..
  @Override
  public int size() {
    return Multisets.sizeImpl(this);
  }

  @Override
  public boolean isEmpty() {
    return entrySet().isEmpty();
  }

  @Override
  public boolean contains(@Nullable Object element) {
    return count(element) > 0;
  }

  @Override
  public Iterator<E> iterator() {
    return Multisets.iteratorImpl(this);
  }

  @Override
  public int count(@Nullable Object element) {
    for (Entry<E> entry : entrySet()) {
      //这样可以避免null
      if (Objects.equal(entry.getElement(), element)) {
        return entry.getCount();
      }
    }
    return 0;
  }

  @Override
  public boolean add(@Nullable E element) {
    //这种add都是调用子类的实现哦！
    //由于不同的add 在HashMulitSet和LinkHashMutilset表现不一样
    add(element, 1);
    return true;
  }
  //留给子类实现
  @Override
  public int add(@Nullable E element, int occurrences) {
    throw new UnsupportedOperationException();
  }

  @Override
  public boolean remove(@Nullable Object element) {
    return remove(element, 1) > 0;
  }
  @Override
  public int remove(@Nullable Object element, int occurrences) {
    throw new UnsupportedOperationException();
  }

  @Override
  public int setCount(@Nullable E element, int count) {
    return Multisets.setCountImpl(this, element, count);
  }
  //这种写法有啥子好处，重构中说，一眼就可以知道这个的作用？
  //将具体的实现都通通弄走了，一看就知道这个在做什么！
  @Override
  public boolean setCount(@Nullable E element, int oldCount, int newCount) {
    return Multisets.setCountImpl(this, element, oldCount, newCount);
  }

  @Override
  public boolean addAll(Collection< ? extends E> elementsToAdd) {
    return Multisets.addAllImpl(this, elementsToAdd);
  }

  @CanIgnoreReturnValue
  @Override
  public boolean removeAll(Collection< ?> elementsToRemove) {
    return Multisets.removeAllImpl(this, elementsToRemove);
  }

  @CanIgnoreReturnValue
  @Override
  public boolean retainAll(Collection< ?> elementsToRetain) {
    return Multisets.retainAllImpl(this, elementsToRetain);
  }
  //这种方法很多地方都有用，提供一个utils方法
  @Override
  public void clear() {
    Iterators.clear(entryIterator());
  }

  // 这里有两种不同类型的Set,为啥啊？这个我去查看了
  //没看的具体的逻辑，不过应该有用，有了当前对象的this的引用
  private transient Set<E> elementSet;

  @Override
  public Set<E> elementSet() {
    Set<E> result = elementSet;
    if (result == null) {
      elementSet = result = createElementSet();
    }
    return result;
  }

  Set<E> createElementSet() {
    return new ElementSet();
  }

  @WeakOuter
  class ElementSet extends Multisets.ElementSet<E> {
    @Override
    Multiset<E> multiset() {
      //这里又使用这种this，感觉好强大
      return AbstractMultiset.this;
    }
  }
//为了遍历entrySet，其实就是为了遍历容器中的数据
//在下一个组合Map里面就可以看到，这个就是为了遍历
//Map中的数据而实现的哦~~
  abstract Iterator<Entry<E>> entryIterator();

  abstract int distinctElements();

  private transient Set<Entry<E>> entrySet;
  //延迟初始化，做的好啊！
  @Override
  public Set<Entry<E>> entrySet() {
    Set<Entry<E>> result = entrySet;
    if (result == null) {
      entrySet = result = createEntrySet();
    }
    return result;
  }

  @WeakOuter
  class EntrySet extends Multisets.EntrySet<E> {
    @Override
    //当前对象这个意义很大
    Multiset<E> multiset() {
      return AbstractMultiset.this;
    }

    @Override
    public Iterator<Entry<E>> iterator() {
      return entryIterator();
    }

    @Override
    public int size() {
      return distinctElements();
    }
  }

  Set<Entry<E>> createEntrySet() {
    return new EntrySet();
  }

  @Override
  public boolean equals(@Nullable Object object) {
    return Multisets.equalsImpl(this, object);
  }

  @Override
  public int hashCode() {
    return entrySet().hashCode();
  }

  @Override
  public String toString() {
    return entrySet().toString();
  }
}

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216

abstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E> implements Serializable {

  //这个是真正的容器，组合进来的哈哈！
  private transient Map<E, Count> backingMap;

  //缓存大小以提高效率。 使用长时间让我们避免需要
  //溢出检查，并确保size（）将正常工作即使
  //multiset曾经大于Integer.MAX_VALUE。
  private transient long size;

  /** Standard constructor. */
  protected AbstractMapBasedMultiset(Map<E, Count> backingMap) {
    this.backingMap = checkNotNull(backingMap);
    this.size = super.size();
  }
  //提供一个简单的遍历Map中的集合数据的接口和hashMap的EntrySet类似的
  @Override
  public Set<Multiset.Entry<E>> entrySet() {
    return super.entrySet();
  }
  //entryset使用的使用就是需要你这个玩意
  @Override
  Iterator<Entry<E>> entryIterator() {

    //entrySet()其实就是提供接口遍历一下 
    //hashMap中的Node<K,V>[] table数组提供了抽象
    final Iterator<Map.Entry<E, Count>>
    backingEntries = backingMap.entrySet().iterator();

    //Multiset.Entry<E>可以获取map中的元素
    return new Iterator<Multiset.Entry<E>>() {
      Map.Entry<E, Count> toRemove;

      @Override
      public boolean hasNext() {
        return backingEntries.hasNext();
      }

      @Override
      public Multiset.Entry<E> next() {
        final Map.Entry<E, Count> mapEntry = backingEntries.next();
        toRemove = mapEntry;
        //这里又对Multiset.Entry进行了抽象
        //封装了一些基本的方法
        /**
        *Multisets.AbstractEntry
        * public int hashCode() {
        *    Object e = this.getElement();
        *    return (e == null?0:e.hashCode()) ^ this.getCount();
        *}
        */
        return new Multisets.AbstractEntry<E>() {
          @Override
          public E getElement() {
            return mapEntry.getKey();
          }

          @Override
          public int getCount() {
            Count count = mapEntry.getValue();
            if (count == null || count.get() == 0) {
              Count frequency = backingMap.get(getElement());
              if (frequency != null) {
                return frequency.get();
              }
            }
            return (count == null) ? 0 : count.get();
          }
        };
      }

      @Override
      public void remove() {
        checkRemove(toRemove != null);
        size -= toRemove.getValue().getAndSet(0);
        backingEntries.remove();
        toRemove = null;
      }
    };
  }

  @Override
  public void clear() {
    for (Count frequency : backingMap.values()) {
      frequency.set(0);
    }
    backingMap.clear();
    size = 0L;
  }

  @Override
  int distinctElements() {
    return backingMap.size();
  }

  @Override
  public int size() {
    //这个Ints方法很厉害的！
    return Ints.saturatedCast(size);
  }
  //这里实现了迭代器，父类也实现了，感觉没有用哈哈！意义一样！
  @Override
  public Iterator<E> iterator() {
    return new MapBasedMultisetIterator();
  }
  /**
  *这里提供了一个遍历器，backingMap中保存的值，提供了删除哈哈，
  *删除重复的元素实际上是减少数量而已
  */
  private class MapBasedMultisetIterator implements Iterator<E> {
    final Iterator<Map.Entry<E, Count>> entryIterator;
    Map.Entry<E, Count> currentEntry;
    int occurrencesLeft;
    boolean canRemove;

    MapBasedMultisetIterator() {
      this.entryIterator = backingMap.entrySet().iterator();
    }

    @Override
    public boolean hasNext() {
      return occurrencesLeft > 0 || entryIterator.hasNext();
    }

    @Override
    public E next() {
      if (occurrencesLeft == 0) {
        currentEntry = entryIterator.next();
        occurrencesLeft = currentEntry.getValue().get();
      }
      occurrencesLeft--;
      canRemove = true;
      return currentEntry.getKey();
    }

    @Override
    public void remove() {
      checkRemove(canRemove);
      int frequency = currentEntry.getValue().get();
      if (frequency <= 0) {
        throw new ConcurrentModificationException();
      }
      if (currentEntry.getValue().addAndGet(-1) == 0) {
        entryIterator.remove();
      }
      size--;
      canRemove = false;
    }
  }

  @Override
  public int count(@Nullable Object element) {
    //函数事编程，代理Maps非空检查！然后或值
    Count frequency = Maps.safeGet(backingMap, element);
    return (frequency == null) ? 0 : frequency.get();
  }
  //诶~这里和我们写的差不多了啊！是不是？
  @Override
  public int add(@Nullable E element, int occurrences) {
    if (occurrences == 0) {
      return count(element);
    }
    checkArgument(occurrences > 0, "cannot be negative: %s", occurrences);
    Count frequency = backingMap.get(element);
    int oldCount;
    if (frequency == null) {
      oldCount = 0;
      backingMap.put(element, new Count(occurrences));
    } else {
      oldCount = frequency.get();
      //好仔细哦~~Int+Int估计会超标哦，所以转换为long之后在去判断！
      long newCount = (long) oldCount + (long) occurrences;
      checkArgument(newCount <= Integer.MAX_VALUE, "too many occurrences");
      frequency.add(occurrences);
    }
    size += occurrences;
    return oldCount;
  }

  @Override
  public int remove(@Nullable Object element, int occurrences) {
    if (occurrences == 0) {
      return count(element);
    }
    checkArgument(occurrences > 0, "occurrences cannot be negative");
    Count frequency = backingMap.get(element);
    if (frequency == null) {
      return 0;
    }

    int oldCount = frequency.get();

    int numberRemoved;
    if (oldCount > occurrences) {
      numberRemoved = occurrences;
    } else {
      numberRemoved = oldCount;
      backingMap.remove(element);
    }

    frequency.add(-numberRemoved);
    size -= numberRemoved;
    return oldCount;
  }
  //非空判断~差不多的方法
  private static int getAndSet(@Nullable Count i, int count) {
    if (i == null) {
      return 0;
    }

    return i.getAndSet(count);
  }

}

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
final class Count implements Serializable {
  private int value;

  Count(int value) {
    this.value = value;
  }

  public int get() {
    return value;
  }

  public void add(int delta) {
    value += delta;
  }

  public int addAndGet(int delta) {
    return value += delta;
  }

  public void set(int newValue) {
    value = newValue;
  }

  public int getAndSet(int newValue) {
    int result = value;
    value = newValue;
    return result;
  }

  @Override
  public int hashCode() {
    return value;
  }
}

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

public final class HashMultiset<E> extends AbstractMapBasedMultiset<E> {


  public static <E> HashMultiset<E> create() {
    return new HashMultiset<E>();
  }

  /**
   * Creates a new, empty {@code HashMultiset} with the specified expected
   * number of distinct elements.
   * 使用具体数量的大小
   */
  public static <E> HashMultiset<E> create(int distinctElements) {
    return new HashMultiset<E>(distinctElements);
  }

  //创建哈哈有数量的元素涩
  public static <E> HashMultiset<E> create(Iterable< ? extends E> elements) {
    HashMultiset<E> multiset = create(Multisets.inferDistinctElements(elements));
    Iterables.addAll(multiset, elements);
    return multiset;
  }

  private HashMultiset() {
    //这里最简单了，哈哈这个就是HashMutiSet，具体的Map让子类来决定！
    super(new HashMap<E, Count>());
  }

  private HashMultiset(int distinctElements) {
    //创建一个可以约定数量的
    super(Maps.<E, Count>newHashMapWithExpectedSize(distinctElements));
  }

  /**
   * 序列化一下，米使用啥子方法虚拟化，就怎么还原
   */
  @GwtIncompatible // java.io.ObjectOutputStream
  private void writeObject(ObjectOutputStream stream) throws IOException {
    stream.defaultWriteObject();
    Serialization.writeMultiset(this, stream);
  }

  @GwtIncompatible // java.io.ObjectInputStream
  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
    stream.defaultReadObject();
    int distinctElements = Serialization.readCount(stream);
    setBackingMap(Maps.<E, Count>newHashMap());
    Serialization.populateMultiset(this, stream, distinctElements);
  }

  private static final long serialVersionUID = 0;
}
static <E> void writeMultiset(Multiset<E> multiset, ObjectOutputStream stream)
    throws IOException {
  int entryCount = multiset.entrySet().size();
  stream.writeInt(entryCount);
  for (Multiset.Entry<E> entry : multiset.entrySet()) {
    stream.writeObject(entry.getElement());
    stream.writeInt(entry.getCount());
  }
}