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

Guava类库中的Multisets的实现机制

1. Multisets数据结构，虽然它不怎么经常用。
2. 我们知道Java类库中的Set不能存放相同的元素，且里面的元素是无顺序的；
3. List是能存放相同的元素，而且是有顺序的。
4. Multisets是能存放相同的元素，但是元素之间的顺序是无序的。

从这里也可以看出，Multisets肯定不是实现Java中Set接口的.因为Set接口是不能存放相同的元素Java中的Set 里面的元素有点像 :[A, C, B]，而 Multiset 会是这样 : [A ×2, C ×3, B ×5]，这个是有区别的

需要统计一篇文章中各个单词出现的次数，我们可能用下面的方法来实现：

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);
        }
    }
}

怎么去获取某个单词的数量呢？处理起来的感觉差不多，做起来很烦，程序员都喜欢偷工减料的，哈哈！所有MutiSet的作用就是这样的，这种集合在STL中很早就有了，不过真的使用的比较少的。

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

类的图结构

Multiset接口

• 这里处理的意义就是MutliSet作为一个接口，面向接口编程下面有很多的实现。
• 第二这里要增加一些特有的属性和方法

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);

}

AbstractCollection

这个是JDK提供的一些基础的操作库，自己去看看吧！抽象的~提供了tostring，clear等等，不过好多都是模板方法，要调用子类的具体的实现

AbstractMultiset抽象

• 抽象的MutliSet提供了一些基本的操作，具体的实现会根据子类的不同而不同
• 这里写了很多的额Multisets.这样的实现，提高了重用的效果，感觉还不错哦！
• 有点像将接口作为函数的参数，调用接口的方法，这种函数事编程的风格！
  Google Guava 写了很多的这样的方法！确实很厉害！
  Multiset.XXX　这里的方法其实调用具体的实现哦！

 /**
   * 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);
  }

这个抽象类，提供了和MultiSet更相关的一些操作，为下层的实现简化了很多。

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();
  }
}

AbstractMapBasedMultiset这里才有真正的感觉了，容器组合进来进行处理数据开始

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);
  }

}

Count保存数据的~

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;
  }
}

HashMultiset LinkedHashMultiset EnumMultiset

• 有了上面的作为支撑，下面的代码实现起来也就是分分钟搞定的事情！
• 使用HashMultiset作为例子

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());
  }
}

整个工程就这样完了诶….慢慢的体会吧！哈这个需要时间去理解别人这样写为啥好！

最后

以上就是要减肥秋天为你收集整理的Guava类库中的Multisets的实现机制源码分析的全部内容，希望文章能够帮你解决Guava类库中的Multisets的实现机制源码分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。